Safe Haskell	Safe-Inferred
Language	Haskell2010

Cardano.TxGenerator.Internal.Fifo

Description

This is a moderately simple implementation, discussed by e.g. Okasaki in https://www.cambridge.org/core/journals/journal-of-functional-programming/article/simple-and-efficient-purely-functional-queues-and-deques/7B3036772616B39E87BF7FBD119015AB in very close to identical form save for being in SML vs. Haskell in section 2, and, somewhat earlier, by Hood and Melville (1981), Gries (1981) and Burton (1982), albeit in other languages. This may not become large enough for it to ever matter in the tx-generator, but Tarjan's structure at https://dl.acm.org/doi/10.1145/324133.324139 might be worthwhile in that case, most likely to happen if someone notices this existing and wants to use it somewhere where it might be significantly more stressed.

Synopsis

data Fifo a = Fifo ![a] ![a]
insert :: Fifo a -> a -> Fifo a
toList :: Fifo a -> [a]
emptyFifo :: Fifo a
remove :: Fifo a -> Maybe (Fifo a, a)
removeN :: Int -> Fifo a -> Maybe (Fifo a, [a])

Documentation

data Fifo a Source #

This implements the section 2 Queues as Paired Lists structure described by Okasaki.

Constructors

Fifo
Fields ![a] the front, from where removals are taken ![a] the rear, where insertions are put

insert :: Fifo a -> a -> Fifo a Source #

The rear's reverse ordering allows this to be a simple cons.

toList :: Fifo a -> [a] Source #

The arrivals inserted at the rear remain in reverse order until there is a need to dequeue that can't be satisfied from the front. Warning : bad complexity when used as a persistent data structure.

emptyFifo :: Fifo a Source #

The empty queue has no contents to sit in either the front or rear.

remove :: Fifo a -> Maybe (Fifo a, a) Source #

Potential failure demands the use of Maybe. Empty front lists trigger reversals of the rear list and the Fifo part of the result becomes a pure front list, namely the tail of that reversal.

removeN :: Int -> Fifo a -> Maybe (Fifo a, [a]) Source #

Dequeueing n items just iterates calling remove within the Maybe monad. Removing n from a Fifo of length k when k < n is regarded as a failure.