Create a gist now

Instantly share code, notes, and snippets.

@ijp /ufracs.hs
Created May 17, 2013

What would you like to do?
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment