Lists are Maps

Stevan Apter (sa@nsl.com)

A K list Z is usefully understood as the map from !#Z to the values of Z. M, a variant of K, is implemented in which the primitives ? and ! are reinterpreted to operate on lists thus reconstrued[1].

K

K has atoms, lists, and dictionaries.

Lists are maps[2]. The list Z of length n is a map from !#Z to the values of Z:

    0 -> 10
    1 -> 20
    2 -> 30

We can use this insight to simplify K by reducing the number of ultimate entities, and therefore distinct ideas present in the language[3]. With fewer ideas the language becomes simpler and easier to learn. I call this variant of K "M". In the examples given below, execution in the M console is indicated by the presence of the prompt "m)".

M

K has atoms, lists, and dictionaries. M has atoms and maps. K dictionaries are M maps, and so are K lists.

In M a map is created using dyadic !. The left argument is the domain and the right argument is the range:

    m)a:`a`b`c!10 20 30
  `a`b`c!10 20 30

The domain of a map is retrieved using monadic ![4]:

    m)!a
  `a`b`c

and the range using monadic ?[5]:

    m)?a
  10 20 30

In M lists are also maps, and use the same constructor and deconstructor primitives:

    m)b:0 1 2!20 30 40
  20 30 40

    m)!b
  0 1 2

    m)?b
  20 30 40

The domain of a list can be elided. The constructor is applied automatically:

    m)b~20 30 40
  1b

Display of a list also elides the domain. The deconstructor is applied automatically:

    m)b
  10 20 30

The domain of a list is also a map, whose domain and range are identical.

    m)m:!10 20 30
  0 1 2

    m)(!m)~?m
  1b
The domain of a list is a fixed point of !:, so the predicate for listhood is[6]:

    m)islist:{(!x)~!!x}

Structure

In M we use , to join maps:

    m)1 2,3 4 5
  1 2 3 4 5

    m)(`a`b`c!10 20 30),`b`c!40 50
  `a`b`c!10 40 50

Lists and dictionaries are both maps, but lists are not dictionaries. It would be wrong to insist on dictionary semantics for the concatenation of lists:

    m)1 2,3 4 5
   0 1 0 1 2!1 2 3 4 5

Structural operations in M are otherwise identical to those in K:

    m)|10 20 30
  30 20 10

    m)|`a`b`c!10 20 30
  `c`b`a!30 20 10

Dictionary-maps can "collapse" into list-maps:

    m)0N_0N 0 1 2!10 20 30 40
   20 30 40

and list-maps can "explode" into dictionary-maps:

    m)((,0N)!,10),20 30 40
   0N 0 1 2!10 20 30 40

Mapping list-maps therefore behaves differently in K and M[7]:

In K:

    k)(0 1 2!10 20 30)!0 1 2!40 50 60
  'type

In M:

    m)(0 1 2!10 20 30)!0 1 2!40 50 60
  10 20 30!40 50 60

The universe of M is therefore smaller than that of K. The list Z is identical to the constructed map (!#Z)!Z[8]:

    m)10 20 30~0 1 2!10 20 30
   1b

Concatenation of lists in M behaves differently than the concatenation of the homonymous dictionaries in K[9]:

    m)(0 1!1 2),0 1 2!3 4 5
  1 2 3 4 5

    k)(0 1!1 2),0 1 2!3 4 5
  0 1 2!3 4 5

Here are some analogies from elsewhere in K:

- In K, a mixed list can collapse to a vector, and a vector can explode to become a mixed list.

- In K4, a list of structurally identical maps is a table. To avoid the collapse from list-of-maps to table we add a "sentinel" -- a map with a different structure.

- In K2/3, where ^: is the shape primitive, a list of equal length lists is a matrix or higher-order rectangular array.

Implementation of M in K

The k4 script for M is:

\d .m
e:{f@-6!g@-5!"k)",x}
g:{$[0>t:@x;x;~t;.z.s'x;x~(!);map;x~(!:);dom;x~(?:);val;x~(,);cat;x]}
f:{$[0>t:@x;x;~t;.z.s'x;99h=t;map[!x;.z.s'. x];x]}
dom:{$[(t:@x)in 99h,- 1 4 5 6 7h;!x;~t<0;!#x;!x]}
map:{$[x~!#y;y;x!y]}
val:{$[(t:@x)in 99 10h,- 10 11h;. x;~t<0;x;. x]}
cat:{dfl[x;y],dfl[y]x}
dfl:{$[(99h=@y)&(98h>t)&~0>t:@x;(!#x)!x;x]}
k)\

and is found here:

http://www.nsl.com/k/m.k

An example M script:

a:`a`b`c!10 20 30
!a
?a
b:0 1 2!20 30 40
!b
?b
b~20 30 40
!!10 20 30
1 2,3 4 5
(`a`b`c!10 20 30),`b`c!40 50
0N_0N 0 1 2!10 20 30 40
((,0N)!,10),20 30 40
((,0N)!,10),0 1 2!20 30 40
10 20 30~0 1 2!10 20 30

is found here:

http://www.nsl.com/k/m.m

Operate it this way:

  q m.k
  \l m.m

Reduction to Two Primitives

M extends and overrides three K primitives: ! !: and ?:. We can merge the behavior of the two monads onto !:, thus preserving the original K meaning for ?::

    m)`a`b`c!10 20 30
  `a`b`c!10 20 30

    m)!`a`b`c!10 20 30
  (`a`b`c;10 20 30)

!x returns (domain x;range x).

The two-primitive version of M uses the following modified 'g' function:

    g:{$[0>t:@x;x;~t;.z.s'x;x~(!);map;x~(!:);{(dom x;val x)};x~(,);cat;x]}

NB: m.m will fail with this definition in force.

The revised definition of !: has a few nice properties. For example, where we want to pass the domain and range of a map to a dyadic function:

    k) f[!x;x[]]

as against:

    m) f .!x

and to swap domain and range:

    m)(!).|!`x`y`z!10 20 30
  10 20 30!`x`y`z

Footnotes

  1. This ideas in this note were stimulated by Gregory Landini's work on the philosophy of Bertrand Russell; specifically, the contrast between two different forms of reductionist analysis. For example, the reduction of heat to molecular motion is an explanation of heat, and not the stronger metaphysical claim that heat doesn't exist. On the other hand, the reduction of number and class to logic such as the one carried out by Whitehead and Russell in Principia Mathematica is eliminativist: numbers and classes may exist but mathematics doesn't need them. In that spirit, the work described in this paper is a reduction in the first sense: K says lists exist, and M says they are maps.
  2. Borror, Jeffrey: Q For Mortals (First Edition, 2006) p.42
  3. My claim is that the ontology described in this paper presently exists in K, but is obscured by the particular choice of primitives. That is, a K list just is a map, even though primitives for accessing its domain and range are absent. Note that this claim is entirely independent of implementation details. The reasoning is substantially identical to Arthur Whitney's argument that K lists exist in APL\360. That is, you get K lists from APL arrays by dropping the rectangularity requirement. In this way, enclose, disclose, and boxed/nested arrays are superfluous in K.
  4. In K, where Z is a list, !Z is symbolic type.
  5. in K, where Z is a dictionary, ?Z is a type error, and ?Z is unique.
  6. John Earnest points out that the following are also predicates for listhood:
        m)a:10 20 30
        m)a~?:/a
      1b
        m)a~?a
      1b
    
  7. M-maps are ungrounded. Since !Z and ?Z are lists, they are also maps. M-maps are infinitely deep, infinitely wide trees.
  8. Except in the case noted above, where X and Y are list-maps, there are no maps with dictionary-domain or dictionary-range. That is, even where (#X)=#Y, if either X or Y is a dictionary, X!Y is an error. Where X is a list and Y is a dictionary, X!Y is a length error and Y!X and Y!Y are both type errors.
  9. As observed by Nick Psaris (private communication)