APL Exercises 2
Recursion
⎕io←0 throughout.
2.0 Factorial
Write a function to compute the factorial function on integer ⍵ , ⍵≥0 .
fac¨ 5 6 7 8 120 720 5040 40320 n←1+?20 (fac n) = n×fac n-1 1 fac 0 1
2.1 Fibonacci Numbers
Write a function to compute the ⍵-th Fibonacci number, ⍵≥0 .
fib¨ 5 6 7 8 5 8 13 21 n←2+?20 (fib n) = (fib n-2) + (fib n-1) 1 fib 0 0 fib 1 1
If the function written above is multiply recursive,
write a version which is singly recursive (only one occurrence of ∇).
Use cmpx to compare the performance of the two functions
on the argument 35 .
2.2 Peano Addition
Let ⍺ and ⍵ be natural numbers
(non-negative integers).
Write a function padd to compute ⍺+⍵ without using +
itself (or - or × or ÷ …).
The only functions allowed are comparison to 0
and the functions pre←{⍵-1} and suc←{⍵+1} .
2.3 Peano Multiplication
Let ⍺ and ⍵ be natural numbers
(non-negative integers).
Write a function ptimes to compute ⍺×⍵ without using ×
itself (or + or - or ÷ …).
The only functions allowed are comparison to 0
and the functions pre←{⍵-1} and suc←{⍵+1} and padd .
2.4 Binomial Coefficients
Write a function to produce the binomal coefficients of order ⍵ , ⍵≥0 .
bc 0 1 bc 1 1 1 bc 2 1 2 1 bc 3 1 3 3 1 bc 4 1 4 6 4 1
2.5 Cantor Set
Write a function to compute the Cantor set of order ⍵ , ⍵≥0 .
Cantor 0 1 Cantor 1 1 0 1 Cantor 2 1 0 1 0 0 0 1 0 1 Cantor 3 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1
The classical version of the Cantor set starts with the interval [0,1]
and at each stage removes the middle third from each remaining subinterval:
[0,1] →
[0,1/3]
∪ [2/3,1] →
[0,1/9]
∪ [2/9,1/3]
∪ [2/3,7/9]
∪ [8/9,1] → ….
{(+⌿÷≢)Cantor ⍵}¨ 3 5⍴⍳15
1 0.666667 0.444444 0.296296 0.197531
0.131687 0.0877915 0.0585277 0.0390184 0.0260123
0.0173415 0.011561 0.00770735 0.00513823 0.00342549
(2÷3)*3 5⍴⍳15
1 0.666667 0.444444 0.296296 0.197531
0.131687 0.0877915 0.0585277 0.0390184 0.0260123
0.0173415 0.011561 0.00770735 0.00513823 0.00342549
2.6 Sierpinski Carpet
Write a function to compute the Sierpinski Carpet of order ⍵ , ⍵≥0 .
SC 0
1
SC 1
1 1 1
1 0 1
1 1 1
SC 2
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1
1 1 1 0 0 0 1 1 1
1 0 1 0 0 0 1 0 1
1 1 1 0 0 0 1 1 1
1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1
' ⌹'[SC 3]
⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹
⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹
⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹
⌹⌹⌹ ⌹⌹⌹⌹⌹⌹ ⌹⌹⌹⌹⌹⌹ ⌹⌹⌹
⌹ ⌹ ⌹ ⌹⌹ ⌹ ⌹ ⌹⌹ ⌹ ⌹ ⌹
⌹⌹⌹ ⌹⌹⌹⌹⌹⌹ ⌹⌹⌹⌹⌹⌹ ⌹⌹⌹
⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹
⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹
⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹
⌹⌹⌹⌹⌹⌹⌹⌹⌹ ⌹⌹⌹⌹⌹⌹⌹⌹⌹
⌹ ⌹⌹ ⌹⌹ ⌹ ⌹ ⌹⌹ ⌹⌹ ⌹
⌹⌹⌹⌹⌹⌹⌹⌹⌹ ⌹⌹⌹⌹⌹⌹⌹⌹⌹
⌹⌹⌹ ⌹⌹⌹ ⌹⌹⌹ ⌹⌹⌹
⌹ ⌹ ⌹ ⌹ ⌹ ⌹ ⌹ ⌹
⌹⌹⌹ ⌹⌹⌹ ⌹⌹⌹ ⌹⌹⌹
⌹⌹⌹⌹⌹⌹⌹⌹⌹ ⌹⌹⌹⌹⌹⌹⌹⌹⌹
⌹ ⌹⌹ ⌹⌹ ⌹ ⌹ ⌹⌹ ⌹⌹ ⌹
⌹⌹⌹⌹⌹⌹⌹⌹⌹ ⌹⌹⌹⌹⌹⌹⌹⌹⌹
⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹
⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹
⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹
⌹⌹⌹ ⌹⌹⌹⌹⌹⌹ ⌹⌹⌹⌹⌹⌹ ⌹⌹⌹
⌹ ⌹ ⌹ ⌹⌹ ⌹ ⌹ ⌹⌹ ⌹ ⌹ ⌹
⌹⌹⌹ ⌹⌹⌹⌹⌹⌹ ⌹⌹⌹⌹⌹⌹ ⌹⌹⌹
⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹
⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹⌹ ⌹
⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹⌹
3-d analogs of the Cantor set and the Sierpinski carpet are the Sierpinski sponge or the Menger sponge.
2.7 Extended H
Write a function for the extend H algorithm for ⍵ , ⍵≥0 , which embeds the complete binary tree of depth ⍵ on the plane. In xH ⍵ there are 2*⍵ leaves, instances of the letter o with exactly one neighbor (or no neighbors for 0=⍵). The root is at the center of the matrix.
xH¨ ⍳5 ┌─┬─────┬─────┬─────────────┬─────────────┐ │o│o-o-o│o o│o-o-o o-o-o│o o o o│ │ │ │| |│ | | │| | | |│ │ │ │o-o-o│ o---o---o │o-o-o o-o-o│ │ │ │| |│ | | │| | | | | |│ │ │ │o o│o-o-o o-o-o│o | o o | o│ │ │ │ │ │ | | │ │ │ │ │ │ o---o---o │ │ │ │ │ │ | | │ │ │ │ │ │o | o o | o│ │ │ │ │ │| | | | | |│ │ │ │ │ │o-o-o o-o-o│ │ │ │ │ │| | | |│ │ │ │ │ │o o o o│ └─┴─────┴─────┴─────────────┴─────────────┘
Write a function that has the same result as xH but checks the result using the assert utility. For example:
assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕SIGNAL 8 ⋄ shy←0}
xH1←{
h←xH ⍵
assert 2=⍴⍴h:
assert h∊'○ -|':
assert (¯1+2*1+⍵)=+/'o'=,h:
…
h
}
2.8 Tower of Hanoi
The Tower of Hanoi problem is to move a set of n different-sized disks from one peg to another, moving one disk at a time, using an intermediate peg if necessary. At all times no larger disk may sit on top of a smaller disk.
Write a function Hanoi ⍵ to solve the problem of moving ⍵ disks from peg 0 to peg 2. Since it’s always the disk which is at the top of a peg which is moved, the solution can be stated as a 2-column matrix with column 0 indicating the source peg and column 1 the destination peg.
Hanoi¨ ⍳5 ┌───┬───┬───┬───┬───┐ │ │0 2│0 1│0 2│0 1│ │ │ │0 2│0 1│0 2│ │ │ │1 2│2 1│1 2│ │ │ │ │0 2│0 1│ │ │ │ │1 0│2 0│ │ │ │ │1 2│2 1│ │ │ │ │0 2│0 1│ │ │ │ │ │0 2│ │ │ │ │ │1 2│ │ │ │ │ │1 0│ │ │ │ │ │2 0│ │ │ │ │ │1 2│ │ │ │ │ │0 1│ │ │ │ │ │0 2│ │ │ │ │ │1 2│ └───┴───┴───┴───┴───┘
Prove that Hanoi ⍵ has ¯1+2*⍵ rows.