ufracs.hs

import Data.List (iterate)
import Data.Ratio

unfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b]
unfold stop mapper next seed
  = map mapper $ takeWhile (not . stop) $ iterate next seed

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

vulgar :: UnitFraction -> Rational
vulgar us = foldr (+) 0 us -- i.e. sum

tests = and [(4 % 5)       === [2,4,20],
             (9 % 31)      === [4,25,3100],
             (21 % 50)     === [3,12,300],
             (1023 % 1024) === [2,3,7,44,9462,373029888]]
  where x === ys = egypt x == (map recip ys)

tests2 = and (map sane [(7 % 9), 1, 0, (1 % 2), (2 % 5)])
  where sane x = x == vulgar (egypt x)