/ 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,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,29,30,31,32,33,34,35,3 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,8,8,8,8,8,8],[9,9,9,9 / 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,2,3,4,5,6,7],[0,1,2,3 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,1,2,3,1,2,3,1,2,3,1,2 ) Back to: contents