⍝ Display of function tree:
mean ← ÷∘⍴⍨∘(+/)⍨ ⍝ derived function for average.
mean dft 1 ⍝ narrow (space-frugal) display.
⍨
┌─┘
∘
┌─┴─┐
⍨ /
┌─┘ ┌─┘
∘ +
┌┴┐
÷ ⍴
mean dft 3 ⍝ wide (space-generous) display.
⍨
┌──┘
∘
┌──┴───┐
⍨ /
┌──┘ ┌──┘
∘ +
┌─┴─┐
÷ ⍴
⍕ 1 0 +¨¨¨.× dft¨ 3 ⍝ diagonal vs vertical left operand.
. .
┌─┴─┐ ┌─┴─┐
¨ × ¨ ×
┌──┘ │
¨ ¨
┌──┘ │
¨ ¨
┌──┘ │
+ +
↑∘(÷∘⊂∘(1∘∨)⍨∘(1∘(,⍨∘⊂))⍨) dft 3 ⍝ derived function for rational pair.
∘
┌─┴─┐
↑ ⍨
┌──┘
∘
┌────┴────┐
⍨ ∘
┌──┘ ┌─┴─┐
∘ 1 ∘
┌───┴───┐ ┌─┴─┐
∘ ∘ ⍨ ⊂
┌─┴─┐ ┌─┴─┐ ┌──┘
÷ ⊂ 1 ∨ ,
+.×⍨∘(÷⍨∘⌽∘(×\)∘⌽⍨)⍨ dft 3
⍨
┌──┘
∘
┌───┴───┐
⍨ ⍨
┌──┘ ┌──┘
. ∘
┌─┴─┐ ┌─┴─┐
+ × ∘ ⌽
┌───┴────┐
∘ \
┌─┴─┐ ┌──┘
⍨ ⌽ ×
┌──┘
÷
+dft 3 ⍝ primitive function.
+
+¨dft 3 ⍝ function derived from monadic operator.
¨
┌──┘
+
+/[2] dft 3 ⍝ check axis operator.
[2]
┌──┘
/
┌──┘
+
+¨∘(÷¨¨¨¨)dft 3 ⍝ overlapping subtrees.
∘
┌──┴───┐
¨ ¨
┌──┘ ┌──┘
+ ¨
┌──┘
¨
┌──┘
¨
┌──┘
÷
+∘(+¨¨¨)dft 3 ⍝ overlapping subtrees.
∘
┌─┴─┐
+ ¨
┌──┘
¨
┌──┘
¨
┌──┘
+
f←+.-.×.÷.⌈.⌊
f∘f∘f∘f∘f dft 3 ⍝ complex derived function expression.
∘
┌────────┴─────────┐
∘ .
┌───────┴────────┐ ┌─┴─┐
∘ . . ⌊
┌──────┴──────┐ ┌─┴─┐ ┌─┴─┐
∘ . . ⌊ . ⌈
┌───┴───┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
. . . ⌊ . ⌈ . ÷
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
. ⌊ . ⌊ . ⌈ . ÷ . ×
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
. ⌈ . ⌈ . ÷ . × + -
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
. ÷ . ÷ . × + -
┌─┴─┐ ┌─┴─┐ ┌─┴─┐
. × . × + -
┌─┴─┐ ┌─┴─┐
+ - + -
∧¨¨¨¨¨¨{⍺⍺∘⍺⍺{⍺⍺∘⍺⍺{⍺⍺∘⍺⍺ dft ⍵}⍵}⍵}3 ⍝ scary sea monster
∘
┌─────────────┴─────────────┐
∘ ∘
┌──────┴──────┐ ┌──────┴──────┐
∘ ∘ ∘ ∘
┌──┴───┐ ┌──┴───┐ ┌──┴───┐ ┌──┴───┐
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘ ┌──┘
∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧
∧¨¨¨¨¨¨{⍺⍺∘⍺⍺{⍺⍺∘⍺⍺{0 ⍺⍺∘⍺⍺ dft ⍵}⍵}⍵}3 ⍝ snoozing sea monster
∘
┌───────┴───────┐
∘ ∘
┌───┴───┐ ┌───┴───┐
∘ ∘ ∘ ∘
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
│ │ │ │ │ │ │ │
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
│ │ │ │ │ │ │ │
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
│ │ │ │ │ │ │ │
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
│ │ │ │ │ │ │ │
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
│ │ │ │ │ │ │ │
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
│ │ │ │ │ │ │ │
∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧
f←+
f←+.f
f←+.f
f←+.f
f←+.f
f←+.f
f←+.f
f.f dft 3 ⍝ test overlapping to the right.
.
┌───┴───┐
. .
┌─┴─┐ ┌─┴─┐
+ . + .
┌─┴─┐ ┌─┴─┐
+ . + .
┌─┴─┐ ┌─┴─┐
+ . + .
┌─┴─┐ ┌─┴─┐
+ . + .
┌─┴─┐ ┌─┴─┐
+ . + .
┌─┴─┐ ┌─┴─┐
+ + + +
f←+
f←f.f
f←f.f
f←f.f
f←f.f
f dft 3 ⍝ balanced tree.
.
┌───────────────┴───────────────┐
. .
┌───────┴───────┐ ┌───────┴───────┐
. . . .
┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐
. . . . . . . .
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
+ + + + + + + + + + + + + + + +
dd←{f←⍺⍺ ⋄ ,⎕fmt ⎕cr'f'} ⍝ default display.
f dd 0
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+
f←f.f ⍝ deeper tree.
f←f.f
f←f.f
f←f.f
f←f.f
80 wrap f dd 0 ⍝ Starry, starry night.
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+
. +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+
. +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+
. +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+
. +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ .
+.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+ . +.+
. +.+ . +.+ . +.+ . +.+ . +.+
1 2 f 3 4 ⍝ (deep inner product).
10
1234∘,∘(,∘5678)dft 3 ⍝ array operands.
∘
┌────┴────┐
∘ ∘
┌──┴───┐ ┌─┴─┐
1234 , , 5678
{⍺}{⍺⍺}{⍺⍺}{⍺⍺}dft 3 ⍝ non-primitive monadic operator.
{⍺⍺}
┌──┘
{⍺⍺}
┌──┘
{⍺⍺}
┌──┘
{⍺}
{⍵}{⍵⍵}{⍵}{⍺⍺{⍵⍵}⍺⍺ dft ⍵} 3 ⍝ non-primitive dyadic operator.
{⍵⍵}
┌─────┴─────┐
{⍵⍵} {⍵⍵}
┌──┴──┐ ┌──┴──┐
{⍵} {⍵} {⍵} {⍵}
⎕fx'fn←{' ' ⍵' '}' ⍝ multi-line function.
⎕fx'mop←{' ' ⍺⍺ ⍵' '}' ⍝ multi-line monadic operator.
⎕fx'dop←{' ' ⍺⍺ ⍵⍵ ⍵' '}' ⍝ multi-line dyadic operator.
mat←3 4⍴⍳12 ⍝ multi-line array operand.
fn mop dop(mat mop) dft 3
{··········
····⍺⍺·⍵⍵·⍵
}··········
┌────┴─────┐
{······· {·······
····⍺⍺·⍵ ····⍺⍺·⍵
}······· }·······
┌──┘ ┌──┘
{···· 1··2··3··4
····⍵ 5··6··7··8
}···· 9·10·11·12
⊃∘(0 1 1∘+)∘(0.5 0 3∘×)⍨∘(2∘⊥)∘(|∘(1∘(,⍨))⍨∘(2∘,)⍨)⍨⍣≡ dft 3 ⍝ osc
⍣
┌─┴─┐
⍨ ≡
┌──┘
∘
┌─────────┴─────────┐
∘ ⍨
┌──┴──┐ ┌──┘
⍨ ∘ ∘
┌──┘ ┌─┴─┐ ┌──┴──┐
∘ 2 ⊥ ⍨ ∘
┌────┴─────┐ ┌──┘ ┌─┴─┐
∘ ∘ ∘ 2 ,
┌─┴─┐ ┌────┴────┐ ┌─┴─┐
⊃ ∘ 0.5·0·3 × | ∘
┌───┴───┐ ┌─┴─┐
0·1·1 + 1 ⍨
┌──┘
,
in←{⊃⍺⍺/⍵} ⍝ in (between): f in x y → x f y
on←{⍺⍺ ⍺ ⍵} ⍝ and its counterpart: x f on y → f x y
↑⍨∘-⍨∘⊃⍨∘(+⍨∘⊃⍨∘(×∘⍴⍨∘×⍨in)⍨on⍨in)⍨on⍨ dft 3 ⍝ inverse for ⍺∘↓.
⍨
┌──┘
{⍺⍺·⍺·⍵}
┌──┘
⍨
┌──┘
∘
┌────┴────┐
⍨ {⊃⍺⍺/⍵}
┌──┘ ┌──┘
∘ ⍨
┌─┴─┐ ┌──┘
⍨ ⊃ {⍺⍺·⍺·⍵}
┌──┘ ┌──┘
∘ ⍨
┌─┴─┐ ┌──┘
⍨ - ∘
┌──┘ ┌───┴────┐
↑ ⍨ {⊃⍺⍺/⍵}
┌──┘ ┌──┘
∘ ⍨
┌─┴─┐ ┌──┘
⍨ ⊃ ∘
┌──┘ ┌─┴─┐
+ ⍨ ×
┌──┘
∘
┌─┴─┐
× ⍴
⌈/¨∘(-∘⊂∘⍳∘⊃∘⌽∘⍴∘⊃⍨)∘(⍳¨in)∘(↓¨)on dft 3 ⍝ inverse for ⌽∘⍵.
{⍺⍺·⍺·⍵}
┌──┘
∘
┌─────────┴─────────┐
∘ ¨
┌──────┴──────┐ ┌──┘
∘ {⊃⍺⍺/⍵} ↓
┌──┴───┐ ┌──┘
¨ ⍨ ¨
┌──┘ ┌──┘ ┌──┘
/ ∘ ⍳
┌──┘ ┌─┴─┐
⌈ ∘ ⊃
┌─┴─┐
∘ ⍴
┌─┴─┐
∘ ⌽
┌─┴─┐
∘ ⊃
┌─┴─┐
∘ ⍳
┌─┴─┐
- ⊂
dinv ← ↑⍨∘-⍨∘⊃⍨∘(+⍨∘⊃⍨∘(×∘⍴⍨∘×⍨in)⍨ on⍨in)⍨ on⍨ ⍝ drop inverse.
2 3 dinv 3 2⍴⍳6
0 0 0 0 0
0 0 0 0 0
0 0 0 1 2
0 0 0 3 4
0 0 0 5 6
leq ← ∨∘(=in)⍨∘(<in)⍨ on ⍝ equivalent of dyadic fork (< ∨ =)
0 0 1 1 leq 0 1 0 1 ⍝ test function.
1 1 0 1
leq dft 3 ⍝ display function tree.
{⍺⍺·⍺·⍵}
┌──┘
⍨
┌──┘
∘
┌──┴───┐
⍨ {⊃⍺⍺/⍵}
┌──┘ ┌──┘
∘ <
┌─┴─┐
∨ {⊃⍺⍺/⍵}
┌──┘
=
⍝ function to generate vector of possible inverses for ⍉∘⍵ :
set←∧/∘⊃∘(,∘⊃∘(∊⍨/)⍨∘(⊃∘(∊/))⍨/)on⍨on
sel←⊃∘((/⍨)/)∘(set¨⍨∘⊂\)on⍨
cvec←(sel∘,∘⍳∘(⍴⍨)∘⍴∘⍴)⍨∘(⍳∘⍴∘⍴)⍨
trinv←⊃∘(cvec/)on
trinv dft 3
{⍺⍺·⍺·⍵}
┌──┘
∘
┌─┴─┐
⊃ /
┌──┘
⍨
┌──┘
∘
┌──┴───┐
⍨ ∘
┌──┘ ┌─┴─┐
∘ ∘ ⍴
┌─┴─┐ ┌─┴─┐
∘ ⍴ ⍳ ⍴
┌─┴─┐
∘ ⍴
┌───┴────┐
∘ ⍨
┌─┴─┐ ┌──┘
∘ ⍳ ⍴
┌─┴─┐
⍨ ,
┌──┘
{⍺⍺·⍺·⍵}
┌──┘
∘
┌────┴─────┐
∘ \
┌─┴─┐ ┌──┘
⊃ / ∘
┌──┘ ┌─┴─┐
⍨ ⍨ ⊂
┌──┘ ┌──┘
/ ¨
┌──┘
{⍺⍺·⍺·⍵}
┌──┘
⍨
┌──┘
{⍺⍺·⍺·⍵}
┌──┘
∘
┌───┴────┐
∘ /
┌─┴─┐ ┌──┘
/ ⊃ ⍨
┌──┘ ┌──┘
∧ ∘
┌──┴───┐
⍨ ∘
┌──┘ ┌─┴─┐
∘ ⊃ /
┌───┴────┐ ┌──┘
∘ / ∊
┌─┴─┐ ┌──┘
, ⊃ ⍨
┌──┘
∊
{⍺}∘{⍵}dft 3 ⍝ check we distinguish {⍵} from a dyadic derv.
∘
┌──┴──┐
{⍺} {⍵}
'abc'∘, dft 3 ⍝ not all 3-vectors are dervs.
∘
┌──┴──┐
abc ,
ulam←⍴∘⍒∘(+\)∘(↑∘(,∘((/∘(⍴∘(1∘,∘(,∘(¯1∘,)⍨∘-⍨))⍨∘(2∘×)⍨)⍨∘(2∘/∘⍳))⍨)⍨∘(+∘(×∘⌊∘(÷∘2)⍨∘(1∘+)⍨)⍨∘(2∘|)⍨)⍨)⍨∘(×⍨)⍨)⍨∘(,⍨)⍨
ulam 10 ⍝ Ulam spiral:
82 81 80 79 78 77 76 75 74 73
83 50 49 48 47 46 45 44 43 72
84 51 26 25 24 23 22 21 42 71
85 52 27 10 9 8 7 20 41 70
86 53 28 11 2 1 6 19 40 69
87 54 29 12 3 4 5 18 39 68
88 55 30 13 14 15 16 17 38 67
89 56 31 32 33 34 35 36 37 66
90 57 58 59 60 61 62 63 64 65
91 92 93 94 95 96 97 98 99 100
⍝ The following output compares the two styles of attaching a left operand to
⍝ its monadic operator. The left tree shows the diagonal or "dog-leg" style,
⍝ while the right tree shows the straight-down style:
⍕ 1 0 ulam dft¨ 3
⍨ ⍨
┌──┘ │
∘ ∘
┌──┴───┐ ┌─┴─┐
⍨ ⍨ ⍨ ⍨
┌──┘ ┌──┘ │ │
∘ , ∘ ,
┌──────┴───────┐ ┌───┴────┐
∘ ⍨ ∘ ⍨
┌───┴────┐ ┌──┘ ┌──┴──┐ │
∘ \ ∘ ∘ \ ∘
┌─┴─┐ ┌──┘ ┌──┴───┐ ┌─┴─┐ │ ┌─┴─┐
⍴ ⍒ + ⍨ ⍨ ⍴ ⍒ + ⍨ ⍨
┌──┘ ┌──┘ │ │
∘ × ∘ ×
┌─┴─┐ ┌─┴─┐
↑ ⍨ ↑ ⍨
┌──┘ │
∘ ∘
┌─────────┴─────────┐ ┌────────┴────────┐
⍨ ⍨ ⍨ ⍨
┌──┘ ┌──┘ │ │
∘ ∘ ∘ ∘
┌─┴─┐ ┌──┴──┐ ┌─┴─┐ ┌──┴──┐
, ⍨ ⍨ ∘ , ⍨ ⍨ ∘
┌──┘ ┌──┘ ┌─┴─┐ │ │ ┌─┴─┐
∘ ∘ 2 | ∘ ∘ 2 |
┌──┴───┐ ┌─┴─┐ ┌────┴────┐ ┌─┴─┐
⍨ ∘ + ⍨ ⍨ ∘ + ⍨
┌──┘ ┌─┴─┐ ┌──┘ │ ┌─┴─┐ │
∘ ∘ ⍳ ∘ ∘ ∘ ⍳ ∘
┌─┴─┐ ┌─┴─┐ ┌──┴──┐ ┌─┴─┐ ┌─┴─┐ ┌──┴──┐
/ ⍨ 2 / ⍨ ∘ / ⍨ 2 / ⍨ ∘
┌──┘ ┌──┘ ┌─┴─┐ │ │ ┌─┴─┐
∘ ∘ 1 + ∘ ∘ 1 +
┌──┴──┐ ┌───┴───┐ ┌──┴──┐ ┌───┴───┐
⍨ ∘ ∘ ∘ ⍨ ∘ ∘ ∘
┌──┘ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ │ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
∘ 2 × × ⌊ ÷ 2 ∘ 2 × × ⌊ ÷ 2
┌─┴─┐ ┌─┴─┐
⍴ ∘ ⍴ ∘
┌───┴────┐ ┌──┴──┐
∘ ⍨ ∘ ⍨
┌─┴─┐ ┌──┘ ┌─┴─┐ │
1 , ∘ 1 , ∘
┌─┴─┐ ┌─┴─┐
⍨ - ⍨ -
┌──┘ │
∘ ∘
┌─┴─┐ ┌─┴─┐
, ∘ , ∘
┌─┴──┐ ┌─┴──┐
¯1 , ¯1 ,
⍝ Dfn for distinct solutions of N-queens problem:
queens←{ ⍝ N-queens problem.
atk←{↑(⊂⍵)+↓¯1 0 1∘.×⌽⍳⍴⍵} ⍝ attack
nxt←{(⍳⍺)~atk ⍵} ⍝ next row
nxts←{(⊂⊃⌽⍵),¨(⊃⍵)nxt⊃⌽⍵} ⍝ possible next rows
red←{(⊃⍵),⊂⊃,/nxts¨(⊃⍵),∘⊂¨⊃⌽⍵} ⍝ reduction
q←{⊃⌽↑red/(⍳⍵),⊂⍵,⊂⊂⍳0} ⍝ general ⍵-queens problem
rot4←{(⊢∘⍒)\4/⊂⍵} ⍝ fn: 4 rotations
tps2←{(⊢∘⍋)\2/⊂⍵} ⍝ fn: 2 transpositions
ord←{⍒↑,↑tps2¨rot4 ⍵} ⍝ fn: order of permutations
best←{1=⊃ord ⍵} ⍝ fn: transformation is "best"
fmt←{⍵∘.=⍳⍴⍵} ⍝ format of complete solution
nq←{fmt¨(best¨⍵)/⍵}∘q ⍝ distinct solutions.
nq ⍵
}
queens 5 ⍝ 5-queens: distinct solutions.
┌─────────┬─────────┐
│0 0 0 1 0│0 0 0 0 1│
│1 0 0 0 0│0 0 1 0 0│
│0 0 1 0 0│1 0 0 0 0│
│0 0 0 0 1│0 0 0 1 0│
│0 1 0 0 0│0 1 0 0 0│
└─────────┴─────────┘
⍝ Equivalent derived function coding:
atk ← ↑∘(+∘↓∘(¯1 0 1∘(∘.×)∘⌽∘⍳∘⍴)⍨∘⊂⍨) ⍝ attack
nxt ← ~∘atk⍨∘⍳⍨ ⍝ next row
nxts ← ,¨∘(nxt∘⊃∘⌽⍨∘⊃⍨)⍨∘⊂∘⊃∘⌽⍨ ⍝ possible next rows
red ← ⊢∘(,∘⊂∘⊃∘(,/)∘(nxts¨)∘(,∘⊂¨∘⊃∘⌽⍨∘⊃⍨)⍨∘⊃⍨) ⍝ reduction
rot4 ← ⊢∘⍒\∘(4∘/)∘⊂ ⍝ fn: 4 rotations
tps2 ← ⊢∘⍋\∘(2∘/)∘⊂ ⍝ fn: 2 transpositions
ord ← ⍒∘↑∘,∘↑∘(tps2¨)∘rot4 ⍝ fn: order of perms
best ← 1∘=∘⊃∘ord ⍝ fn: perm is "best"
fmt ← ∘.=∘⍳∘⍴⍨ ⍝ format of solution
q ← ⊃∘⌽∘↑∘(red/)∘(,∘⊂∘(,∘⊂∘⊂∘⍳∘(0∘⊣)⍨)⍨∘⍳⍨) ⍝ general ⍵-queens prob
nq ← fmt¨∘((/⍨)∘(best¨)⍨)∘q ⍝ distinct solutions.
nq 5 ⍝ 5-queens: distinct solutions.
┌─────────┬─────────┐
│0 0 0 1 0│0 0 0 0 1│
│1 0 0 0 0│0 0 1 0 0│
│0 0 1 0 0│1 0 0 0 0│
│0 0 0 0 1│0 0 0 1 0│
│0 1 0 0 0│0 1 0 0 0│
└─────────┴─────────┘
nq dft 3 ⍝ N-queens: derived fn tree
∘
┌─────────────────────────────┴─────────────────────────────┐
∘ ∘
┌───┴────┐ ┌───────────┴────────────┐
¨ ⍨ ∘ ⍨
┌──┘ ┌──┘ ┌───┴────┐ ┌──┘
⍨ ∘ ∘ / ∘
┌──┘ ┌──┴───┐ ┌─┴─┐ ┌──┘ ┌─┴─┐
∘ ⍨ ¨ ∘ ↑ ∘ ⍨ ⍳
┌─┴─┐ ┌──┘ ┌──┘ ┌─┴─┐ ┌─┴─┐ ┌──┘
∘ ⍴ / ∘ ⊃ ⌽ ⊢ ⍨ ∘
┌─┴─┐ ┌───────┴────────┐ ┌──┘ ┌───┴────┐
. ⍳ ∘ ∘ ∘ ∘ ⍨
┌─┴─┐ ┌─┴─┐ ┌───────┴────────┐ ┌─┴─┐ ┌─┴─┐ ┌──┘
∘ = ∘ ⊃ ∘ ∘ ⍨ ⊃ , ⊂ ∘
┌─┴─┐ ┌────┴────┐ ┌─┴─┐ ┌──┘ ┌───┴───┐
1 = ∘ ¨ ∘ ⊂ ∘ ∘ ∘
┌─┴─┐ ┌──┘ ┌──┴──┐ ┌────────┴─────────┐ ┌─┴─┐ ┌─┴─┐
∘ ↑ ∘ \ ∘ ∘ ⍨ ∘ ⍳ 0 ⊣
┌─┴─┐ ┌─┴─┐ ┌──┘ ┌─┴─┐ ┌──────┴───────┐ ┌──┘ ┌─┴─┐
∘ , ∘ ⊂ ∘ 4 / ∘ ¨ ∘ ∘ ⊂
┌─┴─┐ ┌──┴──┐ ┌─┴─┐ ┌───┴────┐ ┌──┘ ┌─┴─┐ ┌─┴─┐
⍒ ↑ \ ∘ ⊢ ⍒ ∘ / ⍨ ⍨ ⊃ , ⊂
┌──┘ ┌─┴─┐ ┌─┴─┐ ┌──┘ ┌──┘ ┌──┘
∘ 2 / ∘ ⊃ , ∘ ∘
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
⊢ ⍋ , ⊂ ∘ ⌽ ∘ ⌽
┌─┴─┐ ┌─┴─┐
∘ ⊃ ¨ ⊃
┌─┴─┐ ┌──┘
⍨ ⊂ ∘
┌──┘ ┌─┴─┐
∘ , ⊂
┌──┴───┐
¨ ⍨
┌──┘ ┌──┘
, ∘
┌─┴─┐
⍨ ⊃
┌──┘
∘
┌─┴─┐
∘ ⌽
┌─┴─┐
⍨ ⊃
┌──┘
∘
┌─┴─┐
⍨ ⍳
┌──┘
∘
┌─┴─┐
~ ∘
┌─┴─┐
↑ ⍨
┌──┘
∘
┌─┴─┐
⍨ ⊂
┌──┘
∘
┌───┴───┐
∘ ∘
┌─┴─┐ ┌─┴─┐
+ ↓ ∘ ⍴
┌─┴─┐
∘ ⍳
┌─┴─┐
∘ ⌽
┌───┴────┐
¯1·0·1 .
┌─┴─┐
∘ ×
⍝ Notice how derived function [nq] consists entirely of:
⍝ - primitive functions and operators, together with
⍝ - ⊣ and ⊢ and
⍝ - the literal values ¯1 0 1, 4, 2 and 0.
⍝
⍝ These literal values could also be replaced with expressions of primitive
⍝ functions: for example 2/⊂⍵ could be recast:
⍝
⍝ 2/⊂⍵ → (≡⊂⍵)/⊂⍵ → /∘⊂⍨∘≡∘⊂⍨⍵
⍝
⍝ Similarly:
⍝
⍝ ⍴⍴⊂⍵ → 0
⍝ ≡⍵ → 1
⍝ ≡⊂⍵ → 2
⍝ ≡⊂⊂⊂⍵ → 4
⍝
⍝ This means that,in extremis, distinct solutions of the N-queens problem may be
⍝ expressed as a function derived solely from primitive functions and operators.
⍝
⍝ k101 ← ⊢∘(-∘≡∘⊂⍨∘⍳∘≡∘⊂∘⊂⍨) ⍝ k101 ⍵ → ¯1 0 1
⍝ k0 ← ⍴∘⍴∘⊂ ⍝ k0 ⍵ → 0
⍝ k1 ← ≡ ⍝ k1 ⍵ → 1
⍝ k2 ← ≡∘⊂ ⍝ k2 ⍵ → 2
⍝ k4 ← ≡∘⊂∘⊂∘⊂ ⍝ k4 ⍵ → 4
⍝ atk ← ↑∘(+∘↓∘(∘.×∘⌽∘⍳∘⍴⍨∘k101⍨)⍨∘⊂⍨) ⍝ attack
⍝ nxt ← ~∘atk⍨∘⍳⍨ ⍝ next row
⍝ nxts ← ,¨∘(nxt∘⊃∘⌽⍨∘⊃⍨)⍨∘⊂∘⊃∘⌽⍨ ⍝ possible next rows
⍝ red ← ⊢∘(,∘⊂∘⊃∘(,/)∘(nxts¨)∘(,∘⊂¨∘⊃∘⌽⍨∘⊃⍨)⍨∘⊃⍨) ⍝ reduction
⍝ rot4 ← ⊢∘⍒\∘(/∘⊂⍨∘k4⍨) ⍝ 4 rotations
⍝ tps2 ← ⊢∘⍋\∘(/∘⊂⍨∘k2⍨) ⍝ 2 transpositions
⍝ ord ← ⍒∘↑∘,∘↑∘(tps2¨)∘rot4 ⍝ order of permutations
⍝ best ← =∘⊃∘ord⍨∘k1⍨ ⍝ transformation is "best"
⍝ fmt ← ∘.=∘⍳∘⍴⍨ ⍝ format of solutions
⍝ q ← ⊃∘⌽∘↑∘(red/)∘(,∘⊂∘(,∘⊂∘⊂∘⍳∘k0⍨)⍨∘⍳⍨) ⍝ general ⍵-queens problem
⍝ nq ← fmt¨∘((/⍨)∘(best¨)⍨)∘q ⍝ distinct solutions.
⍝
⍝ nq dft 5 ⍝ V13 primitive fn/op only version:
⍝ ∘
⍝ ┌───────────────────────────────┴───────────────────────────────┐
⍝ ∘ ∘
⍝ ┌───┴────┐ ┌───────────┴───────────┐
⍝ ¨ ⍨ ∘ ⍨
⍝ ┌─┘ ┌─┘ ┌───┴───┐ ┌─┘
⍝ ⍨ ∘ ∘ / ∘
⍝ ┌─┘ ┌──┴──┐ ┌─┴─┐ ┌─┘ ┌─┴─┐
⍝ ∘ ⍨ ¨ ∘ ↑ ∘ ⍨ ⍳
⍝ ┌─┴─┐ ┌─┘ ┌─┘ ┌─┴─┐ ┌─┴─┐ ┌─┘
⍝ ∘ ⍴ / ⍨ ⊃ ⌽ ⊢ ⍨ ∘
⍝ ┌─┴─┐ ┌─┘ ┌─┘ ┌───┴───┐
⍝ . ⍳ ∘ ∘ ∘ ⍨
⍝ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┘
⍝ ∘ = ⍨ ≡ ⍨ ⊃ , ⊂ ∘
⍝ ┌─┘ ┌─┘ ┌───┴───┐
⍝ ∘ ∘ ∘ ∘
⍝ ┌───────┴───────┐ ┌───────┴───────┐ ┌─┴─┐ ┌─┴─┐
⍝ ∘ ∘ ∘ ⍨ ∘ ⍳ ∘ ⊂
⍝ ┌─┴─┐ ┌─────────┴──────────┐ ┌─────┴─────┐ ┌─┘ ┌─┴─┐ ┌─┴─┐
⍝ = ⊃ ∘ ∘ ∘ ¨ ∘ ∘ ⊂ ⍴ ⍴
⍝ ┌────┴────┐ ┌────┴────┐ ┌───┴───┐ ┌─┘ ┌─┴─┐ ┌─┴─┐
⍝ ∘ ¨ \ ⍨ ∘ / ⍨ ⍨ ⊃ , ⊂
⍝ ┌─┴─┐ ┌─┘ ┌─┘ ┌─┘ ┌─┴─┐ ┌─┘ ┌─┘ ┌─┘
⍝ ∘ ↑ ∘ ∘ ∘ ∘ ⊃ , ∘ ∘
⍝ ┌─┴─┐ ┌───┴────┐ ┌─┴─┐ ┌───┴───┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
⍝ ∘ , \ ⍨ ⊢ ⍒ ⍨ ∘ , ⊂ ∘ ⌽ ∘ ⌽
⍝ ┌─┴─┐ ┌─┘ ┌─┘ ┌─┘ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
⍝ ⍒ ↑ ∘ ∘ ∘ ∘ ⊂ ∘ ⊃ ¨ ⊃
⍝ ┌─┴─┐ ┌──┴──┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┘
⍝ ⊢ ⍋ ⍨ ∘ / ⊂ ∘ ⊂ ⍨ ⊂ ∘
⍝ ┌─┘ ┌─┴─┐ ┌─┴─┐ ┌─┘ ┌─┴─┐
⍝ ∘ ≡ ⊂ ≡ ⊂ ∘ , ⊂
⍝ ┌─┴─┐ ┌──┴──┐
⍝ / ⊂ ¨ ⍨
⍝ ┌─┘ ┌─┘
⍝ , ∘
⍝ ┌─┴─┐
⍝ ⍨ ⊃
⍝ ┌─┘
⍝ ∘
⍝ ┌─┴─┐
⍝ ∘ ⌽
⍝ ┌─┴─┐
⍝ ⍨ ⊃
⍝ ┌─┘
⍝ ∘
⍝ ┌─┴─┐
⍝ ⍨ ⍳
⍝ ┌─┘
⍝ ∘
⍝ ┌─┴─┐
⍝ ~ ∘
⍝ ┌─┴─┐
⍝ ↑ ⍨
⍝ ┌─┘
⍝ ∘
⍝ ┌─┴─┐
⍝ ⍨ ⊂
⍝ ┌─┘
⍝ ∘
⍝ ┌───┴───┐
⍝ ∘ ⍨
⍝ ┌─┴─┐ ┌─┘
⍝ + ↓ ∘
⍝ ┌──┴──┐
⍝ ⍨ ∘
⍝ ┌─┘ ┌─┴─┐
⍝ ∘ ⊢ ⍨
⍝ ┌─┴─┐ ┌─┘
⍝ ∘ ⍴ ∘
⍝ ┌─┴─┐ ┌─┴─┐
⍝ ∘ ⍳ ∘ ⊂
⍝ ┌─┴─┐ ┌─┴─┐
⍝ . ⌽ ∘ ⊂
⍝ ┌─┴─┐ ┌─┴─┐
⍝ ∘ × ∘ ≡
⍝ ┌─┴─┐
⍝ ⍨ ⍳
⍝ ┌─┘
⍝ ∘
⍝ ┌─┴─┐
⍝ ∘ ⊂
⍝ ┌─┴─┐
⍝ - ≡
⍝∇ dft wrap
Back to: code
Back to: Workspaces