package batteries

  1. Overview
  2. Docs
package batteries
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module type BatFingerTree.SSource

Sourcetype ('a, 'm) fg

The type of finger trees containing elements of type 'a measured by 'm.

Sourcetype ('wrapped_type, 'a, 'm) wrap

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

Sourceval empty : ('a, 'm) fg

empty is the sequence with no elements.

Sourceval singleton : 'a -> ('a, 'm) fg

singleton elt build the sequence containing elt as its sole element.

O(1).

Sourceval cons : (('a, 'm) fg -> 'a -> ('a, 'm) fg, 'a, 'm) wrap

cons t elt adds elt to the left of t.

O(1) amortized, O(log(n)) worst case.

Sourceval snoc : (('a, 'm) fg -> 'a -> ('a, 'm) fg, 'a, 'm) wrap

snoc t elt adds elt to the right of t.

O(1) amortized, O(log(n)) worst case.

Deconstruction

Sourceval front : (('a, 'm) fg -> (('a, 'm) fg * 'a) option, 'a, 'm) wrap

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.

Sourceval front_exn : (('a, 'm) fg -> ('a, 'm) fg * 'a, 'a, 'm) wrap

front_exn t returns (tl, hd) when hd is the first element of the sequence and tl is the rest of the sequence.

  • raises Empty

    if t is empty.

O(1) amortized, O(log(n)) worst case.

Sourceval head : ('a, 'm) fg -> 'a option

head t returns None if t is empty, or Some hd otherwise, where hd is the first element of the sequence.

O(1).

Sourceval head_exn : ('a, 'm) fg -> 'a

head_exn t returns the first element of the sequence.

  • raises Empty

    if t is empty.

O(1).

Sourceval last : ('a, 'm) fg -> 'a option

last t returns None if t is empty, or Some hd otherwise, where hd is the last element of the sequence.

O(1).

Sourceval last_exn : ('a, 'm) fg -> 'a

last_exn t returns the last element of the sequence.

  • raises Empty

    if t is empty.

O(1).

Sourceval tail : (('a, 'm) fg -> ('a, 'm) fg option, 'a, 'm) wrap

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.

Sourceval tail_exn : (('a, 'm) fg -> ('a, 'm) fg, 'a, 'm) wrap

tail_exn t returns the sequence t where the first element has been removed.

  • raises Empty

    if t is empty.

O(1) amortized, O(log(n)) worst case.

Sourceval init : (('a, 'm) fg -> ('a, 'm) fg option, 'a, 'm) wrap

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.

Sourceval init_exn : (('a, 'm) fg -> ('a, 'm) fg, 'a, 'm) wrap

init_exn t returns the sequence t where the last element has been removed.

  • raises Empty

    if t is empty.

O(1) amortized, O(log(n)) worst case.

Sourceval rear : (('a, 'm) fg -> (('a, 'm) fg * 'a) option, 'a, 'm) wrap

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.

Sourceval rear_exn : (('a, 'm) fg -> ('a, 'm) fg * 'a, 'a, 'm) wrap

rear_exn t returns (init, last) when last is the last element of the sequence and init is the rest of the sequence.

  • raises Empty

    if t is empty.

O(1) amortized, O(log(n)) worst case.

Inspection

Sourceval size : ('a, 'm) fg -> int

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).

Sourceval is_empty : ('a, 'm) fg -> bool

is_empty t returns true when the sequence has no elements.

O(1).

Sourceval fold_left : ('acc -> 'a -> 'acc) -> 'acc -> ('a, 'm) fg -> 'acc

fold_left is equivalent to List.fold_left.

O(n).

Sourceval fold_right : ('acc -> 'a -> 'acc) -> 'acc -> ('a, 'm) fg -> 'acc

fold_right is equivalent to List.fold_right.

O(n).

Sourceval iter : ('a -> unit) -> ('a, 'm) fg -> unit

iter is equivalent to List.iter.

O(n).

Sourceval iter_right : ('a -> unit) -> ('a, 'm) fg -> unit

iter_right is equivalent to List.iter o List.rev.

O(n).

Sourceval compare : ('a -> 'a -> int) -> ('a, 'm) fg -> ('a, 'm) fg -> int

compare cmp t1 t2 compares the two sequences lexicographically.

O(n).

Sourceval equal : ('a -> 'a -> bool) -> ('a, 'm) fg -> ('a, 'm) fg -> bool

equal eq t1 t2 returns true when the two sequences contain the the same elements.

O(n).

Conversions

Conversions to other structures

Sourceval enum : ('a, 'm) fg -> 'a BatEnum.t

enum t builds an enumeration of the elements of t going from left to right.

O(1).

Forcing the whole enumeration takes O(n).

Sourceval backwards : ('a, 'm) fg -> 'a BatEnum.t

backwards t builds an enumeration of the elements of t going from right to left. Same complexity as enum.

Sourceval to_list : ('a, 'm) fg -> 'a list

to_list t is equivalent to BatList.of_enum (enum t).

O(n).

Sourceval to_list_backwards : ('a, 'm) fg -> 'a list

to_list_backwards t is equivalent to BatList.of_enum (backwards t).

O(n).

Conversions from other structures

Sourceval of_enum : ('a BatEnum.t -> ('a, 'm) fg, 'a, 'm) wrap

of_enum e build the sequence containing the elements of e in the same order.

Its complexity is the complexity of forcing the enumeration.

Sourceval of_backwards : ('a BatEnum.t -> ('a, 'm) fg, 'a, 'm) wrap

of_backwards e is equivalent to reverse (of_enum e).

O(n).

Sourceval of_list : ('a list -> ('a, 'm) fg, 'a, 'm) wrap

of_list l is equivalent to of_enum (BatList.enum l).

O(n).

Sourceval of_list_backwards : ('a list -> ('a, 'm) fg, 'a, 'm) wrap

of_list_backwards l is equivalent to of_enum_backwards (BatList.enum l).

O(n).

Combining/reorganizing

Sourceval map : (('a -> 'b) -> ('a, 'm) fg -> ('b, 'm) fg, 'b, 'm) wrap

map is equivalent to List.map.

O(n).

Sourceval map_right : (('a -> 'b) -> ('a, 'm) fg -> ('b, 'm) fg, 'b, 'm) wrap

map_right is equivalent to List.rev o List.map o List.rev.

O(n).

Sourceval append : (('a, 'm) fg -> ('a, 'm) fg -> ('a, 'm) fg, 'a, 'm) wrap

append is equivalent to List.append.

O(log(min(n,m))).

Sourceval reverse : (('a, 'm) fg -> ('a, 'm) fg, 'a, 'm) wrap

reverse t is equivalent to of_list (List.rev (to_list t)).

O(n).

Boilerplate code

Sourceval print : ?first:string -> ?last:string -> ?sep:string -> ('a, 'b) BatIO.printer -> (('a, _) fg, 'b) BatIO.printer
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct