/ Max extends the Min language with type, lists and local definitions.
/ Call Max from APL by typing:
/
/ max''
/
/ Lists are constructed with:
/
/ The null list '[]', pronounced "null",
/
/ Infix operator ':', pronounced "cons", the list constructor.
/
/ Informally, cons hitches an item on to the front of the list that follows.
/ Cons binds to the right in the same way as APL, with a binding strength less
/ than that of function application.
a = 0 : +0 : [] / Lists are constructed with cons and null,
a / and displayed in bracketed form.
[0,1]
b = [2,+2] / The display form may be used for input,
c = [a,b] / and lists may be nested.
c / A list of lists.
[[0,1],[2,3]]
(0:1:[]) : (2:3:[]) : [] / Alternative construction.
[[0,1],[2,3]]
[ / Expressions
· · [0,1], / · may be
· · [2,3] / · · input over
· ] / · · · several lines.
[[0,1],[2,3]]
/ We can use cons in function argument patterns to deconstruct lists.
h (x:y) = x / Head.
h [3,1,4]
3
t (x:y) = y / Tail.
t [3,1,4]
[1,4]
t (h c), h (t c) / ',' separates compound statements.
[1], [2,3]
j [] z = z / Join of two lists.
j (x:y) z = x : j y z
j [1,2,3] [4,5,6]
[1,2,3,4,5,6]
/ Max includes Min as a subset, so definitions may combine list and natural
/ number expressions. This function is the sum total of a list of numbers:
s [] = 0 / Sum total of list of natural numbers.
s (0:y) = s y
s (+x:y) = +(s(x:y))
s [1,2,3,4,5]
15
l [] = 0 / Length of list.
l (x:y) = +(l y)
l [[],[],[],[]] / Length of list of lists.
4
l [l,l,l] / Length of list of functions.
3
/ Max is a strongly typed language. Following an expression with :: displays its
/ type.
3 :: / The type of a natural number is "num".
#
[1,2,3] :: / List of natural numbers.
[#]
+ :: / Succ is a function from num to num.
#→#
s :: / Type of function Sum defined above.
[#]→#
l :: / Type of function Length.
[⍺]→#
j :: / Type of function Join.
[⍺]→[⍺]→[⍺]
[l,l,l] :: / List of functions.
[[⍺]→#]
/ Following :: with a type expression, declares the type of an object. For ex-
/ ample, Map applies its function first argument to each item of its list second
/ argument. It is similar to APL's primitive operator: each.
m :: (⍺→⍵)→[⍺]→[⍵] / Map.
m f [] = [] / Function mapped over null is null.
m f (h:t) = f h : m f t / Function of head, cons map function tail.
m + [0,1,2,3] / map succ over a list of numbers.
[1,2,3,4]
m (j [0]) [[1],[2],[3]] / map join [0] over a list of lists.
[[0,1],[0,2],[0,3]]
/ Fold applies its function first argument to successive pairs of items in its
/ list third argument. The second argument is an identity for the null list.
/ This version which folds from the right, is similar to APL's primitive oper-
/ ator: reduce.
f :: (⍺→⍵→⍵)→⍵→[⍺]→⍵ / Fold right.
f g i [] = i / Fold of null is identity.
f g i (h:t) = g h (f g i t) / function of head with fold of tail.
f j [] [[1,2],[3,4],[5,6]] / Fold join of a list of lists.
[1,2,3,4,5,6]
/ '.' pronounced "where", introduces a definition local to its preceding ex-
/ pression.
[x,x] . x=[1,2] / List of x's where x is a list of numbers.
[[1,2],[1,2]]
[y,y] . y=[x,x] . x=[1,2] / List of y's where y is a list of x's where ...
[[[1,2],[1,2]],[[1,2],[1,2]]]
/ Local definitions may be entered on following lines where indentation enhances
/ the legibility of the function:
r :: [⍺]→[⍺] / Reverse of list.
r = f [] / Reverse uses an auxiliary function: f,
. f x [] = x / whose first argument: x is an accumulator
. f x (y:z) = f (y:x) z / for the reversed list.
r [[1,2],[3,4],[5,6]] / reverse list.
[[5,6],[3,4],[1,2]]
m r [[1,2],[3,4],[5,6]] / map reverse over list.
[[2,1],[4,3],[6,5]]
/ Local definitions may be nested:
b c / Expression: b applied to c.
. b x = a (a x) / b local to expression.
. . a = + / a local to b.
. c = + a / c local to expression.
. . a = 0 / a local to c.
3
~~m / Retain only the Map function.
m
/ Radix n decode of list of digits:
r :: #→[#]→# / Radix n 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 → add base to next col.
r 2 [1,0,1,0,1,0] / binary decode.
42
d [1,2,3] / decimal decode.
. d = r (+9)
123
r h [2,0] / hex decode using
. h = r 8 [2,0] / oct decode.
32
/ Max's evaluation is lazy, so lists may be of infinite length.
z . z=0:z / Infinite list of Zeros.
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
n = q 0 / The Natural numbers.
. q i = i : q(+i)
n
[0,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,28,2
t :: #→[⍺]→[⍺] / First i items Taken from list.
t 0 y = [] / zero take: null.
t (+i) (x:y) = x : t i y / (i+1)th take: head cons i'th take.
d :: #→[⍺]→[⍺] / First i items Dropped from list.
d 0 y = y / zero drop: original list.
d (+i) (x:y) = d i y / (i+1)th drop: i'th drop of tail.
t 4 (d 3 n) / Section from natural numbers.
[3,4,5,6]
/ Zipwith: / A dyadic map function.
z :: (⍺→⍵→∊)→[⍺]→[⍵]→[∊] / Zip lists with function.
z f [] [] = [] / both lists null: null,
z f [] (x:y) = [] / first list null: null,
z f (a:b) [] = [] / second list null: null,
z f (a:b) (x:y) = f a x : z f b y / heads cons zipped tails.
z (l.lxy=[x,y]) n [3,1,4,1,5,9] / sequence zipped with index.
[[0,3],[1,1],[2,4],[3,1],[4,5],[5,9]]
z r n n / Zip with replicate: {⍵⍴⍵}¨⍳⌊/⍬
. r 0 a = [] / Replicate :: #→⍺→[⍺]
. r (+i) a = a : r i a
[[],[1],[2,2],[3,3,3],[4,4,4,4],[5,5,5,5,5],[6,6,6,6,6,6],[7,7,7,7,7,7,7],[8,8,
/ Combinators facilitate "tacit" definition:
b f g x = f (g x), b :: / Compositor.
(⍺→⍵)→(∊→⍺)→∊→⍵
c f g x = f x g, c :: / Permutator.
(⍺→⍵→∊)→⍵→⍺→∊
s f g x = f x (g x), s :: / Distributor, a.k.a. "Hook".
(⍺→⍵→∊)→(⍺→⍵)→⍺→∊
i = c t n / Tacit defn: first ⍵ natural numbers.
i 9 / ⍳9
[0,1,2,3,4,5,6,7,8]
m i n / Infinite sequence of sequences.
[[],[0],[0,1],[0,1,2],[0,1,2,3],[0,1,2,3,4],[0,1,2,3,4,5],[0,1,2,3,4,5,6],[0,1,
r [1,2,3] / Infinite Repetition of list items.
. r = s j r / Tacit definition of repeater.
. . j [] z = z / Join of two lists.
. . j (x:y) z = x : j y z
[1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,
)
Back to: contents