tree ← (derv ##.ddft) smooth ⍝ Display derived function tree.
Operator [ddft] returns the character matrix representation of its derived func-
tion operand [derv].
Right argument [smooth] determines whether the branches of the tree are drawn
using smooth or clunky line-drawing characters (the latter are easier to print):
1-smooth ┌─┴─┐
0-clunky .-'-.
Technical notes:
A complication arises from compacting the output by meshing subtrees to overlap
vertically.
Without vertical overlap With vertical overlap
------------------------ ---------------------
∘ ∘
┌──┴──────────┐ ┌───┴───┐
∘ ∘ ∘ ∘
┌──┴─┐ ┌──┴─┐ ┌─┴─┐ ┌─┴─┐
∘ + ∘ + ∘ + ∘ +
┌──┴─┐ ┌──┴─┐ ┌─┴─┐ ┌─┴─┐
∘ + ∘ + ∘ + ∘ +
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
∘ + ∘ + ∘ + ∘ +
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
+ + + + + + + +
This is achieved by inner function "mesh" using steps:
1. Extend the shallower subtree so that both have the same number of rows.
2. Determine the minimum horizontal gap between the subtrees.
3. Distribute the number of characters to be dropped between the subtrees.
4. Drop separating blanks; join corresponding rows; mix rows to a matrix.
Examples:
deco← +.×⍨∘(÷∘⌽∘(+\)∘⌽⍨)⍨ ⍝ derived function.
disp ⎕cr'deco' ⍝ nested canonical rep'n.
┌→────────────────────────────────────┬─┐
│┌→──────┬─┬─────────────────────────┐│ │
││ │ │┌→────────────────────┬─┐││ │
││ │ ││┌→──────────────┬─┬─┐│ │││ │
││ │ │││┌→───────┬─┬──┐│ │ ││ │││ │
││┌→──┬─┐│ ││││┌→─┬─┬─┐│ │ ││ │ ││ │││ │
│││+.×│⍨││∘│││││÷⍨│∘│⌽││∘│×\││∘│⌽││⍨│││⍨│
││└──→┴─┘│ ││││└─→┴─┴─┘│ │ ││ │ ││ │││ │
││ │ │││└───────→┴─┴─→┘│ │ ││ │││ │
││ │ ││└──────────────→┴─┴─┘│ │││ │
││ │ │└────────────────────→┴─┘││ │
│└──────→┴─┴────────────────────────→┘│ │
└────────────────────────────────────→┴─┘
deco ddft 1 ⍝ tree using smooth chars.
⍨
┌─┘
∘
┌───┴───┐
⍨ ⍨
┌─┘ ┌─┘
. ∘
┌─┴─┐ ┌─┴─┐
+ × ∘ ⌽
┌───┴───┐
∘ \
┌─┴─┐ ┌─┘
⍨ ⌽ ×
┌─┘
÷
deco ddft 0 ⍝ tree using clunky chars.
⍨
.-'
∘
.---'---.
⍨ ⍨
.-' .-'
. ∘
.-'-. .-'-.
+ × ∘ ⌽
.---'---.
∘ \
.-'-. .-'
⍨ ⌽ ×
.-'
÷
+{⍺⍺ ⍵}{⍺⍺ ⍵}ddft 1 ⍝ non-primitive operator.
{⍺⍺·⍵}
┌─┘
{⍺⍺·⍵}
┌─┘
+
^¨¨¨¨¨¨{⍺⍺∘⍺⍺{⍺⍺∘⍺⍺{⍺⍺∘⍺⍺ ddft ⍵}⍵}⍵}1 ⍝ scary sea monster.
∘
┌───────────┴───────────┐
∘ ∘
┌─────┴─────┐ ┌─────┴─────┐
∘ ∘ ∘ ∘
┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘
¨ ¨ ¨ ¨ ¨ ¨ ¨ ¨
┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘ ┌─┘
^ ^ ^ ^ ^ ^ ^ ^
⍝ "Combinators" [in] and [on], together with primitive operators
⍝ compose ∘ and commute ⍨ allow us to build long function-operator
⍝ trains:
in←{⊃⍺⍺/⍵} ⍝ in (between): f in x y → x f y
on←{⍺⍺ ⍺ ⍵} ⍝ and its counterpart: x f on y → f x y
⍝ J language's hook and fork constructs may be translated into such
⍝ trains using: ┌──────────┬──────────────────┬─────────────────────┐
⍝ │ J Syntax │ Equivalent D │ Equivalent Train │
⍝ ┌─────────────┼──────────┼──────────────────┼─────────────────────┤
⍝ │Monadic Hook │ (g h) │ {g h ⍵} │ g∘h │
⍝ ├─────────────┼──────────┼──────────────────┼─────────────────────┤
⍝ │Dyadic Hook │ (g h) │ {⍺ g h ⍵} │ g∘h │
⍝ ├─────────────┼──────────┼──────────────────┼─────────────────────┤
⍝ │Monadic Fork │ (f g h) │ {(f ⍵)g h ⍵} │ g∘h⍨∘f⍨ │
⍝ ├─────────────┼──────────┼──────────────────┼─────────────────────┤
⍝ │Dyadic Fork │ (f g h) │ {(⍺ f ⍵)g ⍺ h ⍵} │ g∘(h in)⍨∘(f in)⍨on │
⍝ └─────────────┴──────────┴──────────────────┴─────────────────────┘
⍝ For example:
avg ← ÷∘⍴⍨∘(+/)⍨ ⍝ equivalent of monadic fork (+/ ÷ ⍴)
avg 1 2 3 4 ⍝ test function.
1 2 3 4
avg ddft 1 ⍝ display function tree.
⍨
┌─┘
∘
┌──┴──┐
⍨ /
┌─┘ ┌─┘
∘ +
┌─┴─┐
÷ ⍴
leq ← ∨∘(=in)⍨∘(<in)⍨on ⍝ equivalent of dyadic fork (< ∨ =)
0 0 1 1 leq 0 1 0 1 ⍝ test function.
1 1 0 1
leq ddft 1 ⍝ display function tree.
on←{⍺⍺·⍺·⍵}
┌─┘
⍨
┌─┘
∘
┌──┴──┐
⍨ in←{⊃⍺⍺/⍵}
┌─┘ ┌─┘
∘ <
┌─┴─┐
∨ in←{⊃⍺⍺/⍵}
┌─┘
=
⍝ NB: The above functions include monadic commute: f⍨x → x f x, which appeared
⍝ in V10. To experiment with the functions in Dyalog V9 or below, replace each
⍝ occurrence of ⍨ with: {⍺←⍵ ⋄ ⍵ ⍺⍺ ⍺}. <V>
⍝ Historical note: Mechanisms for distributing arguments through trees of
⍝ functions originated in the field of combinatorial algebra in the 1920s
⍝ and 30s. See min.dws/Background for more on combinators.
⍝ More examples of function-operator trains:
fib ← +/∘(!∘⌽⍨)∘(-∘⎕io)∘⍳ ⍝ ⍵th fibonacci number.
fib¨⍳10
1 1 2 3 5 8 13 21 34 55
fib ddft 1
∘
┌─┴─┐
∘ ⍳
┌────┴───┐
∘ ∘
┌──┴──┐ ┌─┴─┐
/ ⍨ - 1
┌─┘ ┌─┘
+ ∘
┌─┴─┐
! ⌽
dinv ← ↑⍨∘-⍨∘⊃⍨∘(+⍨∘⊃⍨∘(×∘⍴⍨∘×⍨in)⍨on⍨in)⍨on⍨ ⍝ inverse for ⍺∘↓.
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
dinv ddft 1 ⍝ display function tree.
⍨
┌─┘
on←{⍺⍺·⍺·⍵}
┌─┘
⍨
┌─┘
∘
┌───┴───┐
⍨ in←{⊃⍺⍺/⍵}
┌─┘ ┌─┘
∘ ⍨
┌─┴─┐ ┌─┘
⍨ ⊃ on←{⍺⍺·⍺·⍵}
┌─┘ ┌─┘
∘ ⍨
┌─┴─┐ ┌─┘
⍨ - ∘
┌─┘ ┌───┴───┐
↑ ⍨ in←{⊃⍺⍺/⍵}
┌─┘ ┌─┘
∘ ⍨
┌─┴─┐ ┌─┘
⍨ ⊃ ∘
┌─┘ ┌─┴─┐
+ ⍨ ×
┌─┘
∘
┌─┴─┐
× ⍴
rinv ← ⌈/¨∘(-∘⊂∘⍳∘(⊃∘⌽)∘⍴∘⊃⍨)∘(⍳¨in)∘(↓¨)on ⍝ inverse for ⌽∘⍵.
'Mississippi' rinv 'issippiMiss'
4
rinv ddft 1 ⍝ display function tree.
on←{⍺⍺·⍺·⍵}
┌─┘
∘
┌─────────┴─────────┐
∘ ¨
┌─────┴────┐ ┌─┘
∘ in←{⊃⍺⍺/⍵} ↓
┌──┴──┐ ┌─┘
¨ ⍨ ¨
┌─┘ ┌─┘ ┌─┘
/ ∘ ⍳
┌─┘ ┌─┴─┐
⌈ ∘ ⊃
┌─┴─┐
∘ ⍴
┌───┴───┐
∘ ∘
┌─┴─┐ ┌─┴─┐
∘ ⍳ ⊃ ⌽
┌─┴─┐
- ⊂
⍝ Functions for 1st and 2nd items of a pair, used in these examples, might also
⍝ be considered combinators. In the examples above, they have been implemented
⍝ (assuming ⎕ml<2) as ⊃ and ⊃∘⌽, respectively. A more satisfying, though slower,
⍝ alternative might be:
fst ← {⍺}in ⍝ 1st item of pair.
snd ← {⍵}in ⍝ 2nd item of pair.
See also: tfmt fork
Back to: contents
Back to: Dyalog APL
Trouble seeing APL font?