Day 5
-----

0.  compositions
1.  adverbs
2.  each
3.  each-left and each-right
4.  over
5.  scan
6.  examples combining ' / \ /: and \:
7.  prior
8.  converging selection and multi-column sorting
9.  pointer-chasing with vector-scan and trees
10. state-transition with matrix-scan, -over, and -prior
11. scatter-indexing
12. a simple application: t.k

0. compositions

the simplest compositions are expressions like:

    2+

so

    (2+)3
  5

compositions can be formed from more complex expressions:

take any expression:

    a+b*(c-d)%e

remove the last element:

    a+b*(c-d)%

if the last element in the resulting expression is a dyadic verb, then that expression can be applied to an argument:

    a:1+b:1+c:1+d:1+e:10

    a+b*(c-d)%e
  15.3

    f:a+b*(c-d)%

    f e
  15.3

suppose the last verb in the original expression is a monadic verb:

    a+b*(c-d)%-e

then replace the last element with : s.t. the final verb is an explicit monad:

    a+b*(c-d)%-e
  12.7

    g:a+b*(c-d)%-:

    g e
  12.7

suppose the last element is a lambda:

    k:{-x}

    a+b*(c-d)%k e
  12.7

    h:a+b*(c-d)%k@

    h e
  12.7

1. adverbs

nouns are things:                         larry

verbs are actions and predicates:

intransitive verbs have the form v n:     moe laughed

transitive verbs have the form n v n:     larry punched curly

adverbs modify verbs to make verbs:       moe laughed sarcastically

we say that an adverb derives a verb from a verb.

there are six adverbs:

    '       each
    \:      each-left
    /:      each-right
    /       over
    \       scan
    ':      prior

    each:         f'b     a f'b    f'[a;b;..]
    over:         f/b     a f/b    f/[a;b;..]
    scan:         f\b     a f\b    f\[a;b;..]
    each-right    a f/:b
    each-left     a f\:b
    prior         f':a a  a f':b

adverbs are abstractions from common patterns of iteration.

a+b generalizes all possible ways of adding comformable objects:

    atom+atom -> atom
    atom+list -> list
    list+atom -> list
    list+list -> list

2. each.

atomic functions pervade lists: x+y*z

