module Num.ContinuedFraction
(
continuedFraction
, collapseFraction
, approximate
, convergent
, prettyFrac
, prettyFracM
) where
import Control.Recursion (ListF (..), NonEmptyF (..), apo, cata)
import Data.Foldable
import Data.List (intersperse)
import Data.List.NonEmpty (NonEmpty (..))
import Data.Maybe (fromJust)
import Data.Ratio (Ratio, denominator, (%))
isInteger :: (RealFrac a) => a -> Bool
isInteger = idem down
where
idem = ((==) <*>)
down = realToFrac . (floor :: (RealFrac a) => a -> Integer)
continuedFraction :: (RealFrac a, Integral b) => a -> [b]
continuedFraction = apo coalgebra
where coalgebra x
| isInteger x = go $ Left []
| otherwise = go $ Right alpha
where alpha = 1 / (x - realToFrac (floor x :: Integer))
go = Cons (floor x)
prettyFrac :: (Show a) => NonEmpty a -> String
prettyFrac (x :| xs) = "[" ++ show x ++ "; " ++ fold (intersperse ", " (show <$> xs)) ++ "]"
prettyFracM :: (Show a) => [a] -> Maybe String
prettyFracM [] = Nothing
prettyFracM (x:xs) = Just (prettyFrac (x :| xs))
collapseFractionM :: (Integral a, Integral b) => [a] -> Maybe (Ratio b)
collapseFractionM [] = Nothing
collapseFractionM (x:xs) = Just $ collapseFraction (x:|xs)
collapseFraction :: (Integral a, Integral b) => NonEmpty b -> Ratio a
collapseFraction = cata a
where a (NonEmptyF x xs) = go xs $ fromIntegral x % 1
go = maybe id ((+) . (1/))
convergent :: (RealFrac a, Integral b) => Int -> a -> Ratio b
convergent n x = fromJust . (collapseFractionM :: Integral a => [Integer] -> Maybe (Ratio a)) $
take n (continuedFraction x)
approximate :: (RealFrac a, Integral b) => a -> b -> Ratio b
approximate x d = last . takeWhile ((<= d) . denominator) $
fmap (flip convergent x) [1..]