||KRC prelude, D. A. Turner, April 2016 ||This is a new prelude written for the Unix version of KRC, mostly ||borrowed from the preludes of Miranda and/or Haskell abs :- takes the absolute value of a number, e.g. abs (-3) is 3; abs x = x, x >= 0 = -x all :- applied to a predicate (truth-valued function) and a list returns "TRUE" if the predicate holds for every element; all f = and . map f and :- applied to a list of truthvalues, takes the logical conjunction; and = foldr '&' "TRUE" any :- applied to a predicate and a list returns "TRUE" if the predicate is "TRUE" for at least one element of the list; any f = or . map f bool :- predicate, returns "TRUE" on the strings "TRUE" and "FALSE", "FALSE" on other values; bool x = x=="TRUE" | x=="FALSE" char :- predicate, true on strings of size one, false otherwise (defined in machine code); chr :- `chr n' is ascii character number n, e.g. chr 10 == "\n" (defined in machine code); cjustify :- applied to a number and a string, centre justifies the string in a field of the specified width; cjustify n x = cjustify' (n - printwidth x) x cjustify' :- used by cjustify; cjustify' n x = [spaces (n / 2),x,spaces ((n + 1) / 2)] curry :- converts a function that expects a 2-list into a function that takes its arguments one at a time; curry f a b = curry f [a,b] curry_ :- generic, converts a function expecting an n-list into the corresponding n-ary function. Example: curry = curry_ 2. Unlike generic uncurry, curry_ needs to be given n; curry_ 0 f = f [] curry_ n f = curry_' n f curry_' :- used by curry_, it is introduced to get round the rule that a KRC function must have the same number of formal parameters in each of its defining equations; curry_' n f a = curry_ (n-1) (f . (':' a)) concat :- applied to a list of lists, joins them into a single list with `++', e.g. concat [[1,2],[3,4]] = [1,2,3,4]; concat = foldr '++' [] const :- creates constant functions, e.g (const 3) is a function that always returns 3; const a b = a digit :- predicate, true on single digit strings; digit x = char x & "0" <= x <= "9" digitval :- returns the numeric value of a digit; digitval x = ord x - ord "0", digit x drop :- `drop n x' returns list x without its first n elements; drop n x = x, n <= 0 drop n [] = [] drop n (a:x) = drop (n - 1) x dropwhile :- `dropwhile f x' removes elements from the front of list x for which function f returns "TRUE"; dropwhile f [] = [] dropwhile f (a:x) = dropwhile f x, f a = a:x elem :- applied to a value and a list returns "TRUE" or "FALSE" as the value is or not present in the list; elem = flip member even :- predicate, true on even numbers; even n = n % 2 == 0 error :- applied to a printable value, terminates the program and prints the value with (!) on stderr. (defined in machine code); explode :- explodes a string into a list of characters (defined in machine code); filter :- applied to a predicate and a list returns a list of the elements for which the predicate takes value "TRUE"; filter f x = {a|a<-x;f a} flip :- converts a two-argument function into one that takes its arguments in the opposite order; flip f a b = f b a foldl :- folds up a list using a given binary operator and start value in a left associative way. Example: foldl op r [a,b,c] = op c (op b (op a r)) In order to run in constant space, foldl evaluates the accumulating result at each stage; foldl op s [] = s foldl op s (a:x) = strict (foldl op) (op a s) x foldl1 :- folds left over non-empty lists; foldl1 op (a:x) = foldl op a x foldr :- folds up a list using a given binary operator and start value in a right associative way. Example: foldr op r [a,b,c] = op a (op b (op c r)); foldr op s [] = s foldr op s (a:x) = op a (foldr op s x) foldr1 :- folds right over non-empty lists; foldr1 op [a] = a foldr1 op (a:b:x) = op a (foldr1 op (b:x)) function :- type testing predicate (defined in machine code); hd :- applied to a non empty list, returns its first element; hd (a:x) = a id :- is the identity function, applied to any object it returns it; id a = a implode :- takes a list of strings and joins them together to make a single string - the opposite of explode (defined in machine code); init :- applied to a non-empty list returns the list without its last element; init [a] = [] init (a:x) = a : init x interleave :- merges two lists into one by taking members from them alternately; interleave (a:x) y = a:interleave y x interleave [] y = y intersect :- returns a list of the common elements of two lists; intersect x y = filter (member x) y iterate :- (iterate f x) is the infinite list [x,f x,f(f x), ... ]; iterate f x = x : iterate f (f x) last :- applied to a non-empty list returns its last element; last x = x (#x-1) lay :- applied to a list formats it to have one element per line when printed with !; lay [] = [] lay (a:x) = show a:"\n":lay x layn :- similar to `lay', but produces output with numbered lines; layn x = layn' 1 x layn' :- (layn' n x) formats list x one element per line with lines numbered starting at n; layn' n [] = [] layn' n (a:x) = rjustify 4 n:") ":show a:nl:layn' (n + 1) x length :- a function with same action as unary `#'; length x = #x letter :- predicate, true on single letter strings; letter x = uppercase x | lowercase x limit :- finds the fixed point, if any, of a function repeatedly applied to an initial value; limit f x = limit f (f x), f x \= x = x list :- type testing predicate (defined in machine code); listdiff :- defines the action of the "--" operator; listdiff [] y = [] listdiff x [] = x listdiff (a:x) (b:y) = listdiff x y, a == b = listdiff (a:listdiff x [b]) y ljustify :- applied to a number and a string, left justifies the string in a field of the specified width; ljustify n x = [x,spaces (n - printwidth x)] lowercase :- predicate, true on lowercase letters; lowercase x = char x & ord "a" <= ord x <= ord "z" map :- applied to a function and a list returns the list obtained by applying the function to each element; map f x = {f a|a<-x} max :- returns the greater of two numbers or two strings under '>='; max a b = a, a>=b = b maximum :- of a list of numbers or strings returns the greatest; maximum = foldl1 max member :- applied to a list and a value returns "TRUE" or "FALSE" as the value is or not present in the list; member [] a = "FALSE" member (a:x) b = a == b | member x b merge :- of two ordered lists merges them to a single ordered list; merge x [] = x merge [] y = y merge (a:x) (b:y) = a:merge x (b:y), a <= b = b:merge (a:x) y min :- returns the lesser of two numbers or two strings under '<='; min a b = a, a<=b = b minimum :- of a list of numbers or strings returns the least; minimum = foldl1 min mkset :- removes duplicate elements from a list, takes time quadratic in the length of the list; mkset x = mkset' x [] mkset' :- used by mkset; mkset' [] y = [] mkset' (a:x) y = mkset' x y, member y a = a:mkset' x (a:y) neg :- a function with same action as unary `-'; neg x = -x nl :- newline; nl = chr 10 not :- a function with same action as unary `\'; not x = \x np :- newpage; np = chr 12 number :- type testing predicate (defined in machine code); odd :- predicate, true on odd numbers; odd n = \even n or :- applied to a list of truthvalues, takes their logical disjunction; or = foldr '|' "FALSE" ord :- converts a character to its ascii number, e.g. ord "\n" == 10 (defined in machine code); printwidth :- for any value returns its width on printing with "!", width meaning number of characters (defined in machine code); product :- applied to list of numbers returns their product; product = foldl '*' 1 quote :- quotation mark; quote = chr 34 read :- takes a file or device name and returns a list of characters (defined in machine code); rep :- `rep n x' produces a list with n elements all of which are x; rep n x = take n (repeat x) repeat :- `repeat x' produces an infinite list of x's; repeat x = x : repeat x reverse :- applied to a list returns a list of the same elements in reverse order; reverse = foldl ':' [] rjustify :- applied to a number and a string, right justifies the string in a field of the specified width; rjustify n x = [spaces (n - printwidth x),x] seq :- `seq x y' evaluates x and returns y (defined in machine code); show :- applied to any (non-function) value formats it to show its structure when printed with !; show x = x, number x = ["\"",map showchar (explode x),"\""], string x show [] = "[]" show (a:x) = ["[",show a,{[",",show b]|b<-x},"]"] showchar :- part of the workings of `show', for use on strings; showchar c = c, 32 <= ord c < 127 showchar "\a" = "\\a" showchar "\b" = "\\b" showchar "\f" = "\\f" showchar "\n" = "\\n" showchar "\r" = "\\r" showchar "\v" = "\\v" showchar "\\" = "\\\\" showchar "\"" = "\\\"" showchar c = ["\\",ord c] sort :- of a list of numbers or strings returns an ordered list of the same elements. This version of merge-sort is due to Ian Lynagh; sort = sort' . map (flip ':' []) sort' :- used by sort; sort' [] = [] sort' [x] = x sort' xs = sort' (sort'' xs) sort'' :- used by sort, Ian Lynagh calls this function merge_pairs; sort'' [] = [] sort'' [x] = [x] sort'' (x:y:xs) = merge x y : sort'' xs spaces :- applied to a number returns a list of that many spaces; spaces 0 = [] spaces n = " ":spaces (n - 1) strict :- applied to a function returns a version of the function that always evaluates its argument; strict f x = seq x (f x) string :- type testing predicate (defined in machine code); sum :- applied to list of numbers returns their sum; sum = foldl '+' 0 tab :- horizontal tab; tab = chr 9 take :- `take n x' returns a list of the first n elements of list x; take n x = [], n <= 0 take n [] = [] take n (a:x) = a : take (n - 1) x takewhile :- `takewhile f x' takes elements from the front of list x for which function f returns "TRUE"; takewhile f [] = [] takewhile f (a:x) = a : takewhile f x, f a = [] tl :- applied to a non-empty list returns the list without its first element; tl (a:x) = x uncurry :- generic uncurry, converts an n-ary function into a function that takes its arguments as an n-list; uncurry f [] = f uncurry f (a:x) = uncurry (f a) x union :- returns a merger of two lists with duplicates removed; union x y = mkset (interleave x y) until :- of predicate, function and value, applies the function to the value until the predicate is satisfied; until f g x = x, f x = until f g (g x) uppercase :- predicate, true on uppercase letters; uppercase x = char x & ord "A" <= ord x <= ord "Z" vt :- vertical tab; vt = chr 11 write :- used to mark items to be sent to a file on output with ! write "filename" x where x is any KRC data item. (defined in machine code); zip :- applied to a list of lists, returns the matrix transpose i.e. rows and columns are interchanged. Example zip [[1,2,3],[4,5,6]] = [[1,4],[2,5],[3,6]] also accepts upper triangular matrices, e.g. zip [[1,2,3],[4,5],[6]] = [[1,4,6],[2,5],[3]]; zip x = zip' (takewhile ('\=' []) x) zip' :- used by zip; zip' x = [], x==[] = map hd x : zip (map tl x) zipwith :- applies an n-ary function to each row of a matrix with n columns. Taking a 3-ary function f as example zipwith f [x,y,z] = [f (x 0) (y 0) (z 0), f (x 1) (y 1) (z 1), ... ]; zipwith f xss = map (uncurry f) (zip xss)