Module Belt_List

'a t is compatible with built-in list type

length xs

• returns

  the length of the list xs

See length

head xs returns None if xs is the empty list, otherwise it returns Some value where value is the first element in the list.

head [] = None ;;
head [1;2;3] = Some 1 ;;

headExn xs

See head

raise an exception if xs is empty

tail xs returns None if xs is empty; otherwise it returns Some xs2 where xs2 is everything except the first element of xs;

tail [] = None;;
tail [1;2;3;4] = Some [2;3;4];;

tailExn xs

See tail

raise an exception if xs is empty

add xs y adds y to the beginning of list xs

add [1] 3 = [3;1];;

get xs n

return the nth element in xs, or None if n is larger than the length

get [0;3;32] 2 = Some 32 ;;
get [0;3;32] 3 = None;;

getExn xs n

See get

raise an exception if n is larger than the length

make n v

• return a list of length n with each element filled with value v
• return the empty list if n is negative

make 3 1 =  [1;1;1]

makeBy n f

• return a list of length n with element i initialized with f i
• return the empty list if n is negative

makeBy 5 (fun i -> i) = [0;1;2;3;4];;
makeBy 5 (fun i -> i * i) = [0;1;4;9;16];;

shuffle xs

• returns

  a new list in random order

drop xs n

return the list obtained by dropping the first n elements, or None if xs has fewer than n elements

drop [1;2;3] 2 = Some [3];;
drop [1;2;3] 3 = Some [];;
drop [1;2;3] 4 = None;;

take xs n

return a list with the first n elements from xs, or None if xs has fewer than n elements

take [1;2;3] 1 = Some [1];;
take [1;2;3] 2 = Some [1;2];;
take [1;2;3] 4 = None;;

splitAt xs n split the list xs at position n return None when the length of xs is less than n

splitAt [0;1;2;3;4] 2 = Some ([0;1], [2;3;4])

concat xs ys

• returns

  the list obtained by adding ys after xs

  concat [1;2;3] [4;5] = [1;2;3;4;5]

concatMany a return the list obtained by concatenating in order all the lists in array a

concatMany [| [1;2;3] ; []; [3]; [4] |] = [1;2;3;3;4]

reverseConcat xs ys is equivalent to concat (reverse xs) ys

reverseConcat [1;2] [3;4] = [2;1;3;4]

flatten ls return the list obtained by concatenating in order all the lists in list ls

flatten [ [1;2;3] ; []; [3]; [4] ] = [1;2;3;3;4]

map xs f

return the list obtained by applying f to each element of xs

map [1;2] (fun x-> x + 1) = [3;4]

zip xs ys

• returns

  a list of pairs from the two lists with the length of the shorter list

  zip [1;2] [3;4;5] = [(1,3); (2,4)]

zipBy xs ys f

See zip

Equivalent to zip xs ys |> List.map (fun (x,y) -> f x y)

zipBy [1;2;3] [4;5] (fun a b -> 2 * a + b) = [6;9];;

mapWithIndex xs f applies f to each element of xs. Function f takes two arguments: the index starting from 0 and the element from xs.

mapWithIndex [1;2;3] (fun i x -> i + x) =
[0 + 1; 1 + 2; 2 + 3 ]

fromArray arr converts the given array to a list

fromArray [|1;2;3|]  = [1;2;3]

toArray xs converts the given list to an array

toArray [1;2;3] = [|1;2;3|]

reverse xs returns a new list whose elements are those of xs in reverse order.

reverse [1;2;3] = [3;2;1]

mapReverse xs f

Equivalent to reverse (map xs f)

mapReverse [3;4;5] (fun x -> x * x) = [25;16;9];;

forEach xs f Call f on each element of xs from the beginning to end. f returns unit, so no new array is created. Use foreach when you are primarily concerned with repetitively creating side effects.

forEach ["a";"b";"c"] (fun x -> Js.log("Item: " ^ x));;
(*  prints:
  Item: a
  Item: b
  Item: c
*)

let us = ref 0;;
forEach [1;2;3;4] (fun x -> us := !us + x);;
!us  = 1 + 2 + 3 + 4;;

forEachWithIndex xs f

forEach ["a";"b";"c"] (fun i x -> Js.log("Item " ^ (string_of_int i) ^ " is " ^ x));;
(*  prints:
  Item 0 is a
  Item 1 is b
  Item 2 is cc
*)

let total = ref 0 ;;
forEachWithIndex [10;11;12;13] (fun i x -> total := !total + x + i);;
!total  = 0 + 10 + 1 +  11 + 2 + 12 + 3 + 13;;

reduce xs f

Applies f to each element of xs from beginning to end. Function f has two parameters: the item from the list and an “accumulator”, which starts with a value of init. reduce returns the final value of the accumulator.

