A type meant to avoid duplication of signatures.
For the generic finger tree, this type will be monoid:'m monoid -> measure:('a -> 'm) -> 'wrapped_type.
Once the finger tree has been specialized, the resulting module should be reexported in such a way that the type is now simply 'wrapped_type.
val empty : ('a, 'm) fgempty is the sequence with no elements.
val singleton : 'a -> ('a, 'm) fgsingleton elt build the sequence containing elt as its sole element.
O(1).
cons t elt adds elt to the left of t.
O(1) amortized, O(log(n)) worst case.
snoc t elt adds elt to the right of t.
O(1) amortized, O(log(n)) worst case.
front t returns None when t is empty, or Some (tl, hd) when hd is the first element of the sequence and tl is the rest of the sequence.
O(1) amortized, O(log(n)) worst case.
front_exn t returns (tl, hd) when hd is the first element of the sequence and tl is the rest of the sequence.
Empty if t is empty.
O(1) amortized, O(log(n)) worst case.
val head : ('a, 'm) fg -> 'a optionhead t returns None if t is empty, or Some hd otherwise, where hd is the first element of the sequence.
O(1).
val head_exn : ('a, 'm) fg -> 'ahead_exn t returns the first element of the sequence.
Empty if t is empty.
O(1).
val last : ('a, 'm) fg -> 'a optionlast t returns None if t is empty, or Some hd otherwise, where hd is the last element of the sequence.
O(1).
val last_exn : ('a, 'm) fg -> 'alast_exn t returns the last element of the sequence.
Empty if t is empty.
O(1).
tail t returns None when t is empty, or Some tl where tl is the sequence t where the first element has been removed.
O(1) amortized, O(log(n)) worst case.
tail_exn t returns the sequence t where the first element has been removed.
Empty if t is empty.
O(1) amortized, O(log(n)) worst case.
init t returns None if t is empty, or Some init where init is the sequence t where the last element has been removed.
O(1) amortized, O(log(n)) worst case.
init_exn t returns the sequence t where the last element has been removed.
Empty if t is empty.
O(1) amortized, O(log(n)) worst case.
rear t returns None when t is empty, or Some (init, last) where last is the last element of the sequence and init is the rest of the sequence.
O(1) amortized, O(log(n)) worst case.
rear_exn t returns (init, last) when last is the last element of the sequence and init is the rest of the sequence.
Empty if t is empty.
O(1) amortized, O(log(n)) worst case.
val size : ('a, 'm) fg -> intsize t returns the number of elements in the sequence. If you want to know that a sequence is empty, it is much better to use is_empty.
O(n).
val is_empty : ('a, 'm) fg -> boolis_empty t returns true when the sequence has no elements.
O(1).
val fold_left : ('acc -> 'a -> 'acc) -> 'acc -> ('a, 'm) fg -> 'accfold_left is equivalent to List.fold_left.
O(n).
val fold_right : ('acc -> 'a -> 'acc) -> 'acc -> ('a, 'm) fg -> 'accfold_right is equivalent to List.fold_right.
O(n).
val iter : ('a -> unit) -> ('a, 'm) fg -> unititer is equivalent to List.iter.
O(n).
val iter_right : ('a -> unit) -> ('a, 'm) fg -> unititer_right is equivalent to List.iter o List.rev.
O(n).
compare cmp t1 t2 compares the two sequences lexicographically.
O(n).
equal eq t1 t2 returns true when the two sequences contain the the same elements.
O(n).
enum t builds an enumeration of the elements of t going from left to right.
O(1).
Forcing the whole enumeration takes O(n).
backwards t builds an enumeration of the elements of t going from right to left. Same complexity as enum.
val to_list : ('a, 'm) fg -> 'a listto_list t is equivalent to BatList.of_enum (enum t).
O(n).
val to_list_backwards : ('a, 'm) fg -> 'a listto_list_backwards t is equivalent to BatList.of_enum (backwards t).
O(n).
of_enum e build the sequence containing the elements of e in the same order.
Its complexity is the complexity of forcing the enumeration.
of_backwards e is equivalent to reverse (of_enum e).
O(n).
of_list l is equivalent to of_enum (BatList.enum l).
O(n).
of_list_backwards l is equivalent to of_enum_backwards (BatList.enum l).
O(n).
map is equivalent to List.map.
O(n).
map_right is equivalent to List.rev o List.map o List.rev.
O(n).
append is equivalent to List.append.
O(log(min(n,m))).
reverse t is equivalent to of_list (List.rev (to_list t)).
O(n).
val print :
?first:string ->
?last:string ->
?sep:string ->
('a, 'b) BatIO.printer ->
(('a, _) fg, 'b) BatIO.printer