Module Prelude.Lists

len is List.length.

comparison is Stdlib.List.compare.

(to_string ?left ?sep ?right f xs) returns a string representation of xs.

f is used for the string representation of each element of xs.

The representation of the list is inserted between ?left (default: "[") and ?right (default: "]"); each element of xs is separated by ?sep (default: "; ").

Example: (to_string string_of_int (1--10)) = "[1; 2; 3; 4; 5; 6; 7; 8; 9; 10]"

(hd xs) is the first element of xs.

• raises Failure

  if the list is empty.

(head xs) is None if (xs = []) and (Some (hd xs)) otherwise.

(init xs) is all the elements of xs except the last one; tail-recursive

(init xs) = (rev $ tl $ rev) 

• raises Failure

  if the list is empty.

(tl (x::xs)) is xs.

• raises Failure

  if the list is empty.

(tail xs) is None if (xs = []) and (Some (tl xs)) otherwise.

(last xs) is the last element of xs; tail-recursive.

(last xs) = (hd (rev xs)) 

• raises Failure

  if the list is empty.

(get) is (flip List.nth).

cons is List.cons.

snoc is (flip cons).

(consup x) is (x::[]).

(revcons) is (xs @ [x]).

(unfoldr p f g x) builds a list (f x :: unfoldr p f g (g x)) from a seed value x until ((p x) = true). Not tail-recursive.

Example:

• (unfoldr ((=) 0) id pred 10) = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1]

(make n f) is [f 0; f 1; ...; f (n-1)], evaluated left to right. Tail-recursive.

Example: a list of 10 random integers in the range 0-99:

make 10 (fun _ -> Random.int 100) 

(repeat n x) is the list of exactly n x's.

trappend is a tail-recursive List.append.

(prepend xs ys) prepends xs onto the front of ys and is another name for List.append.

(postpend xs ys) postpends xs onto the end of ys and is the same as (flip List.append).

(scanl f z list) is similar to foldl, but returns a list of successive reduced values from the left:

scanl (±) z [x1; x2; ...] = [z; z ± x1; (z ± x1) ± x2; ...] 

Invariant: (last (scanl f z xs)) = (foldl f z xs)

(eachpair f list) applies f to each consecutive pair of elements in list.

Example: (eachpair f [1;2;3;4]) = (f 1 2 :: f 2 3 :: f 3 4 :: [])

Invariants:

• ∀f.(eachpair f []) = []
• ∀f.∀x.(eachpair f [x]) = []
• ∀f.∀xs.xs = [] || (len (eachpair f xs)) = (len xs - 1)

(permutations xs) is the list of all permutations of xs; not tail-recursive. O(n!).

• author Michel Quercia

(upto m n) is the list of ints in the interval [m,n] (tail-recursive).

(upto 1 5) = [1; 2; 3; 4; 5].

(--) is upto.

(1--5) = [1; 2; 3; 4; 5]

(random ?size r ()) is a list of size (size ()) (default: < 100); the elements are given by (r ()).

(null xs) is true iff (xs = []).

empty is null.

(nonempty xs) is true iff (not (null xs)).

(singleton xs) is true iff (len xs = 1), O(1).

(many xs) is true iff (len xs > 1), O(1).

(prefix pat subj) is true if pat is a prefix of subj and false otherwise.

Invariants:

• ∀xs : (prefix [] xs) = true
• ∀xs : (prefix xs xs) = true
• ∀xs : (xs = [] || prefix (init xs) xs) = true

foldl is List.fold_left.

(foldr f z xs) is (List.fold_right f xs z).

This order of parameters is much more useful in conjunction with the (|>)-operator.

foldl1 is foldl with no initial accumulator value, and thus must be applied to non-empty lists.

• raises Invalid_argument

  if the list is empty.

foldr1 is foldr with no initial accumulator value, and thus must be applied to non-empty lists.

• raises Invalid_argument

  if the list is empty.

foldl2 is List.fold_left2.

foldr2 is List.fold_right2.

(foldwise ?skip n f init xs) left-fold f across sequential non-overlapping n-wise subsequences of xs; tail-recursive.

For example, (foldwise 2) is a pairwise fold:

 foldwise 2 (snocwith rev) [] (1--12) |> rev
= [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]; [11; 12]] 

f is given an accumulator and a sublist of length n. For efficiency, the sublists passed to f will be in the reverse of the order in which they occur in xs; f can reverse them if necessary.

Unless skip is true, f must be prepared to receive a final sublist of length less than n if the length of xs is not evenly divisible by n.

If (skip = true), only the initial (len xs - ((len xs) mod n)) elements of xs will be processed.

