package grenier
Install
Dune Dependency
Authors
Maintainers
Sources
sha256=b08e4c774ef72fc53c4fcee477e739d1beac9702079300daddf51ced9fa9cd26
sha512=984d92c51dac7b3f169cad595969a4fdbeb2be7b420ed1a85618d6adbb64af855cf2618d9bd0834e84d6734b99196944cab04435e1aeacad8cdfbc9a7f73d6d4
doc/grenier.dbseq/Dbseq/index.html
Module DbseqSource
Dbseq immutable sequence
Dbseq is a small data structure that offers operations halfway between a list and an immutable array. Most operations have a logarithmic cost. In practice, it is a log with base 4 and small constant factors.
This data structure is particularly suitable to associate metadata to variables in De-Bruijn notation (hence the name).
Sequences with element of type 'a *
cons x xs adds element x at the beginning of sequence xs. x now has index 0 and xs's elements are shifted by 1. Worst-case cost is O(log n), though the actual cost is quasi constant.
get i xs access the i'th element of xs in cost O(log i). In particular, access to recent elements is quasi constant.
The operation is only defined if 0 <= i < length xs, and will raise Not_found if i is out of bounds.
set i x xs update the i'th element of xs to value x in cost O(log i).
The operation is only defined if 0 <= i < length xs, and will raise Not_found if i is out of bounds.
update xs i f behaves like set i (f (get i xs)) xs