cfracs.hs

import Data.List(intercalate, 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

data Continued = CFrac Integer [Integer]
               deriving (Eq)

instance Show Continued where
  show (CFrac c cs) = "[" ++ show c ++ ";" ++ cs' ++ "]"
    where cs' = intercalate "," (map show cs)

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)


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

tests = and [(9 % 16)        === CFrac 0 [1,1,3,2],
             (415 % 93)      === CFrac 4 [2,6,7],
             (23456 % 10000) === CFrac 2 [2,1,8,2,1,1,4]]
  where a === b = continued a == b

tests2 = and (map sane [12, (137 % 1600), (49 % 8), (12 % 13)])
  where sane x = x == rational (continued x)