Lists are Maps [0]
==================


0. K.

K has atoms, lists, and dictionaries.  

Lists are maps [1].  The list Z of length n is a map from <0 .. n-1>  to the values of Z:

    Z = 10 20 30

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

We can use this insight to simplify K by reducing the number of distinct ideas [2].  I call this variant of K "M".


1. M.

M has atoms and maps.  M-maps comprehend the dictionaries and lists of K.

In both K and 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 ! [3]:

    m)!a
  `a`b`c

and the range using monadic ? [4]:

    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:

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


3. 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 maps, but lists are not dictionaries.  It would be wrong to insist on dictionary semantics for the join 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 [5]:

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.  A list Z is identical to the constructed map (!#Z)!Z [6]:

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

Nick Psaris points out that joining lists in M behaves differently than joining the homonymous dictionaries in q:

    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.


4. 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]}

and is found here:

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

An example M script:

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

Operate it this way:

  q m.k
  \l m.m


5. Reduction to Two Primitives.

M extends and overrides three K primitives:  ! !: and ?:.  But we can merge the behavior of the two monads. 

    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.)

In fact, the new definition of !: serves other uses.  For example, where we want to pass the domain and range of a map to a dyadic function:

    k) f[!x;x[]]

vs

    m) f .!x

Reverse domain and range:

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


6. Notes

[0] This "philosophical" note on K was stimulated by the chapter on _Principia Mathematica_ in Gregory Landini's book _Russell_.  Specifically, his discussion of the different forms of reductionist analysis.  For example, the reduction of heat to molecular motion is an explanation of heat, not a claim that heat doesn't exist, while the logicist reduction of number such as the one carried out by Whitehead and Russell is eliminativist:  numbers may exist but we don't need them to do mathematics.  In that spirit, the work described in this paper is a reduction in the first sense:  K says lists exist, and I say they are maps.

[1] Borror, Jeffrey: _Q For Mortals_ (First Edition, 2006) p.42

[2] My argument 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 have always existed 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 seen to be superfluous.

[3] In K, !<list> is symbolic type.

[4] in K, ?<dict> is a type error and ?<list> is unique.

[5] M-maps are ungrounded.  Since !Z and ?Z are lists, they are also maps.  M-maps are infinitely deep, infinitely wide trees.

[6] 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.  <list>!<dict> is a length error and <dict>!<list> and <dict>!<dict> are type errors.