module Core_list:sig
..end
type'a
t ='a list
compare
on lists is lexicographic.val typerep_of_t : 'a Typerep_lib.Std.Typerep.t -> 'a t Typerep_lib.Std.Typerep.t
val typename_of_t : 'a Typerep_lib.Std.Typename.t -> 'a t Typerep_lib.Std.Typename.t
include Container.S1
include Monad.S
val of_list : 'a t -> 'a t
of_list
is the identity function. It is useful so that the List
module matches
the same signature that other container modules do, namely:
val of_list : 'a List.t -> 'a t
val nth : 'a t -> int -> 'a option
val nth_exn : 'a t -> int -> 'a
n
-th element of the given list.
The first element (head of the list) is at position 0.
Raise if the list is too short or n
is negative.val rev : 'a t -> 'a t
val rev_append : 'a t -> 'a t -> 'a t
List.rev_append l1 l2
reverses l1
and concatenates it to l2
. This is equivalent
to (
List.rev
l1) @ l2
, but rev_append
is more efficient.val unordered_append : 'a t -> 'a t -> 'a t
List.unordered_append l1 l2
has the same elements as l1 @ l2
, but in some
unspecified order. Generally takes time proportional to length of first list, but is
O(1) if either list is empty.val rev_map : 'a t -> f:('a -> 'b) -> 'b t
List.rev_map l ~f
gives the same result as
List.rev
(
ListLabels.map
f l)
, but is more efficient.val fold_left : 'a t -> init:'b -> f:('b -> 'a -> 'b) -> 'b
fold_left
is the same as fold
, and one should always use fold
rather than
fold_left
, except in functors that are parameterized over a more general signature
where this equivalence does not hold.val iter2_exn : 'a t -> 'b t -> f:('a -> 'b -> unit) -> unit
List.iter2_exn [a1; ...; an] [b1; ...; bn] ~f
calls in turn
f a1 b1; ...; f an bn
.
Raise if the two lists have different lengths.val rev_map2_exn : 'a t -> 'b t -> f:('a -> 'b -> 'c) -> 'c t
List.rev_map2_exn l1 l2 ~f
gives the same result as
List.rev (List.map2_exn l1 l2 ~f)
, but is more efficient.val fold2_exn : 'a t -> 'b t -> init:'c -> f:('c -> 'a -> 'b -> 'c) -> 'c
List.fold2_exn ~f ~init:a [b1; ...; bn] [c1; ...; cn]
is
f (... (f (f a b1 c1) b2 c2) ...) bn cn
.
Raise if the two lists have different lengths.val for_all2_exn : 'a t -> 'b t -> f:('a -> 'b -> bool) -> bool
List.for_all
, but for a two-argument predicate.
Raise if the two lists have different lengths.val exists2_exn : 'a t -> 'b t -> f:('a -> 'b -> bool) -> bool
List.exists
, but for a two-argument predicate. Raise
if the end of one list is reached before the end of the other.val filter : 'a t -> f:('a -> bool) -> 'a t
filter l ~f
returns all the elements of the list l
that satisfy the predicate p
.
The order of the elements in the input list is preserved.val rev_filter : 'a t -> f:('a -> bool) -> 'a t
filter
, but reverses the order of the input listval filteri : 'a t -> f:(int -> 'a -> bool) -> 'a t
val partition_map : 'a t ->
f:('a -> [ `Fst of 'b | `Snd of 'c ]) -> 'b t * 'c t
partition_map t ~f
partitions t
according to f
.val partition_tf : 'a t -> f:('a -> bool) -> 'a t * 'a t
partition_tf l ~f
returns a pair of lists (l1, l2)
, where l1
is the list of all the
elements of l
that satisfy the predicate p
, and l2
is the list of all the
elements of l
that do not satisfy p
. The order of the elements in the input list
is preserved. The "tf" suffix is mnemonic to remind readers at a call that the result
is (trues, falses).val split_n : 'a t -> int -> 'a t * 'a t
split_n n [e1; ...; em]
is ([e1; ...; en], [en+1; ...; em])
. If n > m
,
([e1; ...; em], [])
is returned. If n < 0
, ([], [e1; ...; em])
is
returned.val sort : cmp:('a -> 'a -> int) -> 'a t -> 'a t
Pervasives.compare
is a suitable comparison
function.
The current implementation uses Merge Sort. It runs in linear heap space and logarithmic stack space.
Presently, the sort is stable, meaning that two equal elements in the input will be in
the same order in the output.
val stable_sort : cmp:('a -> 'a -> int) -> 'a t -> 'a t
val merge : 'a t -> 'a t -> cmp:('a -> 'a -> int) -> 'a t
l1
and l2
are sorted according to the comparison
function cmp
, merge cmp l1 l2
will return a sorted list containing all the
elements of l1
and l2
. If several elements compare equal, the elements of l1
will be before the elements of l2
.val hd : 'a t -> 'a option
val tl : 'a t -> 'a t option
val hd_exn : 'a t -> 'a
val tl_exn : 'a t -> 'a t
val findi : 'a t -> f:(int -> 'a -> bool) -> (int * 'a) option
val find_exn : 'a t -> f:('a -> bool) -> 'a
find_exn t ~f
returns the first element of t
that satisfies f
. It raises
Not_found
if there is no such element.val append : 'a t -> 'a t -> 'a t
append [1; 2] [3; 4; 5]
is [1; 2; 3; 4; 5]
val map : 'a t -> f:('a -> 'b) -> 'b t
List.map f [a1; ...; an]
applies function f
to a1, ..., an
, and builds the list
[f a1; ...; f an]
with the results returned by f
.val concat_map : 'a t -> f:('a -> 'b t) -> 'b t
concat_map t ~f
is concat (map t ~f)
, except that there is no guarantee about the
order in which f
is applied to the elements of t
.val concat_mapi : 'a t -> f:(int -> 'a -> 'b t) -> 'b t
concat_mapi t ~f
is like concat_map, but passes the index as an argumentval map2_exn : 'a t -> 'b t -> f:('a -> 'b -> 'c) -> 'c t
List.map2_exn [a1; ...; an] [b1; ...; bn] ~f
is [f a1 b1; ...; f an bn]
. Raise
if the two lists have different lengths.val rev_map3_exn : 'a t ->
'b t ->
'c t -> f:('a -> 'b -> 'c -> 'd) -> 'd t
val map3_exn : 'a t ->
'b t ->
'c t -> f:('a -> 'b -> 'c -> 'd) -> 'd t
val rev_map_append : 'a t -> 'b t -> f:('a -> 'b) -> 'b t
rev_map_append l1 l2 ~f
reverses l1
mapping f
over each
element, and appends the result to the front of l2
.val fold_right : 'a t -> f:('a -> 'b -> 'b) -> init:'b -> 'b
List.fold_right [a1; ...; an] ~f ~init:b
is
f a1 (f a2 (... (f an b) ...))
.val unzip : ('a * 'b) t -> 'a t * 'b t
unzip [(a1,b1); ...; (an,bn)]
is ([a1; ...; an], [b1; ...; bn])
.val zip : 'a t -> 'b t -> ('a * 'b) t option
zip [a1; ...; an] [b1; ...; bn]
is [(a1,b1); ...; (an,bn)]
.
Returns None if the two lists have different lengths.val zip_exn : 'a t -> 'b t -> ('a * 'b) t
val mapi : 'a t -> f:(int -> 'a -> 'b) -> 'b t
val rev_mapi : 'a t -> f:(int -> 'a -> 'b) -> 'b t
val iteri : 'a t -> f:(int -> 'a -> unit) -> unit
val foldi : 'a t -> f:(int -> 'b -> 'a -> 'b) -> init:'b -> 'b
val reduce_exn : 'a t -> f:('a -> 'a -> 'a) -> 'a
reduce_exn [a1; ...; an] ~f
is f (... (f (f a1 a2) a3) ...) an
. It fails on the
empty list. Tail recursive.val reduce : 'a t -> f:('a -> 'a -> 'a) -> 'a option
val reduce_balanced : 'a t -> f:('a -> 'a -> 'a) -> 'a option
reduce_balanced
returns the same value as reduce
when f
is associative, but
differs in that the tree of nested applications of f
has logarithmic depth.
This is useful when your 'a
grows in size as you reduce it and f
becomes more
expensive with bigger inputs. For example, reduce_balanced ~f:(^)
takes n*log(n)
time, while reduce ~f:(^)
takes quadratic time.
val reduce_balanced_exn : 'a t -> f:('a -> 'a -> 'a) -> 'a
val group : 'a t -> break:('a -> 'a -> bool) -> 'a t t
group l ~break
returns a list of lists (i.e., groups) whose concatenation is
equal to the original list. Each group is broken where break returns true on
a pair of successive elements.
Example
group ~break:(<>) 'M';'i';'s';'s';'i';'s';'s';'i';'p';'p';'i'
->
['M'];['i'];['s';'s'];['i'];['s';'s'];['i'];['p';'p'];['i']
val groupi : 'a t ->
break:(int -> 'a -> 'a -> bool) -> 'a t t
Example, group the chars of Mississippi into triples
groupi ~break:(fun i _ _ -> i mod 3 = 0)
'M';'i';'s';'s';'i';'s';'s';'i';'p';'p';'i'
->
['M'; 'i'; 's']; ['s'; 'i'; 's']; ['s'; 'i'; 'p']; ['p'; 'i']
val last : 'a t -> 'a option
val last_exn : 'a t -> 'a
val is_prefix : 'a t -> prefix:'a t -> equal:('a -> 'a -> bool) -> bool
is_prefix xs ~prefix
returns true
if xs
starts with prefix
.val find_consecutive_duplicate : 'a t -> equal:('a -> 'a -> bool) -> ('a * 'a) option
find_consecutive_duplicate t ~equal
returns the first pair of consecutive elements
(a1, a2)
in t
such that equal a1 a2
. They are returned in the same order as
they appear in t
.val remove_consecutive_duplicates : 'a t -> equal:('a -> 'a -> bool) -> 'a t
remove_consecutive_duplicates
. The same list with consecutive duplicates removed.
The relative order of the other elements is unaffected.val dedup : ?compare:('a -> 'a -> int) -> 'a t -> 'a t
dedup
(de-duplicate). The same list with duplicates removed, but the
order is not guaranteed.val contains_dup : ?compare:('a -> 'a -> int) -> 'a t -> bool
contains_dup
True if there are any two elements in the list which are the same.val find_a_dup : ?compare:('a -> 'a -> int) -> 'a t -> 'a option
find_a_dup
returns a duplicate from the list (no guarantees about which
duplicate you get), or None if there are no dups.exception Duplicate_found of (unit -> Sexplib.Sexp.t) * string
exn_if_dup
belowval exn_if_dup : ?compare:('a -> 'a -> int) ->
?context:string -> 'a t -> to_sexp:('a -> Sexplib.Sexp.t) -> unit
exn_if_dup ?compare ?context t ~to_sexp
will run find_a_dup
on t
, and raise
Duplicate_found
if a duplicate is found. The context
is the second argument of
the exceptionval count : 'a t -> f:('a -> bool) -> int
count l ~f
is the number of elements in l
that satisfy the
predicate f
.val range : ?stride:int ->
?start:[ `exclusive | `inclusive ] ->
?stop:[ `exclusive | `inclusive ] -> int -> int -> int t
range ?stride ?start ?stop start_i stop_i
is the list of integers from start_i
to
stop_i
, stepping by stride
. If stride
< 0 then we need start_i
> stop_i
for
the result to be nonempty (or start_i
= stop_i
in the case where both bounds are
inclusive).val init : int -> f:(int -> 'a) -> 'a t
init n ~f
is [(f 0); (f 1); ...; (f (n-1))]
. It is an error if n < 0
.val rev_filter_map : 'a t -> f:('a -> 'b option) -> 'b t
rev_filter_map l ~f
is the reversed sublist of l
containing
only elements for which f
returns Some e
.val rev_filter_mapi : 'a t -> f:(int -> 'a -> 'b option) -> 'b t
val filter_map : 'a t -> f:('a -> 'b option) -> 'b t
filter_map l ~f
is the sublist of l
containing only elements
for which f
returns Some e
.val filter_mapi : 'a t -> f:(int -> 'a -> 'b option) -> 'b t
val filter_opt : 'a option t -> 'a t
filter_opt l
is the sublist of l
containing only elements
which are Some e
. In other words, filter_opt l
= filter_map ~f:ident l
.module Assoc:sig
..end
sub
, unlike slice
, doesn't use python-style indices!val sub : 'a t -> pos:int -> len:int -> 'a t
sub pos len l
is the len
-element sublist of l
, starting at pos
.val slice : 'a t -> int -> int -> 'a t
slice l start stop
returns a new list including elements l.(start)
through
l.(stop-1)
, normalized python-style.val take : 'a t -> int -> 'a t
take l n
is fst (split_n n l)
.
drop l n
is snd (split_n n l)
.val drop : 'a t -> int -> 'a t
val take_while : 'a t -> f:('a -> bool) -> 'a t
take_while l ~f
returns the longest prefix of l
for which f
is true
.val drop_while : 'a t -> f:('a -> bool) -> 'a t
drop_while l ~f
drops the longest prefix of l
for which f
is true
.val split_while : 'a t -> f:('a -> bool) -> 'a t * 'a t
split_while xs ~f = (take_while xs ~f, drop_while xs ~f)
val concat : 'a t t -> 'a t
val concat_no_order : 'a t t -> 'a t
concat
but faster and without preserving any ordering (ie for lists that are
essentially viewed as multi-sets.val cons : 'a -> 'a t -> 'a t
val cartesian_product : 'a t -> 'b t -> ('a * 'b) t
val to_string : f:('a -> string) -> 'a t -> string
val permute : ?random_state:Core_random.State.t -> 'a t -> 'a t
permute ?random_state t
returns a permutation of t
.
permute
side affects random_state
by repeated calls to Random.State.int
.
If random_state
is not supplied, permute
uses Random.State.default
.
val is_sorted : 'a t -> compare:('a -> 'a -> int) -> bool
is_sorted t ~compare
returns true
iff forall adjacent a1; a2
in t
, compare a1
a2 <= 0
.
is_sorted_strictly
is similar, except it uses <
instead of <=
.
val is_sorted_strictly : 'a t -> compare:('a -> 'a -> int) -> bool
val equal : 'a t -> 'a t -> equal:('a -> 'a -> bool) -> bool
module Infix:sig
..end
val transpose : 'a t t -> 'a t t option
transpose m
transposes the rows and columns of the matrix m
,
considered as either a row of column lists or (dually) a column of row lists.
Example,
transpose [1;2;3];[4;5;6]
= [1;4];[2;5];[3;6]
On non-empty rectangular matrices, transpose
is an involution
(i.e., transpose (transpose m) = m
). Transpose returns None when called
on lists of lists with non-uniform lengths.
val transpose_exn : 'a t t -> 'a t t
transpose_exn
transposes the rows and columns of its argument, throwing an exception
if the list is not rectangular.
val intersperse : 'a t -> sep:'a -> 'a t
intersperse xs ~sep
places sep
between adjacent elements of xs
.
e.g. intersperse [1;2;3] ~sep:0 = [1;0;2;0;3]
val t_of_sexp : (Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t
val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
val bin_t : 'a Bin_prot.Type_class.t -> 'a t Bin_prot.Type_class.t
val bin_read_t : 'a Bin_prot.Read.reader -> 'a t Bin_prot.Read.reader
val __bin_read_t__ : 'a Bin_prot.Read.reader -> (int -> 'a t) Bin_prot.Read.reader
val bin_reader_t : 'a Bin_prot.Type_class.reader -> 'a t Bin_prot.Type_class.reader
val bin_size_t : 'a Bin_prot.Size.sizer -> 'a t Bin_prot.Size.sizer
val bin_write_t : 'a Bin_prot.Write.writer -> 'a t Bin_prot.Write.writer
val bin_writer_t : 'a Bin_prot.Type_class.writer -> 'a t Bin_prot.Type_class.writer
of_list
is the identity function. It is useful so that the List
module matches
the same signature that other container modules do, namely:
val of_list : 'a List.t -> 'a t
n
-th element of the given list.
The first element (head of the list) is at position 0.
Raise if the list is too short or n
is negative.List.rev_append l1 l2
reverses l1
and concatenates it to l2
. This is equivalent
to (
List.rev
l1) @ l2
, but rev_append
is more efficient.List.unordered_append l1 l2
has the same elements as l1 @ l2
, but in some
unspecified order. Generally takes time proportional to length of first list, but is
O(1) if either list is empty.List.rev_map l ~f
gives the same result as
List.rev
(
ListLabels.map
f l)
, but is more efficient.fold_left
is the same as fold
, and one should always use fold
rather than
fold_left
, except in functors that are parameterized over a more general signature
where this equivalence does not hold.List.iter2_exn [a1; ...; an] [b1; ...; bn] ~f
calls in turn
f a1 b1; ...; f an bn
.
Raise if the two lists have different lengths.List.rev_map2_exn l1 l2 ~f
gives the same result as
List.rev (List.map2_exn l1 l2 ~f)
, but is more efficient.List.fold2_exn ~f ~init:a [b1; ...; bn] [c1; ...; cn]
is
f (... (f (f a b1 c1) b2 c2) ...) bn cn
.
Raise if the two lists have different lengths.List.for_all
, but for a two-argument predicate.
Raise if the two lists have different lengths.List.exists
, but for a two-argument predicate. Raise
if the end of one list is reached before the end of the other.filter l ~f
returns all the elements of the list l
that satisfy the predicate p
.
The order of the elements in the input list is preserved.filter
, but reverses the order of the input listpartition_map t ~f
partitions t
according to f
.partition_tf l ~f
returns a pair of lists (l1, l2)
, where l1
is the list of all the
elements of l
that satisfy the predicate p
, and l2
is the list of all the
elements of l
that do not satisfy p
. The order of the elements in the input list
is preserved. The "tf" suffix is mnemonic to remind readers at a call that the result
is (trues, falses).split_n n [e1; ...; em]
is ([e1; ...; en], [en+1; ...; em])
. If n > m
,
([e1; ...; em], [])
is returned. If n < 0
, ([], [e1; ...; em])
is
returned.Pervasives.compare
is a suitable comparison
function.
The current implementation uses Merge Sort. It runs in linear heap space and logarithmic stack space.
Presently, the sort is stable, meaning that two equal elements in the input will be in
the same order in the output.
Same as sort, but guaranteed to be stable
Merge two lists: assuming that l1
and l2
are sorted according to the comparison
function cmp
, merge cmp l1 l2
will return a sorted list containing all the
elements of l1
and l2
. If several elements compare equal, the elements of l1
will be before the elements of l2
.
Return the first element of the given list. Raise if the list is empty.
Return the given list without its first element. Raise if the list is empty.
find_exn t ~f
returns the first element of t
that satisfies f
. It raises
Not_found
if there is no such element.
append [1; 2] [3; 4; 5]
is [1; 2; 3; 4; 5]
List.map f [a1; ...; an]
applies function f
to a1, ..., an
, and builds the list
[f a1; ...; f an]
with the results returned by f
.concat_map t ~f
is concat (map t ~f)
, except that there is no guarantee about the
order in which f
is applied to the elements of t
.concat_mapi t ~f
is like concat_map, but passes the index as an argumentList.map2_exn [a1; ...; an] [b1; ...; bn] ~f
is [f a1 b1; ...; f an bn]
. Raise
if the two lists have different lengths.rev_map_append l1 l2 ~f
reverses l1
mapping f
over each
element, and appends the result to the front of l2
.List.fold_right [a1; ...; an] ~f ~init:b
is
f a1 (f a2 (... (f an b) ...))
.unzip [(a1,b1); ...; (an,bn)]
is ([a1; ...; an], [b1; ...; bn])
.zip [a1; ...; an] [b1; ...; bn]
is [(a1,b1); ...; (an,bn)]
.
Returns None if the two lists have different lengths.reduce_exn [a1; ...; an] ~f
is f (... (f (f a1 a2) a3) ...) an
. It fails on the
empty list. Tail recursive.reduce_balanced
returns the same value as reduce
when f
is associative, but
differs in that the tree of nested applications of f
has logarithmic depth.
This is useful when your 'a
grows in size as you reduce it and f
becomes more
expensive with bigger inputs. For example, reduce_balanced ~f:(^)
takes n*log(n)
time, while reduce ~f:(^)
takes quadratic time.
group l ~break
returns a list of lists (i.e., groups) whose concatenation is
equal to the original list. Each group is broken where break returns true on
a pair of successive elements.
Example
group ~break:(<>) 'M';'i';'s';'s';'i';'s';'s';'i';'p';'p';'i'
->
['M'];['i'];['s';'s'];['i'];['s';'s'];['i'];['p';'p'];['i']
This is just like group, except that you get the index in the original list of the
current element along with the two elements.
Example, group the chars of Mississippi into triples
groupi ~break:(fun i _ _ -> i mod 3 = 0)
'M';'i';'s';'s';'i';'s';'s';'i';'p';'p';'i'
->
['M'; 'i'; 's']; ['s'; 'i'; 's']; ['s'; 'i'; 'p']; ['p'; 'i']
The final element of a list. The _exn version raises on the empty list.
is_prefix xs ~prefix
returns true
if xs
starts with prefix
.
find_consecutive_duplicate t ~equal
returns the first pair of consecutive elements
(a1, a2)
in t
such that equal a1 a2
. They are returned in the same order as
they appear in t
.
remove_consecutive_duplicates
. The same list with consecutive duplicates removed.
The relative order of the other elements is unaffected.
dedup
(de-duplicate). The same list with duplicates removed, but the
order is not guaranteed.
contains_dup
True if there are any two elements in the list which are the same.
find_a_dup
returns a duplicate from the list (no guarantees about which
duplicate you get), or None if there are no dups.
only raised in exn_if_dup
below
exn_if_dup ?compare ?context t ~to_sexp
will run find_a_dup
on t
, and raise
Duplicate_found
if a duplicate is found. The context
is the second argument of
the exception
count l ~f
is the number of elements in l
that satisfy the
predicate f
.
range ?stride ?start ?stop start_i stop_i
is the list of integers from start_i
to
stop_i
, stepping by stride
. If stride
< 0 then we need start_i
> stop_i
for
the result to be nonempty (or start_i
= stop_i
in the case where both bounds are
inclusive).
default = 1
default = `inclusive
default = `exclusive
init n ~f
is [(f 0); (f 1); ...; (f (n-1))]
. It is an error if n < 0
.
rev_filter_map l ~f
is the reversed sublist of l
containing
only elements for which f
returns Some e
.
rev_filter_mapi is just like rev_filter_map, but it also passes in the index of each
element as the first argument to the mapped function. Tail-recursive.
filter_map l ~f
is the sublist of l
containing only elements
for which f
returns Some e
.
filter_mapi is just like filter_map, but it also passes in the index of each
element as the first argument to the mapped function. Tail-recursive.
filter_opt l
is the sublist of l
containing only elements
which are Some e
. In other words, filter_opt l
= filter_map ~f:ident l
.
Interpret a list of (key, value) pairs as a map in which only the first
occurrence of a key affects the semantics, i.e.:
List.Assoc.xxx alist ...args...
is always the same as (or at least sort of isomorphic to):
Map.xxx (alist |! Map.of_alist_multi |! Map.map ~f:List.hd) ...args...
sub
, unlike slice
, doesn't use python-style indices!sub pos len l
is the len
-element sublist of l
, starting at pos
.slice l start stop
returns a new list including elements l.(start)
through
l.(stop-1)
, normalized python-style.take l n
is fst (split_n n l)
.
drop l n
is snd (split_n n l)
.take_while l ~f
returns the longest prefix of l
for which f
is true
.drop_while l ~f
drops the longest prefix of l
for which f
is true
.split_while xs ~f = (take_while xs ~f, drop_while xs ~f)
concat
but faster and without preserving any ordering (ie for lists that are
essentially viewed as multi-sets.permute ?random_state t
returns a permutation of t
.
permute
side affects random_state
by repeated calls to Random.State.int
.
If random_state
is not supplied, permute
uses Random.State.default
.
is_sorted t ~compare
returns true
iff forall adjacent a1; a2
in t
, compare a1
a2 <= 0
.
is_sorted_strictly
is similar, except it uses <
instead of <=
.
transpose m
transposes the rows and columns of the matrix m
,
considered as either a row of column lists or (dually) a column of row lists.
Example,
transpose [1;2;3];[4;5;6]
= [1;4];[2;5];[3;6]
On non-empty rectangular matrices, transpose
is an involution
(i.e., transpose (transpose m) = m
). Transpose returns None when called
on lists of lists with non-uniform lengths.
transpose_exn
transposes the rows and columns of its argument, throwing an exception
if the list is not rectangular.
intersperse xs ~sep
places sep
between adjacent elements of xs
.
e.g. intersperse [1;2;3] ~sep:0 = [1;0;2;0;3]