Fold is well-loved by Functional Programmers: to the mathematically inclined, it represents a homomorphism from an initial algebra to another algebra; to the pragmatists, it captures a common pattern of recursion, where we collapse a structure to a single value.
Its dual, unfold, is not as well appeciated. It isn't just me that thinks so, it was the title of a 1998 paper by Jeremy Gibbons. It isn't clear to me why; it is as common to build structures as it is to collapse them, but a part of the issue is likely to be (as with comonads vs monads) lack of practice.
unfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b] unfold stop mapper next seed = map mapper $ takeWhile (not . stop) $ iterate next seed
The definition is quite clear. We generate an infinite list from an initial value, take as much as we want, and then convert the values into the form we need. The version provided by Haskell's Data.List isn't as nice, which may be one reason it doesn't get used as often, but it does allow for us to share computation between the three tasks of generating, pruning and mapping.
unfoldr :: (a -> Maybe (b, a)) -> a -> [b] unfoldr gen seed = case gen seed of Just (val, seed') -> val : unfoldr gen seed' Nothing -> 
So, we have our definition, what can we do with it?
The example given by Gibbons is one of breadth first search on trees. So first we'll need a tree data type
data Tree a = Node a [Tree a] deriving (Show, Eq) value :: Tree a -> a value (Node a _) = a children :: Tree a -> [Tree a] children (Node _ cs) = cs
The idea behind the breadth first search is simple. If we had a way of getting lists of the values at each "level" of the tree, then breadth-first search would be easy.
bfs :: (a -> Bool) -> Tree a -> [a] bfs p t = filter p . concat . levels $ t
So we need a way to get the levels of the tree. Since we are returning a list, we can use use unfold to generate the list.
levels :: Tree a -> [[a]] levels t = unfold null (map value) (concatMap children) [t]
The code is so lovely, I don't think it should need explaining, but you can read Gibbons for more on it. So now we'll turn to two examples from the world of fractions.
Fibonacci's greedy algorithm for Egyptian Fractions.
An Egyptian fraction is a representation of a fraction as the sum of distinct unit fractions (fractions of the from 1/x). For example, 2/3 becomes 1/2 + 1/6, and 11/13 becomes 1/2 + 1/3 + 1/78. In the Liber Abaci, Fibonacci provided an algorithm for turning ordinary "vulgar" fractions, into Egyptian fractions.
By continuing with the expansion, you eventually end up with a unit fraction, at which point you are done.
Since this algorithm can be thought of as returning a list of numbers to sum, we can also use an unfold here.
type UnitFraction = [Rational] unit :: Rational -> UnitFraction unit rat = unfold (== 0) (recip . ceiling' . recip) next rat where next frac = ((- d) `mod` n) % (d * (ceiling (recip frac))) where n = numerator frac d = denominator frac ceiling' = fromIntegral . ceiling egypt :: Rational -> UnitFraction egypt rat | 0 <= rat && rat <= 1 = unit rat
As mentioned earlier, unfolds are the dual of folds, so if converting rationals to Egyptian fractions is an unfold, then converting back is a fold.
vulgar :: UnitFraction -> Rational vulgar us = foldr (+) 0 us -- i.e. sum
Converting to Continued Fractions
A similar example can be found in the world of continued fractions. A continued fraction is a fraction of the form
By interpreting the coefficients as a list, we can come up with an unfold that converts rationals to continued fractions.
data Continued = CFrac Integer [Integer] deriving (Eq) continued :: Rational -> Continued continued rat = CFrac c (cont cs) where (c,cs) = properFraction rat cont rat = unfold (== 0) (floor . recip) (fractionalPart . recip) rat fractionalPart :: Rational -> Rational fractionalPart frac = frac - fromIntegral (floor frac)
and of course, the reverse process is also a fold
rational :: Continued -> Rational rational (CFrac c cs) = c' + foldr step 0 cs' where step x prev = recip (x + prev) c' = fromIntegral c cs' = map fromIntegral cs
Is that all?
Far from it, there are many examples in the Data.List module that can
be represented as unfolds. For instance,
repeat can be defined
scanl f z xs = z : unfoldr step (z,xs) where step (z,) = Nothing step (z,(x:xs)) = Just (z',(z',xs)) where z' = f z x repeat x = unfoldr step () where step () = Just (x, ())
Some procedures, like
map, can even be expressed as both a fold and an
map f xs = unfoldr step xs where step  = Nothing step (x:xs) = Just (f x, xs) map f xs = foldr step  xs where step x y = f x : y
So given this tremendous flexibility, why is unfold so unpopular? After writing all this, I think maybe that's the problem. Unfold performs mapping, pruning, and generating, which gives it a more complicated interface. (This is true whether you use the Scheme version or the Haskell version). In practice, it might just be easier on the mind to have map, fold, and iterate.