Skip to content

unfoldr

zip allows us to zip two lists together. unzip is its inverse: it takes a list of pairs and splits it into two lists containing the first and second elements of the pairs in the input list. Similarly, unfoldr can be viewed as the inverse of foldr: Where foldr reduces a list down to a single value, unfoldr can be used to produce a list from a seed value. The goal is to produce a list of bs, a list of type [b], from a seed value of type a. To do this, we need a generator function. This generator function needs to do three things:

  • Given the initial seed value, it needs to produce the first list element.
  • It also needs to produce an updated seed value from which to produce the remainder of the list.
  • It needs to tell us when the whole list has been generated, when we're done.

A natural type for such a generator function is a -> Maybe (b, a). If there are no more list elements to be produced, the result is Nothing. Otherwise, the result is Just a pair consisting of the first list element and the updated seed value from which to produce the rest of the list. For example,

GHCi
>>> import Data.List
>>> gen x = if x > 10 then Nothing else Just (x, x+1)
>>> unfoldr gen 0
[0,1,2,3,4,5,6,7,8,9,10]

The initial seed value is 0. Given a seed value of x, gen produces x as the next list element and chooses x+1 as the next seed value. It does this until x > 10, at which point it returns Nothing to indicate that the list is done. unfoldr gen 0 thus generates the list [0,1,2,3,4,5,6,7,8,9,10]. What would unfoldr gen 5 generate? Formulate an answer first and then try it out in GHCi.

Here's how unfoldr is implemented:

unfoldr :: (a -> Maybe (b, a)) -> a -> [b]
unfoldr gen = go
  where
    go seed = case gen seed of
        Just (x, seed') -> x : go seed'
        _               -> []

Exercise

In an earlier exercise, I asked you to implement replicate. replicate n x produces a list containing n copies of x:

GHCi
>>> replicate 5 1
[1,1,1,1,1]
>>> replicate 10 1
[1,1,1,1,1,1,1,1,1,1]

Implement this function using unfoldr.

Solution 
replicate n x = unfoldr rep n
  where
    rep 0 = Nothing
    rep m = Just (x, m - 1)

Remember, the logic of unfoldr gen seed is to generate list elements from left to right by calling gen repeatedly on the current seed. If gen returns Nothing, we're done; there are no more list elements to add. If gen returns Just (x, seed'), then x becomes the next list element and seed' is the new seed value from which to generate the elements following x.

Here, we use n as our seed. If the seed is 0, then we do not want to generate any list elements, so rep 0 = Nothing. If the seed is positive, then we add one copy of x to the list and decrease our seed by 1 to indicate that we have one less copy of x to add.

Exercise

The list comprehension [x..y] generates the list of all numbers between x and y:

GHCi
>>> [3..8]
[3,4,5,6,7,8]

Implement a function genRange x y that generates the same list. Do not use list comprehensions. Use unfoldr to implement genRange instead.

GHCi
>>> genRange 3 8
[3,4,5,6,7,8]
Solution 
genRange x y = unfoldr gen x
  where
    gen z | z > y     = Nothing
          | otherwise = Just (z, z + 1)

Think about the seed value z as generating the list [z..y]. Then unfoldr gen x generates exactly the list [x..y]. If z > y, this list is empty, so gen z returns Nothing. Otherwise, the first element of [z..y] is z and the remainder of this list is the list [z+1..y], to be generated from the seed z + 1. Thus, gen z returns Just (z, z + 1).

Exercise

In an earlier exercise, I asked you to implement a function everyOther that returns a list containing every other element in the input list:

GHCi
>>> everyOther [1,2,3,4,5]
[1,3,5]
>>> everyOther "Hello"
"Hlo"

I asked you to implement this function using zip, filter, and map. Implement this function using unfoldr instead. Think about how you can do this by taking the input list as the seed. The point of this exercise is to illustrate that the seed value from which to generate the result of unfoldr can have any type. It can even be a list itself.

Solution 
everyOther :: [a] -> [a]
everyOther = unfoldr takeOneDropOne
  where
    takeOneDropOne (x:xs) = Just (x, drop 1 xs)
    takeOneDropOne _      = Nothing

everyOther xs uses xs itself as the seed value. As long as the seed list is not empty, we split it into its head x and tail xs. x becomes the first element in the list generated from this seed. The next element in the seed list should be dropped, so the new seed becomes drop 1 xs. This process continues until the seed list is empty. At this point, we have no more elements to add to the output, so takeOneDropOne returns Nothing.

You may wonder why the first equation of takeOneDropOne isn't takeOneDropOne (x:xs) = Just (x, tail xs). Think about what would happen when calling takeOneDropOne [1]. In this case, we would have x = 1 and xs = []. tail xs would then panic because we cannot take the tail of an empty list. drop 1 xs returns the tail of xs if xs is non-empty, and the empty list if xs is empty. Thus, drop 1 xs behaves like a safe version of tail here.