DeferredFolds.Unfoldr

Elements of a vector

A projection on data, which only knows how to execute a right-fold.

It is a monad and a monoid, and is very useful for efficiently aggregating the projections on data intended for right-folding, since its concatenation (<>) has complexity of O(1).

Intuition

The intuition of what this abstraction is all about can be derived from lists.

Let's consider the Data.List.foldr function for lists:

foldr :: (a -> b -> b) -> b -> [a] -> b

If we rearrange its parameters we get

foldr :: [a] -> (a -> b -> b) -> b -> b

Which in Haskell is essentially the same as

foldr :: [a] -> (forall b. (a -> b -> b) -> b -> b)

We can isolate that part into an abstraction:

newtype Unfoldr a = Unfoldr (forall b. (a -> b -> b) -> b -> b)

Then we get to this simple morphism:

list :: [a] -> Unfoldr a
list list = Unfoldr (\ step init -> foldr step init list)

We can do the same with say Data.Text.Text:

text :: Text -> Unfoldr Char
text text = Unfoldr (\ step init -> Data.Text.foldr step init text)

And then we can use those both to concatenate with just an O(1) cost:

abcdef :: Unfoldr Char
abcdef = list ['a', 'b', 'c'] <> text "def"

Please notice that up until this moment no actual data materialization has happened and hence no traversals have appeared. All that we've done is just composed a function, which only specifies which parts of data structures to traverse to perform a right-fold. Only at the moment where the actual folding will happen will we actually traverse the source data. E.g., using the "fold" function:

abcdefLength :: Int
abcdefLength = fold Control.Foldl.length abcdef

Apply a Gonzalez fold

Apply a monadic Gonzalez fold

Reverse the order.

Use with care, because it requires to allocate all elements.

Filter the values given a predicate

Insert a separator value between each element.

Behaves the same way as intersperse.

Construct from any foldable

Ints in the specified inclusive range

Associations of a map

Associations of an intmap

Bytes of a bytestring

Bytes of a short bytestring

Elements of a prim array

Elements of a prim array coming paired with indices

Elements of IntSet.

Ascending infinite stream of enums starting from the one specified

Enums in the specified inclusive range

Ascending infinite stream of ints starting from the one specified

Keys of a hash-map

Associations of a hash-map

Value of a hash-map by key

Value of a hash-map by key

Values of a hash-map by their keys

Elements of a vector coming paired with indices

Binary digits of a non-negative integral number.

Binary digits of a non-negative integral number in reverse order.

Digits of a non-negative number in numeral system based on the specified radix. The digits come in reverse order.

E.g., here's how an unfold of binary digits in proper order looks:

binaryDigits :: Integral a => a -> Unfoldr a
binaryDigits = reverse . reverseDigits 2

Octal digits of a non-negative integral number.

Octal digits of a non-negative integral number in reverse order.

Decimal digits of a non-negative integral number.

Decimal digits of a non-negative integral number in reverse order. More efficient than decimalDigits.

Hexadecimal digits of a non-negative number.

Hexadecimal digits of a non-negative number in reverse order.

Lift into an unfold, which produces pairs with index.

Lift into an unfold, which produces pairs with right-associative index.

Indices of set bits.

Indices of unset bits.

Reproduces the behaviour of unpack.

Implementation is efficient and avoids allocation of an intermediate list.

Reproduces the behaviour of words.

Implementation is efficient and avoids allocation of an intermediate list.

Transformer of chars, replaces all space-like chars with space, all newline-like chars with \n, and trims their duplicate sequences to single-char. Oh yeah, it also trims whitespace from beginning and end.