Invariants:

• (foldwise n (snocwith rev) [] xs |> rev |> flatten) = xs
• (foldwise n ~skip:false f init (take (len xs - len xs mod n) xs)) = (foldwise n ~skip:true f init xs)

(conswith f) is (cons <? f) and also (fun x xs -> f x :: xs).

(conswhen p x xs) is (cons x xs) when p x = true and otherwise is xs.

foldr (conswhen Int.even) [] (1--10) = [2; 4; 6; 8; 10] 

(snocwith f) is (flip (conswith f)). Suitable for foldl.

(fun f -> foldl (snocwith f) [] $ rev) is a tail-recursive map.

(snocwhen p) is (flip (conswhen p)). Suitable for foldl.

concat is List.concat.

(anded bools) is the conjunction of the Booleans in bools.

(ored bools) is the disjunction of the Booleans in bools.

(conjunction ps x) is the conjunction of the predicates in ps.

(disjunction ps x) is the disjunction of the predicates in ps.

(all p xs) is true if (p x) for all of the xs.

Invariant:

• (all p xs) = (map p xs |> anded)

(any p xs) is true if (p x) for any of the xs.

Invariant:

• ∀p : ∀xs : (any p xs) = (map p xs |> ored)

(sum xs) is the sum of the ints in xs.

(product xs) is the product of the ints in xs.

(maximumBy compare xs) is the maximum of the xs according to compare.

Examples:

• maximumBy compare (1--10) = 10 

• maximumBy compare ["zap";"foo"] = "zap" 

• maximumBy compare ["ZAP";"foo"] = "foo" 

• maximumBy AIString.compare ["ZAP";"foo"] = "ZAP" 

• maximumBy AIString.compare ["zap";"foo"] = "zap" 

• raises Invalid_argument

  if the list is empty.

maximum is (maximumBy compare).

Examples:

• maximum (1--10) = 10 

• maximum ["zap";"foo"] = "zap" 

• maximum  ["ZAP";"foo"] = "foo" 

• raises Invalid_argument

  if the list is empty.

(minimum ?compare xs) is the minimum of the xs. If provided, compare is used for comparison (default: polymorphic minimum via min).

Examples:

• minimum (1--10) = 1 

• minimum ["zap";"foo"] = "foo" 

• minimum  ["ZAP";"foo"] = "ZAP" 

• minimum ~compare:AIString.compare ["ZAP";"foo"] = "foo" 

• minimum ~compare:AIString.compare ["zap";"foo"] = "foo" 

• raises Invalid_argument

  if the list is empty.

(break eq list) does control-break processing on the (typically sorted) list, grouping together consecutive subsequences of elements which are equal under eq.

N.B. For the sake of efficiency, the result is in reverse order, as are all the sublists. (List.rev_map rev) will restore order.

Example: this function:

• (break (fun p x -> p.[0] = x.[0]))

will group a sorted list of words into lists of words that begin with the same letter.

