~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

a:: #→#→#       / Ackermann's function.

    a 0    n    = +n
    a (+m) 0    = a m 1
    a (+m) (+n) = a m (a (+m) n)

b:: #→#→#→#     / Ackermann's other function:

    b 0 m   0  = m                  / sum
    b 0 m (+n) = +(b 0 m n)

    b 1 m   0  = 0                  / product
    b 1 m (+n) = b 0 m (b 1 m n )

    b (+(+k)) m   0  = 1            / exponent and beyond ···
    b (+(+k)) m (+n) = b (+k) m (b (+(+k)) m n)

    / Then, using partial application (currying):

    s = b 0     / sum
    p = b 1     / product
    e = b 2     / exponent
    / ...       / ... and beyond.

// examples:

    a 2 2   / ack(2,2)
7

    s 3 2   / sum         3+2   1(+⍣⍵)⍺
5
    p 3 2   / product     3×2 \ ⍺(+⍣⍵)0
6
    e 3 2   / exponent    3*2 \ ⍺(×⍣⍵)1
9
    b 3 2 2 / and beyond  ... \ ⍺(*⍣⍵)1
4

// For more on these functions, search for "Ackermann"
// in: http://www.dyalog.com/dfnsdws/min_backg.htm

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

r:: #→[#]→#     / radix-decode:

    r n = d                                 / auxiliary decode function.
    .   d [ 0] =  0                         / decode [0] → 0.
    .   d [+i] = +i                         / decode [i] → i.
    .   d ( 0:j:k) = d (j:k)                / ignore leading 0.
    .   d (+i:j:k) = c n (i:j:k)            / carry base to next column.
    .   .   c   0  (i:j:k) = d (i:j:k)      / carry 0: done.
    .   .   c (+m) (i:j:k) = c m (i:+j:k)   / carry 1 → next col + base.

// examples:

    r 1 [1,0,1,0,1,0]   / unary decode (tally)
3
    r 2 [1,0,1,0,1,0]   / binary decode
42
    r (+9) [1,2,3]      / decimal decode
123

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

r:: (⍺→⍵→⍵)→⍵→[⍺]→⍵             / fold (reduce) right:

    r f i []    = i
    r f i (x:y) = f x (r f i y)

l:: (⍺→⍵→⍺)→⍺→[⍵]→⍺             / fold (reduce) left:

    l f i [] = i
    l f i (x:y) = l f (f i x) y

// examples:

    r s 0 [1,2,3]               / sum-reduce
    .   s 0 j = j
    .   s (+i) j = +(s i j)
6

    l d 0 [1,2,3]               / decimal-decode
    .   d 0 u = u
    .   d (+t) u = d t (+(+(+(+(+(+(+(+(+(+u))))))))))
123

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

g:: #→#→#       / greatest-common-divisor:

    g m n = h m n m n
    .   h   0    0    i    j  = 0
    .   h   0  (+n)   i    j  = +n
    .   h (+m)   0    i    j  = +m
    .   h (+m) (+n)   0    0  = +m
    .   h (+m) (+n)   0  (+j) = h (+m) (+j) m j
    .   h (+m) (+n) (+i)   0  = h (+i) (+n) i n
    .   h (+m) (+n) (+i) (+j) = h (+m) (+n) i j

// examples:

    [
        g 6 9,  / → 3
        g 3 5,  / → 1
        g 0 3,  / → 3
        g 3 0,  / → 3
        g 3 3   / → 3
    ]
[3,1,3,3,3]

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

m:: (⍺→⍵)→[⍺]→[⍵]       / map (each):

    m f   []  = []
    m f (x:y) = f x : m f y

// examples:

    m + [0,1,2]         / map successor
[1,2,3]

    m (m+) [            / map map ..
        [],             / → []
        [0],            / → [1]
        [1,2],          / → [2,3]
        [3,4,5]         / → [4,5,6]
    ]
[[],[1],[2,3],[4,5,6]]

    m r [               / map reverse
        [],             / → []
        [0],            / → [0]
        [1,2],          / → [2,1]
        [3,4,5]         / → [5,4,3]
    ]
    .   r = f []
    .   .   f x []    = x
    .   .   f x (y:z) = f (y:x) z
[[],[0],[2,1],[5,4,3]]

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

p:: [#]         / prime numbers:

    p = s (i 2)                         / sieve primes from [2,3,4, ...
    .   s  (0:y) = s y                  / skip multiple of prime.
    .   s (+i:y) = +i : s (z i y)       / prime with zeros for multiples.
    .   .   z   0  (x:y) = 0 : z i y    / multiple: zero for head.
    .   .   z (+j) (x:y) = x : z j y    / otherwise: prime for head.
    .   i j = j : i (+j)                / nums [j, +j, +(+j), ...

// example:

    t p . t(a:b:c:x) = [a,b,c]          / first three prime numbers.
[2,3,5]

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

r:: #→#→#       / residue (modulus):

    r   0    0  = 0
    r (+m)   0  = 0
    r   0  (+n) = +n
    r (+m) (+n) = s (+m) (+n) m n
    .   s m n   0    0  = 0
    .   s m n (+i)   0  = n
    .   s m n   0  (+j) = s m (+j) m (+j)
    .   s m n (+i) (+j) = s m n i j

// examples:

    [
        r 0 0,  / → 0
        r 0 3,  / → 3
        r 3 0,  / → 0
        r 3 6,  / → 0
        r 3 7,  / → 1
        r 3 8   / → 2
    ]
[0,3,0,0,1,2]

    )


Back to: contents