Data.FTCQueue

• Constant-time append(><) and snoc(|>)
• Average constant-time viewL (left-edge deconstruction)

Using http://okmij.org/ftp/Haskell/extensible/FTCQueue1.hs as a starting point.

A minimal version of FTCQueue from "Reflection w/o Remorse":

• research: http://okmij.org/ftp/Haskell/Reflection.html
• type-aligned(FTCQueue): https://hackage.haskell.org/package/type-aligned

Documentation

data FTCQueue m a b

Non-empty tree. Deconstruction operations make it more and more left-leaning

tsingleton :: (a -> m b) -> FTCQueue m a b

Build a leaf from a single operation [O(1)]

(|>) :: FTCQueue m a x -> (x -> m b) -> FTCQueue m a b

Append an operation to the right of the tree [O(1)]

snoc :: FTCQueue m a x -> (x -> m b) -> FTCQueue m a b

An alias for '(|>)'

(><) :: FTCQueue m a x -> FTCQueue m x b -> FTCQueue m a b

Append two trees of operations [O(1)]

append :: FTCQueue m a x -> FTCQueue m x b -> FTCQueue m a b

An alias for '(><)'

data ViewL m a b where

Left view deconstruction data structure

Constructors

TOne :: (a -> m b) -> ViewL m a b

(:|) :: (a -> m x) -> FTCQueue m x b -> ViewL m a b

tviewl :: FTCQueue m a b -> ViewL m a b

Left view deconstruction [average O(1)]