MOS.hs

gistfile1.hs

{-# LANGUAGE ViewPatterns #-}

module Main where

import Data.Ratio

-- Runs the euclidian algorithm, returning the GCD along with a list of quotients,
-- or equivantley, a continued fraction representation of a/b in list form
euclidGCD :: (Integral a) => a -> a -> (a,[a])
euclidGCD a b = go a b [] 
    where go a 0 x = (a,x)
          go a b x = go b (a `mod` b) (x++[a `div` b])

-- Just return a list of the quotients
euclidQuot a b = snd $ euclidGCD a b

-- | Converts a continued fraction in list form back into a fraction.
toFrac (x:xs) = x%1 + (rest xs)
          where rest [] = 0
                rest (x:[]) = 1%x
                rest (x:xs) = 1/(x%1 + rest xs)

-- Turn ratio into tuple form
nd :: Integral a => Ratio a -> (a,a)
nd r = (numerator r, denominator r)

-- Calculate the mediant of two ratios
mediant (nd -> (a,b)) (nd -> (c,d)) = (a+c)%(b+d)

-- Calculate the nth semiconvergent of a partial fraction represented as a list
semiconvergent n xs = mediant (toFrac $ take n xs) (toFrac $ take (n+1) xs)

-- Test data, quarter comma meantone generator
x = toRational $ (logBase 2 5)/4
x_list = euclidQuot (numerator x) (denominator x)

main :: IO ()
main = do
    putStrLn "Denominators of the first 15 semiconvergents:"
    print $ map (\x -> denominator $ semiconvergent x x_list) [1..15]
    
    putStrLn "\nQuotients generated by the euclidian algorithm:"
    print x_list
    
    putStrLn "\nReduced form of the first 15 continued fractions:"
    print $ map toFrac $ map (\n -> take n x_list) [1..15]