Unfolding Fractions

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.

In this post, I will be using a slightly different version of unfold than Haskell programmers are used to, but instead one more familiar to Scheme programmers.

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?

Breadth-first Search.

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.

x y = 1 y / x + ( - y ) mod x y y / x

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

a 0 + 1 a 1 + 1 a 2 + 1 + 1 a n

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, scanl and 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 unfold.

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

Conclusion

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.

If you want to play with the fractions examples, the code is on github, here and here.

Lastly, I'd like to apologise if the equations don't come out right on your browser, since I'm using MathML in lieu of Javascript

add

Just wanted to say two things. First, great and interesting post. Second, your blog works well on 7" tablets :-)