package batteries
Install
Dune Dependency
Authors
Maintainers
Sources
md5=ea26b5c72e6731e59d856626049cca4d
sha512=55975b62c26f6db77433a3ac31f97af609fc6789bb62ac38b267249c78fd44ff37fe81901f1cf560857b9493a6046dd37b0d1c0234c66bd59e52843aac3ce6cb
doc/batteries.unthreaded/BatFingerTree/module-type-S/index.html
Module type BatFingerTree.SSource
The type of finger trees containing elements of type 'a measured by 'm.
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.
Construction
singleton 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.
Deconstruction
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.
O(1) amortized, O(log(n)) worst case.
head t returns None if t is empty, or Some hd otherwise, where hd is the first element of the sequence.
O(1).
last t returns None if t is empty, or Some hd otherwise, where hd is the last element of the sequence.
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.
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.
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.
O(1) amortized, O(log(n)) worst case.
Inspection
size 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).
is_empty t returns true when the sequence has no elements.
O(1).
fold_left is equivalent to List.fold_left.
O(n).
fold_right is equivalent to List.fold_right.
O(n).
iter_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).
Conversions
Conversions to other structures
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.
to_list_backwards t is equivalent to BatList.of_enum (backwards t).
O(n).
Conversions from other structures
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).
Combining/reorganizing
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).
Boilerplate code
val print :
?first:string ->
?last:string ->
?sep:string ->
('a, 'b) BatIO.printer ->
(('a, _) fg, 'b) BatIO.printer