reduce [1;2;3;4] 0 (+) = 10;;
reduce [1;2;3;4] 10 (-) = 0;;
reduce [1;2;3;4] [] add = [4;3;2;1];

reduceWithIndex xs f

Applies f to each element of xs from beginning to end. Function f has three parameters: the item from the list and an “accumulator”, which starts with a value of init and the index of each element. reduceWithIndex returns the final value of the accumulator.

reduceWithIndex [1;2;3;4] 0 (fun acc x i -> acc + x + i) = 16;;

reduceReverse xs f

Works like reduce, except that function f is applied to each item of xs from the last back to the first.

reduceReverse [1;2;3;4] 0 (+) = 10;;
reduceReverse [1;2;3;4] 10 (-) = 0;;
reduceReverse [1;2;3;4] [] add = [1;2;3;4];;

mapReverse2 xs ys f

equivalent to reverse (zipBy xs ys f)

mapReverse2 [1;2;3] [1;2] (+) = [4;2]

forEach2 xs ys f stop with the shorter list

reduce2 xs ys init f

Applies f to each element of xs and ys from beginning to end. Stops with the shorter list. Function f has three parameters: an “accumulator” which starts with a value of init, an item from xs, and an item from ys. reduce2 returns the final value of the accumulator.

reduce2 [1;2;3] [4;5] 0 (fun acc x y -> acc + x * x + y) =  0 + (1 * 1 + 4) + (2 * 2 + 5);;
reduce2 [1;2;3] [4;5] [] (fun acc x y -> add acc (x + y) = [2 +5;1 + 4 ];; (*add appends at end *)

reduceReverse2 xs ys init f

Applies f to each element of xs and ys from end to beginning. Stops with the shorter list. Function f has three parameters: an “accumulator” which starts with a value of init, an item from xs, and an item from ys. reduce2 returns the final value of the accumulator.

reduceReverse2 [1;2;3] [4;5] 0 (fun acc x y -> acc + x * x + y) =  0 + (1 * 1 + 4) + (2 * 2 + 5);;
reduceReverse2 [1;2;3] [4;5] [] (fun acc x y -> add acc (x + y) = [1 + 4;2 + 5];; (*add appends at end *)

every xs p

• returns

  true if all elements satisfy p, where p is a predicate: a function taking an element and returning a bool.

  every [] (fun x -> x mod 2 = 0) = true;;
  every [2;4;6] (fun x -> x mod 2 = 0 ) = true;;
  every [1;-3;5] (fun x -> x > 0) = false;;

some xs p

• returns

  true if at least one of the elements in xs satifies p, where p is a predicate: a function taking an element and returning a bool.

  some [] (fun x -> x mod 2 = 0) = false ;;
  some [1;2;4] (fun x -> x mod 2 = 0) = true;;
  some [-1;-3;-5] (fun x -> x > 0) = false;;

every2 xs ys p returns true if predicate p xi yi is true for all pairs of elements up to the shorter length (i.e. min (length xs) (length ys))

every2 [1;2;3] [0;1] (>) = true;;
every2 [] [1] (fun  x y -> x > y) = true;;
every2 [2;3] [1] (fun  x y -> x > y) = true;;
every2 [0;1] [5;0] (fun x y -> x > y) = false;

some2 xs ys p returns true if p xi yi is true for any pair of elements up to the shorter length (i.e. min (length xs) (length ys))

some2 [0;2] [1;0;3] (>) = true ;;
some2 [] [1] (fun  x y -> x > y) =  false;;
some2 [2;3] [1;4] (fun  x y -> x > y) = true;;

cmpByLength l1 l2

Compare two lists solely by length. Returns -1 if length l1 is less than length l2, 0 if length l1 equals length l2, and 1 if length l1 is greater than length l2.

cmpByLength [1;2] [3;4;5;6] = -1;;
cmpByLength [1;2;3] [4;5;6] = 0;;
cmpByLength [1;2;3;4] [5;6] = 1;;

Compare elements one by one f x y. f returns

• a negative number if x is “less than” y
• zero if x is “equal to” y
• a positive number if x is “greater than” y The comparison returns the first non-zero result of f, or zero if f returns zero for all x and y. If all items have compared equal, but xs is exhausted first, return -1. (xs is shorter) If all items have compared equal, but ys is exhausted first, return 1 (xs is longer)

cmp [3] [3;7] (fun a b -> compare a b) = -1
cmp [5;3] [5] (fun a b -> compare a b)  = 1
cmp [|1; 3; 5|] [|1; 4; 2|] (fun a b -> compare a b) = -1;;
cmp [|1; 3; 5|] [|1; 2; 3|] (fun a b -> compare a b) = 1;;
cmp [|1; 3; 5|] [|1; 3; 5|] (fun a b -> compare a b) = 0;;

Attention: The total ordering of List is different from Array, for Array, we compare the length first and, only if the lengths are equal, elements one by one. For lists, we just compare elements one by one

eq xs ys eqElem check equality of xs and ys using eqElem for equality on elements, where eqElem is a function that returns true if items x and y meet some criterion for equality, false otherwise. eq false if length of xs and ys are not the same.

eq [1;2;3] [1;2] (=) = false ;;
eq [1;2] [1;2] (=) = true;;
eq [1; 2; 3] [-1; -2; -3] (fun a b -> abs a = abs b) = true;;

has xs eqFcn returns true if the list contains at least one element for which eqFcn x returns true

has [1;2;3] 2 (=) = true;;
has [1;2;3] 4 (=) = false;;
has [-1;-2;-3] 2 (fun a b -> abs a = abs b) = true;;

getBy xs p returns Some value for the first value in xs that satisifies the predicate function p; returns None if no element satisifies the function.

getBy [1;4;3;2] (fun x -> x mod 2 = 0) = Some 4
getBy [15;13;11] (fun x -> x mod 2 = 0) = None

keep xs p returns a list of all elements in xs which satisfy the predicate function p

keep [1;2;3;4] (fun x -> x mod 2 = 0) =
[2;4]

filter xs p returns a list of all elements in xs which satisfy the predicate function p

filter [1;2;3;4] (fun x -> x mod 2 = 0) =
[2;4]

• deprecated This function will soon be deprecated. Please, use `List.keep` instead.

keepWithIndex xs p returns a list of all elements in xs which satisfy the predicate function p

keepWithIndex [1;2;3;4] (fun _x i -> i mod 2 = 0)
=
[1;3]

filterWithIndex xs p returns a list of all elements in xs which satisfy the predicate function p

filterWithIndex [1;2;3;4] (fun _x i -> i mod 2 = 0)
=
[1;3]

• deprecated This function will soon be deprecated. Please, use `List.keepWithIndex` instead.

keepMap xs f applies f to each element of xs. If f xi returns Some value, then value is kept in the resulting list; if f xi returns None, the element is not retained in the result.

keepMap [1;2;3;4] (fun x -> if x mod 2 = 0 then Some (-x ) else None)
=
[-2;-4]

partition xs p creates a pair of lists; the first list consists of all elements of xs that satisfy the predicate function p; the second list consists of all elements of xs that do not satisfy p

partition [1;2;3;4] (fun x -> x mod 2 = 0) =
([2;4], [1;3])

unzip xs takes a list of pairs and creates a pair of lists. The first list contains all the first items of the pairs; the second list contains all the second items.

unzip [(1,2) ; (3,4)] = ([1;3], [2;4]);;
unzip [(1,2) ; (3,4) ; (5,6) ; (7,8)] = ([1;3;5;7], [2;4;6;8]);;

getAssoc xs k eq

return the second element of a pair in xs where the first element equals x as per the predicate function eq, or None if not found

getAssoc [ 1, "a"; 2, "b"; 3, "c"] 2 (=) = Some "b"
getAssoc [9, "morning"; 15, "afternoon"; 22, "night"] 3 (fun a b -> a mod 12 = b mod 12) = Some "afternoon"

hasAssoc xs k eq return true if there is a pair in xs where the first element equals k as per the predicate funtion eq

hasAssoc [1, "a"; 2, "b"; 3,"c"] 1 (=) = true;;
hasAssoc [9, "morning"; 15, "afternoon"; 22, "night"] 3 (fun a b -> a mod 12 = b mod 12) = true;;

removeAssoc xs k eq Return a list after removing the first pair whose first value is k per the equality predicate eq; if not found, return a new list identical to xs.

removeAssoc [1,"a"; 2, "b"; 3, "c" ] 1 (=) =
  [2, "b"; 3, "c"]
removeAssoc [1,"a"; 2, "b"; 3, "c" ] 99 (=) =
  [1, "a"; 2, "b"; 3, "c"]

setAssoc xs k v eq if k exists in xs by satisfying the eq predicate, return a new list with the key and value replaced by the new k and v; otherwise, return a new list with the pair k, v added to the head of xs.

setAssoc [1,"a"; 2, "b"; 3, "c"] 2 "x" (=) =
[1,"a"; 2, "x"; 3,"c"] ;; 

setAssoc [1,"a"; 3, "c"] 2 "b" (=) = 
[2,"b"; 1,"a"; 3, "c"]

setAssoc [9, "morning"; 3, "morning?!"; 22, "night"] 15 "afternoon"
  (fun a b -> a mod 12 = b mod 12) = [9, "morning"; 15, "afternoon"; 22, "night"]

Note carefully the last example! Since 15 mod 12 equals 3 mod 12, both the key and value are replaced in the list.

sort xs Returns a sorted list.

sort [5; 4; 9; 3; 7] (fun a b -> a - b) = [3; 4; 5; 7; 9]