A pattern to unfold a list

Monday, Dec 28, 2020
Functional Haskell

The following function encapsulates the pattern to produce a list from a single value:

-- unfolding a list
unfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b]
unfold p h t x | p x = []
               | otherwise = h x : unfold p h t (t x)

That is, if the predicate, p, is true for the input argument then an empty is produced. Otherwise, h is applied to the argument to produce the head of the list and is consed to the result of recursively applying unfold to a value produced by applying the function t to the argument.


Let's say we want to create a list of lists by chopping up a single list into chunks of same sizes:

chop4 :: [a] -> [[a]]
chop4 = unfold null (take 4) (drop 4)

We stop when the input list is empty. Head is produced by taking 4 elements from the input list. Next input is produced by dropping 4 elements from the input list.

*Main> chop4 [1..12]


Even map can be defined using unfold:

map :: (a -> b) -> [a] -> [b]
map f = unfold null (f . head) tail

We stop when the input list is empty. Head is produced by applying f to head of input list and next input is produced by applying tail to the current input.


iterate is a library function that produces a list from a single value by repeatedly applying a function to that value. Since the function is repeatedly applied, its type is constrained to (a -> a). Following is an interesting implementation of iterate using unfold:

iter :: (a -> a) -> a -> [a]
iter f = unfold (const False) id f

Since iterate produces an infinite list, we use const False to always produce False for predicate. Since the list starts with the given input value, we use id function for head. f is then used to produce the next input.

*Main> take 10 (iter (+1) 0)