'each' is used to pervade non-atomic functions.

    f'x
    f''x
    f'''x

    a f'b
    f'[a;b;c;d]

    the general form:  f'[x;y;..;z]

all list arguments must have the same count

atomic arguments are extended to the count of the first list (if any)

    f'[10 20 30;40;50 60 70]

3. each-left and each-right.

    a f\:b  =  f[b]'a   / hold the right argument constant and iterate over the left argument

    a f/:b  =  f[a]'b   / hold the left argument constant and iterate over the right argument

4. over.

    valence > 1

    the general form:  f/[x;y;..;z]

    x is a blob
    y .. z are lists count n

    f/[x;y;..;z] = x:f[x;y 0;..;z 0]
                   x:f[x;y 1;..;z 1]
                   :
                   x:f[x;y n;..;z n]

alternatively:

    f[..f[f[x;y 0;..;y n];y 1;..;y 1]..;x n;..;y n]

example:

    f:{x+y*z}
    f/[100;10 20 30;40 50 60]
  3300

valence = 1

    the general form:  f/x

iterate f on x until the result is the same twice in a row or matches the initial value.

    (0|-1+)/10
  0

use \ to see intermediate results:

    (\1!)/"abc"
  "bca"
  "cab"
  "abc"
  "cab"

valence = 2 has an optional syntactic form:

    +/[2;1 2 3]     / standard form
  8

    2+/1 2 3        / initial argument to the left of +/
  8

    +/2 1 2 3       / use the first element as the initial argument
  8

"raze": join a list of lists and atoms:

    ,/("abc";"defg";"x")
  "abcdefgx"

    +/3 7 18 4 9

should NOT be thought of as:

    3+7+18+4+9

but rather as:

    (((3+7)+18)+4)+9

in other words, +/ derives a verb which, when applied to 3 7 18 4 9, gives the behavior:

    (((3+7)+18)+4)+9

in other words, f/x groups from the left.

    -/10 4 7 3 8
  -12

    (((10-4)-7)-3)-8
  -12

    10-4-7-3-8
  18

this is clearer when / is used with an initial value:

    8-/10 4 7 3 8
  -24

or in bracket form:

    -/[8;10 4 7 3 8]
  -24

start with 8.
subtract 10.
take the result and subtract 4.
and so forth.

5. scan.

scan syntax is just like over:

    valence > 1: f\[x;y;..z]
    valence = 1: f\x
    valence = 2: f\[x;y], x f\y, f\x

think of f/x as returning the last of f\x, or as f\x as returning all the intermediate results of f/x.

    +/!3
  2

    +\!3
  0 1 2

    (1!)/"abc"
  "cab"

    (1!)\"abc"
  ("abc"
   "bca"
   "cab")

boolean scans:

    &\1 1 1 0 1 0 1     / turn off all 1's after the first 0
  1 1 1 0 0 0 0

6. examples combining ' / \ /: and \:

left-justify a string:

    {(+/&\x=" ")_ x}"    strip leading blanks"
  "strip leading blanks"

    {(+/&\x=" ")!x}"    rotate leading blanks"
  "rotate leading blanks    "

parity-check = find quoted substrings:

    {(~=)\x="'"}"this 'has quoted' substrings 'embedded' in it"
  0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

    {x@&(~=)\x="'"}"this 'has quoted' substrings 'embedded' in it"
  "'has quoted'embedded"

check for unbalanced parentheses:

    unb:{~(*|=/b)&~|/</b:+\'x=/:"()"}

    a:"this(has(missing)right paren"
    b:"this(has(missing)left))paren"
    c:"this(has(balanced)parens)"

    unb a
  1

    unb b
  1

    unb c
  0

the common patterns:

    x f\:/:y
    x f/:\:y

apply f between each x and each y.

    1 2 3,\:/:4 5
  ((1 4
    2 4
    3 4)
   (1 5
    2 5
    3 5))

    1 2 3,/:\:4 5
  ((1 4
    1 5)
   (2 4
    2 5)
   (3 4
    3 5))

we can use each-left-each-right to generate combinations:

    comb:(,/,/:\:)/     / "(raze join each-left each-right)over"

    comb(1 2;3 4 5)
  (1 3
   1 4
   1 5
   2 3
   2 4
   2 5)

we can define =x (group):

    a:"abbacadddbbb"

    a(&=)/:?a
  (0 3 5
   1 2 9 10 11
   ,4
   6 7 8)

    a a(&=)/:?a
  ("aaa"
   "bbbbb"
   ,"c"
   "ddd")

    a:1000000#a

    \t =a
  6

    \t a(&=)/:?a
  15

7. prior

f has valence 2

f':x evaluates f on overlapping pairs:  (f[x 1;x 0];f[x 2;x 1];..;f[x n+1;x n])

we can use -': to define "deltas":

    -':10 4 8 3 2 9 6
  -6 4 -5 -1 7 -3       / i.e. (4-10;8-4;3-8;2-3;9-2;6-9)

provide an initial value:

    3-':10 4 8 3 2 9 6
  3 -6 4 -5 -1 7 -3

delete extra blanks

    deb:{x@&~0&':" "=x}

    deb"  this has     extra    embedded  blanks    "
  " this has extra embedded blanks "


8.  converging selection and multi-column sorting

define a table with descending g within ascending f:

    t.f:10 10 10 10 20 20 30 30 30
    t.g:9 8 7 6 20 19 7 6 5
    t.h:9 _draw 5

now define the index function:

    index:{[t;i]@[t;_n;@[;i]]}

and randomly scramble the order of t as u:

    u:index[t]9_draw-9

    u
  .((`f
     30 10 30 20 10 30 20 10 10
     )
    (`g
     6 9 5 20 7 7 19 6 8
     )
    (`h
     3 0 1 4 3 3 4 1 4
     ))

now define the xyzx and order functions:

    xyzx:{x y z x}
    order:{[t;f;o]xyzx/[_n;o;t f]}

and sort u back to the original order of t:  g descending within f ascending:

    i:order[u;`g`f](>:;<:)

    i
  1 8 4 7 3 6 5 0 2

    t~index[u]i

we can use xyzx to perform converging selection on a table:  selects within selects.

here is t again:

    t
  .((`f
     10 10 10 10 20 20 30 30 30
     )
    (`g
     9 8 7 6 20 19 7 6 5
     )
    (`h
     0 4 3 1 4 4 3 3 1
     ))

    30>t.f
  1 1 1 1 1 1 0 0 0
    8<t.g
  1 0 0 0 1 1 0 0 0

  i.e.

    (30>t.f)&8<t.g
  1 0 0 0 1 1 0 0 0

but we would like to evaluate 8<t.g *after* we've cut down the number of searches by first evaluating 30>t.f.  in other words, search for 8<t.g *within* 30>t.f.

first, rename the order function:

    select:order

then:

    i:select[t;`f`g](&30>;&8<)

    i
  0 4 5

    index[t]i
  .((`f
     10 20 20
     )
    (`g
     9 20 19
     )
    (`h
     0 4 4
     ))

we can see the intermediate selections (or orderings) by redefining select as a scan:

    selects:{[t;f;o]xyzx\[_n;o;t f]}

then:

    i:selects[t;`f`g](&30>;&8<)
    i
  (
   0 1 2 3 4 5
   0 4 5)

so successive selections from t:

    t index/:i
  (.((`f
      10 10 10 10 20 20 30 30 30
      )
     (`g
      9 8 7 6 20 19 7 6 5
      )
     (`h
      0 4 3 1 4 4 3 3 1
      ))
   .((`f
      10 10 10 10 20 20
      )
     (`g
      9 8 7 6 20 19
      )
     (`h
      0 4 3 1 4 4
      ))
   .((`f
      10 20 20
      )
     (`g
      9 20 19
      )
     (`h
      0 4 4
      )))

9. pointer-chasing with vector-scan and trees

let t be the tree with root 0 and nodes 1-9:

    0
     1
     2
      3
       4
       5
      6
       7
       8
       9

and let the leaves 1 4 5 7 8 and 9 have values 10 40 50 70 80 and 90:

   0
     1    - 10
     2
      3
       4  - 40
       5  - 50
      6
       7  - 70
       8  - 80
       9  - 90

problem:  sum the values at each node in the tree.

first, represent the tree as a parent-vector:

    p:0 0 0 2 3 3 3 6 6 6

thus:  p[0] says that 0 has 0 as parent
       p[1] says that 1 has 0 as parent
       p[2] says that 2 has 0 as parent
       p[3] says that 3 has 2 as parent

and so forth.

indexing:  p[i] is the parent of i.

repeated indexing finds the root of i.

      p 9
    6
      p p 9
    3
      p p p 9
    2
      p p p p 9
    0

use converging-over to reach the root from any node, and use converging-scan to compute the ancestral:

      p/9
    0
      p\9
    9 6 3 2 0

use converging-over-each to compute the ancestral of every node:

      p\'!#p
    (,0
     1 0
     2 0
     3 2 0
     4 3 2 0
     5 3 2 0
     6 3 2 0
     7 6 3 2 0
     8 6 3 2 0
     9 6 3 2 0)

not let v be the value at each node:

      v:0 10 0 0 40 50 0 70 80 90

define the initial state of the summation:

      &#p
    0 0 0 0 0 0 0 0 0

and perform the summation:

      @[&#p;p\'!#p;+;v]
    340 10 330 90 40 50 240 70 80 90

10. state-transition with matrix-scan, -over, and -prior

a finite-state automaton is a machine which has a set of states S0 S1 .. and an input stream I.  the idea is that the machine starts out in state S0 with input I 0.  the machine has a set of state-transition rules, which say:  when in state Si and reading input x move to state Sj and read the next input.  for example, suppose M has three states S0, S1, and S2, and the transition rules are:

  S0:"a":S1
  S0:"b":S1
  S0:"c":S3

  S1:"a":S0
  S1:"b":S1
  S1:"c":S2

  S2:"a":S0
  S2:"b":S1
  S2:"c":S2

i.e. x:y:z says "when in state x if you see a y then go to state z and read the next input."

M starts in S0.  when it sees an "a" or a "b" it moves to S1.  when it sees a "c" it moves to S2.  if M is in S1 or S2 then it moves to S0, S1, S2 if it sees an "a", a "b", or a "c".

we can represent M as a matrix m:

      m:(1 1 2;0 1 2;0 1 2)

and we should encode the input tape I as an integer vector:

      I:"aaabbbbaaccbcc"
      i:"abc"?/:I

then:

      0 m\i
    0 1 0 1 1 1 1 1 0 1 2 2 1 2 2

that is,

  start in S0
  see an "a", so go to S1
  see an "a", so go to S0
  see an "a", so go to S1
  see four "b"'s so stay in S1 until you
  see an "a", so go to S0

and so forth.

matrix-scan (or "mscan") is the scan-form of matrix-over:

    0 m/i
  2

matrix-prior will calculate the state-transitions for each pair of values in the input

i[1]->i[0]
i[2]->i[1]
i[3]->i[2]
i[4]->i[3]
and so forth.

This operation is useful when we have overlapping pairs of inputs and states, or we can use it with just 1 input and 1 starting state.

      i
    0 0 0 1 0 1 1 0 0 0 1 0 1 0
      m':i
    0 0 0 1 0 2 1 0 0 0 1 0 1
      m':0 2
    ,2
      m':1 2
    ,2

(thanks to eusebio for this explanation and example.)

11. scatter-indexing

the left argument specifies where we are selecting from, and the right argument specifies the coordinates of the items being selected

when selecting a single element, scatter selection and indexing are the same

      ((0 1 2);(3 4 5);(6 7 8))[1;2]
    5

      ((0 1 2);(3 4 5);(6 7 8))'[1;2]
    5

the difference is when we want to select more than one element.  indexing would give us a subarray:

      ((0 1 2);(3 4 5);(6 7 8))[1 2;2 0]
    (5 3
     8 6)

and scatter selection would give us just the selected arguments:

      ((0 1 2);(3 4 5);(6 7 8))'[1 2;2 0]
    5 6

or

      ("abc";"def";"ghi")'[0 1 0;0 2 1]
    "afb"

scatter selection is not restricted to 2D matrices.  it can be used for higher dimension arrays (tensors), and the valence of the scatter selection will depend on the dimensions of the array, e.g. for a 3D array we should provide 3 vectors of coordinates:

      (((0 1 2);(3 4 5);(6 7 8));((10 11 12);(13 14 15);(16 17 18));((20 21 22);(23 24 25);(26 27 28)))'[0 1;0 2;0 0]
    0 16

or

      (4#,("abc";"def";"ghi"))'[0 1 0;0 2 1;0 0 0]
    "agd"

if we specify fewer vectors of coordinates than the dimensions of the array, then the array will be re-interpreted as the appropriate array of arrays (e.g., as a matrix of sub-vectors or a matrix of sub-matrices)

      (((0 1 2);(3 4 5);(6 7 8));((10 11 12);(13 14 15);(16 17 18));((20 21 22);(23 24 25);(26 27 28)))'[0 1;0 2]
    (0 1 2
     16 17 18)

or

      (4#,("abc";"def";"ghi"))'[0 1 0;0 2 1]
    ("abc"
     "ghi"
     "def")

an example with a matrix of sub-matrices

      (3#,(((0 1 2);(3 4 5);(6 7 8));((10 11 12);(13 14 15);(16 17 18));((20 21 22);(23 24 25);(26 27 28))))'[0 1;0 2]
    ((0 1 2
      3 4 5
      6 7 8)
     (20 21 22
      23 24 25
      26 27 28))

There is a limit however: the minimum number of arguments is two lists.  if we try to go down to a single list it will result in a projection

      (((0 1 2);(3 4 5);(6 7 8));((10 11 12);(13 14 15);(16 17 18));((20 21 22);(23 24 25);(26 27 28)))'[0 1]
    ((0 1 2
      3 4 5
      6 7 8)
     (10 11 12
      13 14 15
      16 17 18)
     (20 21 22
      23 24 25
      26 27 28))'[0 1]

as far as anyone at 1010 knows, scatter-indexing is not used in production code.

again, thanks to eusebio for organizing this explanation.

12. a simple application: t.k

table[f;n;m]    returns a table of cardinality n with cols f whose values are drawn from m
insert[t;d]     returns t with d appended
update[t;f;i;d] returns t with cols f updated at i with d
delete[t;i]     returns t with rows i deleted
select[t;i]     returns t restricted to rows i
project[t;f;g]  returns t with cols g of t projected to f
group[t;k;f;o]  returns t with keys k and aggregations o[1]f[1] ... o[n]f[n]
where[t;f;o]    returns indices of rows where o[1]f[1] and ... and o[n]f[n]
order[t;f;o]    returns indices of rows sorted by o[1]f[1] within ... within o[n]f[n]
link[t;u;k;l]   returns the join of the data table t with the key table u