["copulatives"; "cumulative"; "deliverable"; "denial"; "drowning";
"folklorists"; "gradualism"; "lowliest"; "orangeade"; "oxen"]
|> break (fun p x -> p#!0 = x#!0) |> List.rev_map rev
= [["copulatives"; "cumulative"]; ["deliverable"; "denial"; "drowning"];
["folklorists"]; ["gradualism"]; ["lowliest"]; ["orangeade"; "oxen"]] 

rev is List.rev.

map is List.map.

trmap is a tail-recursive map.

mapi is List.mapi.

map2 is List.map2.

(flatmap f) is a tail-recursive (map f $ concat).

• author Matt Teichman

filter is List.filter.

(delete ?eq x xs) removes the first occurrence of x from xs; tail recursive.

(replace sub rep xs) replaces each occurrence of sub in xs with rep.

Examples:

• (replace 1 10 (1--6)) = [10; 2; 3; 4; 5; 6]
• (replace 10 20 (1--6)) = [1; 2; 3; 4; 5; 6]
• ((1--6) |> map (flip (mod) 2) |> replace 0 2) = [1; 2; 1; 2; 1; 2]

(behead prefix list) is the remainder of list when the leading prefix is removed.

prefix must be an exact prefix of list for anything to be removed.

Invariants:

• (behead [] xs) = xs
• (behead xs []) = []
• (behead xs xs) = []
• (behead (x::xs) xs) = xs
• (len (behead xs ys)) <= (len ys)
• (prefix xs ys) && (behead xs ys) <> ys

(prefixes xs) is the list of all prefixes of xs.

(prefixes [1;2;3]) = [[]; [1]; [1; 2]; [1; 2; 3]] 

Invariants:

• (prefixes xs) = (scanl snoc [] xs |> map rev)
• (prefixes xs |> map (flip prefix xs) |> anded) = true
• (prefixes xs |> hd) = []

(suffixes xs) is the list of all suffixes of xs.

(suffixes [1;2;3]) = [[]; [3]; [2; 3]; [1; 2; 3]]  

Invariant: (suffixes xs |> hd) = []

(intersperse x xs) inserts x between the elements of xs.

Example: String.(explode "123456" |> intersperse ',' |> implode) = "1,2,3,4,5,6"

Invariants:

• (intersperse x []) = []
• (intersperse x [y]) = [y]

(pad ?(left=false) ~def n xs) pads xs on the right (or on the left, if (left = true)) with enough instances of def such that the length of the result is at least n.

If you need the result list to be exactly of length n (never longer), use:

• (take n $ pad ~def n)

Invariant: (len (pad ~left ~def n xs) = max n (len xs))

(transpose ?def xss) is the transposition of the rows and columns of xss; tail recursive.

Unless def is provided, if any sublist is shorter than the first sublist, (Invalid_argument _) is raised. Otherwise, the resulting sublists will all be of length (len (nth xss 0)).

If def is provided, it serves as a default element that is appended as needed to bring all lists to the length of the longest list in xss; in this case, the "matrix" is guaranteed to be rectangular and no exception will be raised.

Examples:

• transpose [1--3;4--6] = [[1; 4]; [2; 5]; [3; 6]]
• transpose [[1];[1;2]] = [[1; 1]]
• catch transpose [[1;2];[1]] = None
• transpose ~def:0 [[1;2];[1]] = [[1; 1]; [2; 0]]

(evens xs) is all the elements of xs at even indexes.

• evens [1; 3; 5] = [1; 5]
• evens ["a"; "b"; "c"] = ["a"; "c"]

(odds xs) is all the elements of xs at odd indexes.

• odds [0; 2; 4] = [2]
• odds ["a"; "b"; "c"] = ["b"]

(splitat n xs) is (a,b) such that a is the length-n prefix of xs, and b is the remainder of the xs.

It is equivalent to (take n xs, drop n xs), but makes only one pass.

Invariant:

• let a,b = splitat n xs in prefix a xs && (a @ b) = xs

Examples:

• splitat 3 [1;2;3;4;5] = [1;2;3], [4;5]
• splitat 1 [1;2;3] = [1], [2;3]
• splitat 3 [1;2;3] = [1;2;3], []
• splitat 4 [1;2;3] = [1;2;3], []
• splitat 0 [1;2;3] = [], [1;2;3]
• splitat ~-1 [1;2;3] = [], [1;2;3]

(everyother xs) is the list consisting of every other element of xs, starting with the first; O(n), 1-pass algorithm.

Invariants:

• (len (everyother xs) = if even (len xs) then len xs / 2 else len xs / 2 + 1)
• (hd (everyother xs) = hd xs)

(take n xs) is (splitat n >> fst).

Invariant: (take n xs) = (drop (len xs - n) (rev xs) |> rev)

(drop n xs) is (splitat n >> snd).

Invariant: (drop n xs) = (take (len xs - n) (rev xs) |> rev)

(takeall n list) returns the sequential sublists of length n in list.

If n <= 0, the empty list is returned.

Invariant:

• ∀n . n>0 : (takeall n xs |> concat) = xs

Example:

• (takeall 3 (1--10)) = [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]; [10]]

(splitwhile p xs) is (a,b) where a is the longest prefix of xs of elements that satisfy p and b is the remaining suffix..

Invariant:

• splitwhile p xs |> fun (a,b) -> a@b = xs

(takewhile p) is (splitwhile p >> fst)

Invariant:

• (takewhile p xs @ dropwhile p xs) = xs

(dropwhile p xs) is (splitwhile p >> snd).

Invariant:

• ∀xs : ∀p : (takewhile p xs @ dropwhile p xs) = xs

mem is List.mem.

one_of is (flip List.mem).

partition is Lists.partition.

(zip xs ys) takes two lists and returns a list of corresponding pairs; tail-recursive.

This is the same as List.combine, except that if one input list is short, excess elements of the longer list are discarded, rather than raising an exception.

Examples:

• (zip (1--4) (5--8)) = [(1, 5); (2, 6); (3, 7); (4, 8)]
• (zip (1--2) (5--8)) = [(1, 5); (2, 6)]

(zipwith f xs ys) is zip xs ys |> map (uncurry f).

