Copyright | (c) Atze van der Ploeg 2014 (c) David Feuer 2021 |
---|---|
License | BSD-style |
Maintainer | atzeus@gmail.org |
Stability | provisional |
Portability | portable |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
A queue (actually an output-restricted deque), with worst case constant time:
|>
, <|
, and viewl
. It has worst case linear time viewr
. ><
is linear
in the length of its second argument.
Based on: "Simple and Efficient Purely Functional Queues and Deques", Chris Okasaki, Journal of Functional Programming 1995
Documentation
A scheduled Banker's FastQueue, as described by Okasaki.
Instances
A lazy-spined snoc-list. Why lazy-spined? Only because
that's better for fmap
. In theory, strict-spined should
be a bit better for everything else, but in practice it
makes no measurable difference.