DeferredFolds.Unfoldr

Binary digits of a non-negative integral number.

Bytes of a bytestring

Decimal digits of a non-negative integral number.

Ascending infinite stream of enums starting from the one specified

Enums in the specified inclusive range

Filter the values given a predicate

Apply a Gonzalez fold

Apply a monadic Gonzalez fold

Construct from any foldable

Associations of a hash-map

Value of a hash-map by key

Keys of a hash-map

Value of a hash-map by key

Values of a hash-map by their keys

Hexadecimal digits of a non-negative number.

Associations of an intmap

Elements of IntSet.

Insert a separator value between each element.

Behaves the same way as Data.List.intersperse.

Ascending infinite stream of ints starting from the one specified

Ints in the specified inclusive range

Associations of a map

Octal digits of a non-negative integral number.

Elements of a prim array

Elements of a prim array coming paired with indices

Reverse the order.

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

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

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

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

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

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

Indices of set bits.

Bytes of a short bytestring

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.

Indices of unset bits.

Elements of a vector

Elements of a vector coming paired with indices

Lift into an unfold, which produces pairs with index.

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

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