APL Tutorial

⍝ Shortest path length matrix from weighted adjacency matrix Y, using Floyd-Warshall
⍝ (taken from aplcart.info)
(⊃⍳⍤≢(⊢⌊⌷⍤1∘.+⌷)/⍤,⊂)Y

1           ⍝ shape: [1]
1 2 3 4 5 6 ⍝ shape: [6]
1 (2 3 4) 5 ⍝ shape: [3]
(1 2) (3 4) ⍝ shape: [2]
'a' 'b' 'c' ⍝ shape: [3]
'abc'       ⍝ shape: [3]
'a' 2 (3 4) ⍝ shape: [3]

⍳9                ⍝ returns: 1 2 3 4 5 6 7 8 9 (ints from 1 to 9)
99 98 97 96 95⍳98 ⍝ returns: 2 (index of 98 in 99 98 97 96 95)

⍝ more functions

⍝ + (monadic: identity, dyadic: plus)
+3          ⍝ 3
+3 4 5      ⍝ 3 4 5
3+4         ⍝ 7
3+4 5 6     ⍝ 7 8 9
3 4 5+6 7 8 ⍝ 9 11 13

⍝ - (monadic: negate, dyadic: minus)
-3          ⍝ ¯3
-3 4 5      ⍝ ¯3 ¯4 ¯5
3-4         ⍝ ¯1
3-4 5 6     ⍝ ¯1 ¯2 ¯3
3 4 5-6 7 8 ⍝ ¯3 ¯3 ¯3

⍝ × (monadic: direction, dyadic: multiply)
×3          ⍝ 1
×3 ¯4 ¯5    ⍝ 1 ¯1 ¯1
3×4         ⍝ 12
3×4 5 6     ⍝ 12 15 18
3 4 5×6 7 8 ⍝ 18 28 40

⍝ ÷ (monadic: inverse, dyadic: divide)
÷3          ⍝ 0.3333333333
÷3 4 5      ⍝ 0.3333333333 0.25 0.2
3÷4         ⍝ 0.75
3÷4 5 6     ⍝ 0.75 0.6 0.5
3 4 5÷6 7 8 ⍝ 0.5 0.5714285714 0.625

⍝ ⍴ (monadic: shape, dyadic: reshape)
⍴1
⍝ 1

⍴1 2 3
⍝ 3

2 2⍴1 2 3 4
⍝ 1 2
⍝ 3 4

3 3 3⍴(⍳100)
⍝  1  2  3
⍝  4  5  6
⍝  7  8  9
⍝
⍝ 10 11 12
⍝ 13 14 15
⍝ 16 17 18
⍝
⍝ 19 20 21
⍝ 22 23 24
⍝ 25 26 27

⍴(3 3 3⍴(⍳100))
⍝ 3 3 3

⍝ / ("reduce") is a monadic operator
+/                 ⍝ the value of this expression (the result of the application of / on +)
                   ⍝ is a monadic function (called the "derived function"), a right-fold
                   ⍝ with the given function (+) as the step-function
(+/) 1 2 3 ⍝ 6

⍝ ⍨ ("selfie") is a monadic operator
1 2 3⍨             ⍝ when given an array as the argument, the derived functions
                   ⍝ (which, for selfie, can be either monadic and dyadic)
                   ⍝ discard their arguments and return the original argument to selfie
