module Num.ContinuedFraction
(
continuedFraction
, collapseFraction
, approximate
, convergent
, prettyFrac
, prettyFracM
) where
import Data.Functor.Foldable (ListF (..), apo)
import Data.List (intersperse)
import Data.List.NonEmpty (NonEmpty (..), fromList)
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 ++ "; " ++ mconcat (intersperse ", " (show <$> xs)) ++ "]"
prettyFracM :: (Show a) => [a] -> Maybe String
prettyFracM [] = Nothing
prettyFracM (x:xs) = Just (prettyFrac (x :| xs))
collapseFractionM :: (Integral a) => [Integer] -> Maybe (Ratio a)
collapseFractionM [] = Nothing
collapseFractionM [x] = Just $ fromIntegral x % 1
collapseFractionM (x:xs) = fmap ((fromIntegral x % 1 +) . (1 /)) (collapseFractionM xs)
collapseFraction :: (Integral a, Integral b) => NonEmpty b -> Ratio a
collapseFraction (x:|[]) = fromIntegral x % 1
collapseFraction (x:|xs) = (fromIntegral x % 1) + 1 / collapseFraction (fromList xs)
convergent :: (RealFrac a, Integral b) => Int -> a -> Ratio b
convergent n x = fromJust . collapseFractionM $ 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..]