Create a gist now

Instantly share code, notes, and snippets.

@ijp /cfracs.hs
Created May 17, 2013

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