open List (* [last xs] returns the last element of the nonempty list [xs]. *) let rec last1 x xs = match xs with | [] -> x | x :: xs -> last1 x xs let last xs = match xs with | [] -> assert false | x :: xs -> last1 x xs (* [interval i j] constructs a list representation of the semi-open interval [i..j). *) let rec interval i j : int list = if i < j then i :: interval (i + 1) j else [] (* [init i j f] constructs a list of the values [f i] up to [f (j - 1)]. *) let init i j (f : int -> 'a) : 'a list = map f (interval i j) (* [is_matrix m n xss] checks that [xss] is an [m]-by-[n] matrix, represented as a list of lists. *) let is_matrix m n (xss : _ list list) = length xss = m && for_all (fun xs -> length xs = n) xss (* [transpose n xss] transposes a matrix, represented as a list of lists. The parameter [n] is the width of the matrix, and is really useful only in the case where the matrix has zero height, in which case [transpose] constructs a matrix of height [n] and zero width. *) let transpose (n : int) (xss : 'a list list) : 'a list list = let m = length xss in assert (is_matrix m n xss); (* Convert [xss] to an array, for speed. *) let xss : 'a array array = Array.(map of_list (of_list xss)) in (* We have an [m]-by-[n] matrix, and construct an [n]-by-[m] matrix. *) init 0 n (fun j -> init 0 m (fun i -> xss.(i).(j) ) ) (* [hextend xs n f] extends the vertical vector [xs] to a matrix of width [n]. A vector element [x] is turned into [f j x] in the [j]-th row. *) let hextend (xs : 'a list) (n : int) (f : int -> 'a -> 'a) : 'a list list = map (fun x -> init 0 n (fun j -> f j x)) xs (* [uniq cmp xs] assumes that the list [xs] is sorted according to the ordering [cmp] and returns the list [xs] deprived of any duplicate elements. *) let rec uniq1 cmp x ys = match ys with | [] -> [] | y :: ys -> if cmp x y = 0 then uniq1 compare x ys else y :: uniq1 cmp y ys let uniq cmp xs = match xs with | [] -> [] | x :: xs -> x :: uniq1 cmp x xs (* [weed cmp xs] returns the list [xs] deprived of any duplicate elements. *) let weed cmp xs = uniq cmp (List.sort cmp xs) (* [fold_right1] is like [fold_right], but uses the last element of the list (if the list is nonempty) as the initial accumulator, saving one call to the binary operation [f]. This is equivalent to [fold_right] if [accu] is a right unit for [f]. *) let fold_right1 f xs accu = match List.rev xs with | [] -> accu | x :: xs -> let xs = List.rev xs in (* We have decomposed [xs] as [xs] followed with [x]. We can now ignore [accu] and use [x] as the initial accumulator in our right-to-left sweep of the list. *) List.fold_right f xs x (* [fold_left1] is like [fold_left], but uses the first element of the list (if the list is nonempty) as the initial accumulator, saving one call to the binary operation [f]. This is equivalent to [fold_left] if [accu] is a left unit for [f]. *) let fold_left1 f accu xs = match xs with | [] -> accu | x :: xs -> (* We can ignore [accu] and use [x] as the initial accumulator in our left-to-right sweep of the list. *) List.fold_left f x xs (* [filter2 f xs ys] returns the list of elements [y] in [ys] such that the corresponding element [x] in [xs] satisfies [f]. *) let filter2 f xs ys = assert (length xs = length ys); map snd (filter (fun (x, _y) -> f x) (combine xs ys))