(1 2 3⍨)4 5 6      ⍝ 1 2 3
4 5 6(1 2 3⍨)7 8 9 ⍝ 1 2 3
÷⍨                 ⍝ when given a dyadic function as the argument, the derived functions return:
                   ⍝ monadic: the function (selfie's arg) applied with the derived function's
                   ⍝          argument on both sides
(÷⍨)3              ⍝ 1 (the result of 3÷3)
                   ⍝ dyadic: the function (selfie's arg) applied with the derived function's
                   ⍝         arguments, swapped in order (left becomes right, right becomes left)
3(÷⍨)1             ⍝ 0.3333333333 (the result of 1÷3)


⍝ ∘ is a dyadic operator
-∘-                ⍝ when both arguments are functions (let's call them f and g, respectively)
                   ⍝ the derived functions are monadic: f(gY), dyadic: Xf(gY)
                   ⍝ where X and Y are the left and right arguments to the derived function
(-∘÷)2             ⍝ ¯0.5 (the result of -(÷2))
6(÷∘-)2            ⍝ ¯3 (the result of 6÷(-2))
                   ⍝ up to one of the arguments to ∘ can be an array (the other must be a function)
1∘1                ⍝ SYTNAX ERROR (when derived function is applied)
                   ⍝ when an argument is an array, the other must be a dyadic function
                   ⍝ the derived function is monadic: it is the dyadic function
                   ⍝ curried with the array on the respective side
÷∘2                ⍝ "divide by two"
(÷∘2)3             ⍝ 1.5
2∘÷                ⍝ "two divided by..."
(2∘÷)3             ⍝ 0.6666666667

plus ← +
reduce ← /
iota ← ⍳
six ← 6
iota_six ← iota six

plus reduce iota six ⍝ 21
plus reduce iota_six ⍝ 21

f ← {2 × ⍵}             ⍝ ⍵ is the right argument
g ← {⍺ × ⍵}             ⍝ ⍺ is the left argument

f 3                     ⍝ 6
{2 × ⍵} 3               ⍝ 6
3 g 3                   ⍝ 9
3 {⍺ × ⍵} 3             ⍝ 9
3 {2 × ⍵} 3             ⍝ 6 (all dfns are ambivalent, so, unused arguments (⍺ in this case) are ignored)

fib ← {
    ⍵ ≤ 1 : 0           ⍝ ':' is used to return early - "if ⍵ ≤ 1, then return 0"
    ⍵ = 2 : 1
    (∇ ⍵ - 1) + ∇ ⍵ - 2 ⍝ '∇' refers to the current function ("fib" in this case)
}                       ⍝ (using 'fib' here would have the same effect)

fib 1                   ⍝ 0
fib 2                   ⍝ 1
fib 3                   ⍝ 1
fib 4                   ⍝ 2
fib 5                   ⍝ 3

⍝ redundant wrapper for ÷ (same behavior as div ← ÷)
div ← {
    ⍺ ← 1 ⍝ default left argument (used if no left argument is supplied)
    ⍺ ÷ ⍵
}

3 div 2 ⍝ 1.5
div 2   ⍝ 0.5

custom_fib ← {      ⍝ arguments are the starting values of the sequence
    ⍵ ≤ 1 : ⍺⍺
    ⍵ = 2 : ⍵⍵
    (∇ ⍵ - 1) + ∇ ⍵ - 2
}

(0 custom_fib 1) 1  ⍝ 0
(0 custom_fib 1) 2  ⍝ 1
(0 custom_fib 1) 3  ⍝ 1
(0 custom_fib 1) 4  ⍝ 2
(0 custom_fib 1) 5  ⍝ 3

(5 custom_fib 9) 1  ⍝ 5
(5 custom_fib 9) 2  ⍝ 9
(5 custom_fib 9) 3  ⍝ 14
(5 custom_fib 9) 4  ⍝ 23
(5 custom_fib 9) 5  ⍝ 37

custom_fib2 ← {     ⍝ left arg (⍺⍺) is initial array, right arg (⍵⍵) is combination function
    ⍵ ≤ ≢⍺⍺ : ⍺⍺[⍵] ⍝ ≢ is tally (first element of the shape of the array (length, in this case))
    (∇ ⍵ - 1) ⍵⍵ ∇ ⍵ - 2
}

(1 2 custom_fib2 ×) 1 ⍝ 1
(1 2 custom_fib2 ×) 2 ⍝ 2
(1 2 custom_fib2 ×) 3 ⍝ 2
(1 2 custom_fib2 ×) 4 ⍝ 4
(1 2 custom_fib2 ×) 5 ⍝ 8

⍝ pow (taken from https://dyalog.com/uploads/documents/Papers/dfns.pdf)
pow ← {                     ⍝ ⍺⍺ is the number of times to apply ⍵⍵ on ⍵
    ⍺⍺ = 0 : ⍵
    (⍺⍺ - 1) ∇∇ ⍵⍵ ⍵⍵ ⍵     ⍝ apply ⍵⍵ once, then recursively apply pow with (⍺⍺ - 1) and ⍵⍵
}

(0 pow (+∘1)) 5             ⍝ 5
(1 pow (+∘1)) 5             ⍝ 6
(2 pow (+∘1)) 5             ⍝ 7
(3 pow (+∘1)) 5             ⍝ 8

⍝ Shortest path length matrix from weighted adjacency matrix Y, using Floyd-Warshall
⍝ (taken from aplcart.info)
(⊃⍳⍤≢(⊢⌊⌷⍤1∘.+⌷)/⍤,⊂)Y

⍝ this is a train (in parenthesis) being applied to the matrix Y
⍝ (⍤), (∘.), and (/) are operators (dyadic, monadic, and monadic, resp.)
⍝ (this may be easy to tell from the syntax highlighting)
⍝ but all other glyphs in the train are functions
⍝ add parenthesis to show the evaluation of the operators:
(⊃(⍳⍤≢)(((⊢⌊(⌷⍤1)(∘.+)⌷)/)⍤,)⊂)
⍝ add spaces between functions:
( ⊃ (⍳⍤≢) (((⊢⌊(⌷⍤1)(∘.+)⌷)/)⍤,) ⊂)
⍝ ^ ^^^^^ ^^^^^^^^^^^^^^^^^^^^^  ^
⍝ 1   2             3            4
⍝ we have four functions, so this is a 4-train
⍝ 4 is even, so the root is an atop
⍝ so the top of the tree looks like this
⍝ ┌──┴──┐
⍝ ⊃ ┌───┼─┐
⍝   ⍤   ⍤ ⊂
⍝  ┌┴┐  |
⍝  ⍳ ≢ ...

⍝ use the same process to find the tree for function (3):
((⊢⌊(⌷⍤1)(∘.+)⌷)/)⍤, ⍝ function 3 is a derived function from the dyadic operator ⍤.
⍝    ⍤
⍝  ┌─┴─┐
⍝ ...  ,

⍝ find the tree for the left-hand-side of ⍤:
(⊢⌊(⌷⍤1)(∘.+)⌷)/     ⍝ derived function from the monadic operator /.
⍝    /
⍝  ┌─┘
⍝ ...

⍝ left-hand-side of /:
(⊢⌊(⌷⍤1)(∘.+)⌷)
(⊢ ⌊ (⌷⍤1) (∘.+) ⌷)  ⍝ spaces between the functions
⍝ this is a 5-train; 5 is odd, so the root is a fork, and the resulting tree is:
⍝ ┌─┼─────┐
⍝ ⊢ ⌊ ┌───┼─┐
⍝     ⍤   . ⌷
⍝    ┌┴┐ ┌┴┐
⍝    ⌷ 1 ∘ +

⍝ parens to show grouping of forks and atops
( ⊃ ((⍳⍤≢) (((⊢ ⌊ ((⌷⍤1) (∘.+) ⌷))/)⍤,) ⊂) )Y

⍝ the operator ⍤, when applied to functions, is "atop", and has
⍝ identical behavior to the "atop" constructions used in trains
⍝ the original tree is equivalent to
⍝ ┌──┴──┐
⍝ ⊃ ┌───┼──┐
⍝  ┌┴┐ ┌┴┐ ⊂
⍝  ⍳ ≢ / ,
⍝    ┌─┘
⍝  ┌─┼─────┐
⍝  ⊢ ⌊ ┌───┼─┐
⍝      ⍤   . ⌷
⍝     ┌┴┐ ┌┴┐
⍝     ⌷ 1 ∘ +

⍝ reducing (f⍤g) => (fg) in the expression yields an equivalent result
( ⊃ ((⍳≢) (((⊢ ⌊ ((⌷⍤1) (∘.+) ⌷))/),) ⊂) )Y

⍝ note that the remaining ⍤ has 1 as a a right argument;
⍝ 1 is not function, so ⍤ is not atop in this case

⍝ walking through the recursive evaluation of the derived function may
⍝ be a little excessive, but we can use the generalization of the behavior from the
⍝ above examples: apply the argument (Y) recursively to the right ascendants of atops
⍝ and the left and right descendants of forks:
⍝ ┌──┴───┐
⍝ ⊃ ┌────┼──┐         (*)
⍝  ┌┴┐  ┌┴┐ ⊂Y
⍝  ⍳ ≢Y / ,
⍝     ┌─┘
⍝   ┌─┼─────┐
⍝   ⊢ ⌊ ┌───┼─┐
⍝       ⍤   . ⌷
⍝      ┌┴┐ ┌┴┐
⍝      ⌷ 1 ∘ +
⊃ ((⍳≢Y) (((⊢ ⌊ ((⌷⍤1) (∘.+) ⌷))/),) (⊂Y))
⍝         ^^^^^^^^^^^^^^^^^^^^^^^^^

⍝ note that the middle child of the highest fork (*) isn't applied on any arguments
⍝ (it's used as the dyadic function to combine the left and right children)
⍝ let's abstract this away for now; we'll refer to this function as f
f ← ((⊢ ⌊ ((⌷⍤1) (∘.+) ⌷))/),
⊃ ((⍳≢Y) f (⊂Y))

⍝ ┌──┴──┐
⍝ ⊃ ┌───┼──┐
⍝  ┌┴┐  f  ⊂Y
⍝  ⍳ ≢Y

⍝ monadic ⊃: "first" - returns the first element of the given array, "unboxing" it if it is a "scalar-array"
⍝ monadic ⊂: "enclose" - "boxes" an array (turning it into a "scalar-array", so it can be an element of another array)
⍝ monadic ≢: "tally" - returns the number of "major cells" in an array - this is the first number of the shape
⍝ monadic ⍳: "index generator" - (when given a scalar); returns an array of numbers from 1 to the argument (inclusive)

⍝ it's relatively easy to see what this outer tree does: it returns the first
⍝ element of the array returned by f, when applied on (the numbers from 1 to ≢Y)
⍝ on the left, and (boxed Y) on the right

⍝ here's f:
⍝     ┌┴┐
⍝     / ,
⍝   ┌─┘
⍝ ┌─┼─────┐
⍝ ⊢ ⌊ ┌───┼─┐
⍝     ⍤   . ⌷
⍝    ┌┴┐ ┌┴┐
⍝    ⌷ 1 ∘ +

⍝ we know that f will be applied dyadically, so we can repeat the same process as above

f ← { ⍺(((⊢ ⌊ ((⌷⍤1) (∘.+) ⌷))/),)⍵ }
⍝     ┌┴─┐
⍝     / ⍺,⍵
⍝   ┌─┘
⍝ ┌─┼─────┐
⍝ ⊢ ⌊ ┌───┼─┐
⍝     ⍤   . ⌷
⍝    ┌┴┐ ┌┴┐
⍝    ⌷ 1 ∘ +

f ← { ((⊢ ⌊ ((⌷⍤1) (∘.+) ⌷))/) ⍺,⍵ }
⍝      ^^^^^^^^^^^^^^^^^^^^^

⍝ again, we have a relatively large function tree on the left that has no arguments.
⍝ let's abstract it below the / operator

g ← { ⍺(⊢ ⌊ ((⌷⍤1) (∘.+) ⌷))⍵ }
f ← { (g/) ⍺,⍵ }

⍝   ┌┴─┐
⍝   / ⍺,⍵
⍝ ┌─┘
⍝ g

⍝ dyadic ,: "catenate": joins two arrays along their "trailing axis" (the last number of their shape)

⍝ f takes its left and right arguments, combines them into an array,
⍝ and returns that array after reducing it with g
⍝ therefore the top-level code catenates (⍳≢Y) and (⊂Y) (appends a boxed Y to the end of
⍝ the array [1...(≢Y)]), reduces that with g, and returns the first element of the result

⍝ here's g:
⍝ ┌─┼─────┐
⍝ ⊢ ⌊ ┌───┼─┐
⍝     ⍤   . ⌷
⍝    ┌┴┐ ┌┴┐
⍝    ⌷ 1 ∘ +

⍝ again, apply recursive reductions

⍝ ┌───┼─────┐
⍝ ⍺⊢⍵ ⌊ ┌───┼──┐
⍝      ⍺⍤⍵  . ⍺⌷⍵
⍝      ┌┴┐ ┌┴┐
⍝      ⌷ 1 ∘ +

g ← { (⍺⊢⍵) ⌊ (⍺(⌷⍤1)⍵) (∘.+) (⍺⌷⍵) }

⍝ dyadic ⊢: "right": returns the right argument
⍝ dyadic ⌊: (element-wise) minimum (of the two arguments)
⍝ dyadic ⌷: "index": the ⍵'th element of ⍺ (when ⍵ is a scalar)

⍝ monadic ∘.: "outer product": the derived function returns a "multiplication-table" between the
⍝                              two array arguments (with the given function instead of multiplication)

g ← { (⍺⊢⍵) ⌊ (⍺(⌷⍤1)⍵) (∘.+) (⍺⌷⍵) }
⍝ the above g is equivalent to (remove "⍺⊢")
g ← { ⍵ ⌊ (⍺(⌷⍤1)⍵) (∘.+) (⍺⌷⍵) }

⍝ ⍤ (when applied to a function (on the left) and an array
⍝ (on the right)) is "rank": it is a specialized for-each;
⍝ the left argument is the function to apply to each element (or pair of
⍝ elements, if applied dyadically), and the right argument is *how many trailing axes
⍝ the for-each ignores* during iteration. The derived function is rank-polymorphic,
⍝ so the shapes of the arguments (after ignoring the given number of axes)
⍝ doesn't need to match if one of the two is a scalar

⍝ recall that g is being used to reduce ((⍳≢Y),(⊂Y))
⍝ since / is a right-fold, g is first called with (⍺ ← ≢Y) and (⍵ ← Y)
⍝ thus ⍺ has shape [1], and ⍵ has the same shape as Y (assume Y is 2d)

⍝ if ⍺ is a scalar and ⍵ is a rank-2 (2d) matrix, (⍺(⌷⍤1)⍵)
⍝ applies ⌷ on ⍺ and each *row* of ⍵ (the column axis is ignored)
⍝ (the trailing axis of ⍺ is also ignored, but it remains a scalar)
⍝ this expression yields the ⍺'th column of ⍵

⍝ thus (⍺(⌷⍤1)⍵) (∘.+) (⍺⌷⍵) is an addition-table between the ⍺'th column
⍝ of ⍵ and the ⍺'th row of ⍵, so result[i, j] = ⍵[i, ⍺] + ⍵[⍺, j]
⍝ and, in general (in pseudocode/math notation),
⍝ g maps ⍵[i, j] to min(⍵[i, j], ⍵[i, ⍺] + ⍵[⍺, j])
⍝ this exactly matches the bellman-equation for Floyd-Warshall (with ⍵ instead of dp)

⍝ it follows that ⍵[i, j] = dp[i, j, k] after the k'th application of g
⍝ when the reduction (/g) is complete, then the boxed shortest path-length
⍝ matrix remains; it is unboxed and returned by the left argument of the highest atop (⊃)