Safe Haskell	None
Language	Haskell2010

Data.Paired.Foldable

Description

Efficient enumeration of subsets of triangular elements. Given a list [1..n] we want to enumerate a subset [(i,j)] of ordered pairs in such a way that we only have to hold the elements necessary for this subset in memory.

Synopsis

upperTri :: Foldable t => SizeHint -> OnDiag -> Enumerate -> t a -> Either String (IntMap a, Int, [((Int, Int), (a, a))])

Documentation

upperTri Source #

Arguments

:: Foldable t
=> SizeHint	If the size of `t a` is known beforehand, give the appropriate `KnownSize n`, otherwise give `UnknownSize`. Using `UnknownSize` will force the complete spine of `t a`.
-> OnDiag	The enumeration will include the pairs on the main diagonal with `OnDiag`, meaning `(i,i)` will be included for all `i`. Otherwise, `NoDiag` will exclude these elements.
-> Enumerate	Either enumerate `All` elements or enumerate the `s` elements starting at `k` with `FromN k s`.
-> t a	The foldable data structure to enumerate over.
-> Either String (IntMap a, Int, [((Int, Int), (a, a))])	If there is any error then return `Left errorMsg`. Otherwise we have `Right (imap, numElems, list)`. The `imap` structure holds the subset of elements with which we actually generate elements. `numElems` is the total number of elements that will be generated. This is calculated without touch `list`. Finally, `list` is the lazy list of elements to be generated.

Generalized upper triangular elements. Given a list of elements [e_1,...,e_k], we want to return pairs (e_i,e_j) such that we have all ordered pairs with i<j (if NoDiagonal elements), or i<=j (if OnDiagonal elements).

upperTri will force the spine of t a but is consumed linearly with a strict Data.Foldable.foldl'. Internally we keep a Data.IntMap of the retained elements.

This is important if the Enumerate type is set to FromN k n. We start at the kth element, and produce n elements.

TODO compare IntMap and HashMap.

TODO inRange is broken.