(unzip xs) is List.split: it transforms a list of pairs into a list of first components and a list of second components.

Invariant:

• (zip xs ys |> unzip) = (xs,ys) iff (len xs = len ys)

Functions for working with association lists (alists).

(sorted cmp list) is true iff (sort cmp list = list) and is false otherwise; O(n); tail-recursive, constant space.

sorted terminates at the first out-of-order value (if any), so it's much faster than (sort cmp list = list), especially for unsorted lists.

(uniq ?compare list) is the list of representative elements of the identical subsequences of xs; tail-recursive.

It's like sort_uniq but gives a different result for unsorted inputs.

Example:

• (uniq [1;1;2;3;3;3;3;2;2;3;3]) = [1; 2; 3; 2; 3]

Invariant:

• ∀xs : (sort compare xs |> uniq ~compare) = (sort_uniq compare xs)

• parameter compare

  the comparison function (default: compare)

(uniqc ?compare xs) is like (uniq xs) but each element is paired with the size of the original subsequence; tail-recursive.

Example:

• (uniqc [1;1;2;3;3;3;3]) = [(2, 1); (1, 2); (4, 3)]

• parameter compare

  the comparison function (default: compare)

(index ?z list) is an alist whose keys are successive integers (starting from z (default: 0) and whose values are the elements of list; tail-recursive.

Examples:

• (index (1--4)) = [(0, 1); (1, 2); (2, 3); (3, 4)]
• (index ~z:1 (1--4)) = [(1, 1); (2, 2); (3, 3); (4, 4)]

(pos x xs) is the position (index) of the first x in xs, or -1 if x is NOT in xs; tail-recursive.

(project ?relaxed is xs) projects the elements of xs indexed by the indices in is; tail-recursive in the length of is.

The result is in the order of the occurrence of the indices in is.

If any index in is >= (len xs) or < 0, Not_found is raised, unless ~relaxed:true, in which case any bad indices are ignored, and the length of the result may be less than the length of is.

Examples:

• (project [10] (1--20)) = [11]
• (project [3;2;1;0] (1--4)) = [4; 3; 2; 1]
• (project [4;4;4] (1--10)) = [5; 5; 5]

Invariants:

• ((project ~relaxed:false is xs) |> len) = (len is)
• ((project ~relaxed:false is []) && is <> []) = ⊥
• (project ~relaxed:true is []) = []
• (project [] xs) = []
• ∀n . n < 1 let xs = 1--n in (project (map pred xs) xs) = xs
• (project is xs) = (map (List.nth xs) is)

• raises Not_found

  if not relaxed and any index >= (len xs) or < 0

(nub ?compare xs) is the list xs with equal elements removed; tail-recursive; O(n log n).

Equality is determined by compare (default: Stdlib.compare).

The order of the elements in xs is not preserved.

Runs in constant heap space (in addition to the size of the result list) and logarithmic stack space.

nub (1--5 @ 1--3 @ 4--6) = [1; 2; 3; 4; 5; 6]

nub2 is nub but the order of the elements of the list is preserved; not tail-recursive; O(n^2).)

The 2 in nub2 is a reminder that it's O(n^2).

(union ?compare xs ys) returns the list union of the two lists (with no duplicates); not tail-recursive (length of the first argument).

Equality is determined by compare (default: Stdlib.compare).

The order of the elements in xs and ys is not preserved.

• (union xs ys) = (xs @ ys |> nub)

(intersect ?compare xs ys) returns the list intersection of the two lists; tail-recursive; O(n^2).

Equality is determined by compare (default: Stdlib.compare).

The order of the elements in xs and ys is not preserved.

(subset ?compare xs ys) is true if xs is a subset of ys; O(n^2).

Equality is determined by compare (default: Stdlib.compare).

The order of the elements in xs and ys is not preserved.

(diff ?compare xs ys): list difference: the elements of xs minus all of the elements in ys; tail-recursive, O(n^2).

Equality is determined by compare (default: Stdlib.compare).

The order of the elements in xs and ys is not preserved.

(cartesian_product xss) is the Cartesian product of the list of lists xss; not tail-recursive.

Deck of cards:

(cartesian_product [["♠";"♥";"♦";"♣"];("A"::map string_of_int (2--10)@["J";"Q";"K"])]) 

(powerset xs) is the list of all sublists of xs, including [] and xs itself; not tail-recursive.

(combinations n lst) is the list of all subset lists of lst consisting of n elements; not tail-recursive.

• author Matt Teichman

iter is iter.

iteri is iteri.

iter2 is iter2.

(bind list f) is (flatten (map f list)).

(return n) is [n].

Infix and prefix operators.