DPutils- utilities for DP

Safe HaskellNone



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.



upperTri Source #


:: 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.