This paper describes the function-array datatype, an extension to K. A function-array is a function with non-null shape.
Lists can be transformed into function-arrays and vice-versa. K has arrays with shape and functions with valence. Functions are atoms, having shape !0. Lists can be indexed - a[i;j;k] - and functions can be applied - f[x;y;z] - but lists can't be transformed into functions or vice-versa, except via the intermediate representation of strings and the execute operation.
K has atoms and lists. K atoms are integer, float, character, symbol, dictionary, nil, or lambda. lambdas are defined functions:
{[a;b;c]a+b-c}
There is a single empty list:
()
Vectors are homogenous lists of atoms of type integer, float, character, and symbol. Each of these types supports its own vector notation:
1 2 3 1.2 3.4 5.6 "abc" `one`two`three
Corresponding to each vector-type, there is an empty vector:
!0 0#0. "" 0#`
Heterogenous lists are formed with parentheses and ;:
(1;2.2;("abc";`d`e`f;;{x+y}))
A dictionary is an atom constructed from a list of symbol-value pairs or symbol-value-dictionary (or null) triples:
.((`first;10);(`second;20.345);(`third;"abc"))
Dictionaries can be deconstructed into lists of symbol-value-dictionary (or null) triples:
.((`first;10);(`second;20.345);(`third;"abc")) ((`first;10;) (`second;20.345;) (`third;"abc";))
K data has shape. The shape of an object d is an integer vector s which describes the regular structure of d. Intuitively, each element s describes as much of the structure of the corresponding parts of d as can be summarized in a single integer. The count of s is called the rank of d. The rank of an object is a measure of its regularity.
The shape of an atom is !0. Atoms have no parts, hence there is no structure to describe:
^17 !0 ^"a" !0
The rank of an atom is 0:
#^17 0
Since a vector is a homogenous list of atoms, vector shape is simply the enlisted count. We do not have to check whether the parts of a vector are structurally similar - we know that they are:
^10 20 30 ,3 ^"abcdef" ,6
The rank of a vector is 1.
The shape of an empty list -- general or vector -- is ,0:
^!0 ,0 ^() ,0
The shape of a non-empty general list is determined recursively. We start by setting s to ,#d. Then we get the shapes of each part of d, and append to s the longest common subsequence among the shapes. For example,
^(1 2 3;4 5 6) 2 3
We set s to ,2. Then we get the shapes of 1 2 3 and 4 5 6. In both cases, the shape is ,3, and the longest common subsequence is ,3. so we append that to s and get 2 3.
^(1 2 3;4 5) ,2
We set s to ,2. Then we get the shapes of 1 2 3 and 4 5, which are ,3 and ,2. The longest common subsequence is !0, so we append that to s and get ,2.
Here are two implementations of the shape algorithm, one depth-first, the other breadth-first:
dshape:{:[~t:4:x;(#x),{(+/&\=/((#x)&#y)#'(x;y))#x}/_f'x;0>t;#x;!0]}
bshape:{
s:!0
i:0;while[(i=#s)&~|/,//{x'}/[i;@:]x
if[1=#c:?(),i,//{x'}/[i;#:]x;s,:c]
i+:1]
s}
Shape may also be thought of as describing the domain of the indexing function.
For example, an object d of rank r:
d:2 3 4#10*!24 d ((0 10 20 30 40 50 60 70 80 90 100 110) (120 130 140 150 160 170 180 190 200 210 220 230))
d can be indexed:
d[0;1 2;3] 70 110
If index j is in the i-th position of the indexing expression, then every element of ,//j must be a member of !s i. (an elided argument is used to mean "every index along this axis".) If j does not satisfy this requirement, the result is an index error.
d[0;17;1] index error d[0;17;1] ^ >
The number of indexing positions is always equal to the rank of the object: if d has rank r, then d[j1;..;jr] is a valid indexing expression. If too many indices are supplied, the result is a rank error. If too few, the remaining positions are treated as null, i.e. all elements along that axis:
d[0;1 2;3;4] rank error d[0;1 2;3;4] ^ > d[0;1] 40 50 60 70
Indexing is cross-sectional. the result of d[1 2;3 4 5] contains data at positions d[1;3], d[1;4], d[1;5], d[2;3], d[2;4], d[2;5]. The shape of the result of d[1 2;3 4 5] is (^1 2),^3 4 5, i.e. 2 3. If k is a list of the indices of d[k 0;..;k r-1], then the shape of the result is ,/^:'k.
The valence of a function f is the rank of its (possibly infinite) domain D = a X .. X z. Intuitively, it is the maximum number of arguments to which f may be applied.
Since functions are atoms, and it is always a rank error to index an atom, the brackets of indexing can be reused to denote function application. For example, the function f:{[a;b;c]a+b*c} may be applied to three arguments:
f[10;20;30] 610
Application of a function of valence k to more than k arguments results in a valence error:
f[10;20;30;40] valence error f[10;20;30;40] ^ >
The result of applying a function f of valence k to n<k arguments is a function-projection of valence k-n, where the corresponding argument positions of the function are set to constant values, namely those supplied as arguments to the projection.
g:f[10;;30]
g
{[a;b;c]a+b*c}[10;;30]
g[20]
610
h:f[10]
h
{[a;b;c]a+b*c}[10]
h[20;30]
610
The valence of a function is analogous to the rank of an array, but whereas rank is computable as the count of the shape, which in turn is computed by a primitive, valence is neither derived from some more primitive property of functions, nor directly computable by a primitive.
For example, we cannot compute the valence of an arbitrary primitive p, save by looking up p in a table of valences-by-primitive (or analyzing it's name: 5:p). If f is a defined function, then we may be able to compute the valence by analyzing f's argument-list if it has one, or if it doesn't then by counting unassigned occurrences of the variables x, y, and z.
Where v is the valence of primitive p, the order of p is defined to to be the vector 1_-!1+v. Hence the order of + is -1 -2, and that of +: is -1.
We cannot in general say that order is derived from valence (even if we had a primitive for computing that), since we will eventually want to permute the argument-order of an arbitrary function, and have the order of the resulting function carry information about the order of its arguments. But the valence of e.g. commute(+) is the same as that of +, whereas the order of commute(+) is -2 -1, while that of + is -1 -2.
Instead, we will think of the shape ^ primitive as having been extended to deliver the order property of constituent functions:
^(+) -1 -2 ^(+;-) 2 -1 -2
Note that in the case of a single primitive, parentheses are required to first "nominalize" the verb +. The result of (+) is a function-atom, a piece of data.
K shape records the cardinalities of structurally similar subarrays: each element of a shape vector is a count: the number of subarrays of every array at that level. But order is different: the elements of an order vector indicate how incoming arguments are to be mapped to the function's argument-list. So extended shape is a mix of cardinal and ordinal values.
What about defined functions?
Here too, sufficient information must be carried along with function to distinguish e.g. {x+y} from the commute of {x+y}, since the order of the former is -1 -2 and that of the latter -2 -1. At this point, we don't have a functional method for permuting the arguments of either primitives or defined functions; that is, for modifying the order of a function-atom. So we need merely guarantee that order for defined functions is defined correctly for the types of objects we are currently able to construct in K. And here too it suffices to define the order of f as -1_-!1+v. So the order of {x+y} is -1 -2, that of {-x} is -1, and so forth.
What about niladic functions?
Intuitively, it might seem as though the order of a nilad is !0, since a nilad has no arguments, and therefore has valence 0. But as we will see in the next section, this leads to inconsistent results. Fortunately, K nilads are in fact monadic functions. Typically, we apply a nilad to a null argument, written
nilad[]
but we can apply any nilad to any value with identical effect:
nilad 10 20 30
Consequently, we will say that nilads have valence 1 and order ,-1.
What is the shape of a:({x+y};{x+y-z})?
The shape of the first function is -1 -2, and that of the second -1 -2 -3. We will say that the shape of the pair is 2 -1 -2, for the same reason that we say the shape of (!2;!3) is ,2: the unextended shape vector records the longest list of identical counts. The extended shape vector records the longest list of identical counts and argument positions. Note that a[1;10;20;30] is 0, and that a[0;10;20] is 30, since the shape of a[1] is -1 -2 -3 and that of a[0] is -1 -2.
Consider the list:
a:(+;-).
The shape of a is:
^a 2 -1 -2
A pair of function-atoms, each of which has order -1 -2. Since the rank of an object determines the maximum number of indexing positions available in an indexing expression, and the valence of a function determines the maximum number of argument positions available in an application expression, we should expect that
a[i;j;k]
is a valid expression involving a, in which i occupies an indexing position, and j and k occupy argument positions. We should continue to expect that a[i] is a function if i is an atom and not nil, and an array of functions if i is not. But what should we expect the result of a[0;3] to be? Intuitively, we're picking out the first function +, and then applying it to the single argument 3. So we should expect the result to be the monadic function +[3].
What is the order of this result? Since order is analogous to shape, we might expect the answer to be ,-2, but this is impossible. +[3] has valence 1, and its arguments haven't been permuted, so its order should be ,-1. In general, we will say that the order of a function is always a permutation of 1_-!1+v.
Monadic + (+:, "transpose" or "flip") has the following definition: applied to an object of rank greater than 1, it swaps the first two axes. So, if ^x = i,j,.. then ^+x = j,i,.. . What then should be result of transposing a function, say *? Since (*) has shape -1 -2, the result of +(*) should have shape -2 -1. That is, +: applied to a function is commute.
Now consider +a. What should we expect. Since +: swaps the axes of its argument:
^b:+a -1 2 -2
and
^c:+:'+a -1 -2 2
and
^d:++:'a -2 -1 2
Intuitively, c is a function of valence 2. Whatever is supplied as its first argument is mapped to the first arguments of both of its constituents + and -. Whatever is supplied as its second argument is mapped to the second arguments of its constituents. So we should expect:
c[3;7] 10 -4
b is also a function of valence 2, so:
b[3;;7] 10 -4
The arguments of d are reversed, so:
d[3;7] 10 4
We will define function-array extensions to nine structural operations:
+: flip #: count *: first ,: enlist |: reverse # take _ drop ! rotate , join
Now that the shape of an array contains information about both constituent functions and their arrangement, it will be convenient to add a few new terms.
We will refer to the non-negative elements of the shape of an array as the frame of the array, and the negative elements as the order of the array. The dimension of an array is the count of the frame. The valence of an array is the count of the order.
The frame provides information about how many elements there are, and how they are distributed on each dimension. The order tells us how many arguments the function-array takes, and in what order they occur.
count and rank retain their existing meanings, applying to the shape of the array.
As we've seen, flip swaps the first two axes.
^f:+(+;-) / list -> function -1 2 -2 ^+f / function -> list 2 -1 -2 ^+(-) / commute - -2 -1
We will retain the original definition of count as the first of the shape.
^f -1 2 2 #f -1
The shape of the first of a non-function-array a is *1_^a:
a:2 3 4#!24 ^*a 3 4 ^
Since a is a pair of 3 x 4's, each a is a 3 x 4. So *a is a 3 x 4.
The proper extension of first to function-arrays is therefore s _di(0<s:^a)?1:
^t:*(+;-) -1 -2 t~(+) 1enlist turns a function-array into a unit-list:
^f -1 2 -2 ^,f 1 -1 2 -2reverse reverses the shape of the array:
^f -1 2 -2 |f -2 2 -1
take and drop operate on the first of the frame:
^f -1 3 -2 ^1#f -1 1 -2 ^4 5#f -1 4 5 -2 ^2_ f -1 1 -2 ^3_ f -1 0 -2
rotate rotates the shape of the array left (if x&;t0) or right (if x>0):
^f -1 2 -2 ^1!f 2 -2 1 ^-1!f -2 -1 2
join penetrates to the frame of conformable function-arrays:
^a:({x+y%z};{x#!0|y+z})
4 -1 -2 -3
^b:({x+y%z};{x#!0|y+z})
-3 -2 -1 2
^a,b
,2
^a,a
4 -1 -2 -3