Data.Sequence
- Package
- purescript-sequences
- Repository
- hdgarrood/purescript-sequences
This module provides a sequence data type, intended for the same sort of tasks as an Array would be in JavaScript, except with better asymptotic complexity for many operations.
The implementation uses 2-3 finger trees annotated with sizes, as described in the paper Finger Trees: A Simple General-Purpose Data Structure, Ralf Hinze and Ross Paterson, Journal of Functional Programming 16:2 (2006) pp 197-217.
This module is intended to be imported qualified, to avoid name clashes. For example:
import Data.Sequence (Seq)
import Data.Sequence as Seq
#map Source
map :: forall b a. (a -> b) -> Seq a -> Seq b
O(n). Apply a function to every element within a sequence. Note that this function is performed lazily — the actual call is almost instantaneous, regardless of the length of the sequence, because the function is not applied to all elements immediately. The eventual running time (assuming all elements are later requested) is O(n), though.
#fromFoldable Source
fromFoldable :: forall f. Foldable f => f ~> Seq
Probably O(n*log(n)), but depends on the Foldable instance. Turn any
Foldable
into a Seq
.
#toUnfoldable Source
toUnfoldable :: forall f. Functor f => Unfoldable f => Seq ~> f
Probably O(n), but depends on the Unfoldable instance. Turn a Seq
into
any Unfoldable
.
#fullyForce Source
fullyForce :: forall a. Seq a -> Seq a
Force evaluation of all unevaluated thunks within the sequence.