kuretchi's blog

競技プログラミング初心者のブログです。

Haskellで分数の演算

Haskell で分数を扱うには、Data.Ratio モジュールの Ratio a 型を使う。
% 演算子を使い、\displaystyle\frac{a}{b}a % b のように表現される。

ghci> import Data.Ratio
ghci> :t (%)
(%) :: Integral a => a -> a -> Ratio a
ghci> :t 2 % 3
2 % 3 :: Integral a => Ratio a
ghci> 5 % 10
1 % 2
ghci> 2 % (-3)
(-2) % 3
ghci> (-2) % (-3)
2 % 3

Ratio a 型は、Num、Fractional、Real 型クラスのインスタンスである。
そのため、特に型注釈のない小数などの多相定数は Ratio a 型になることができる。

ghci> 1.2 :: Integral a => Ratio a
6 % 5
ghci> -1.3 :: Ratio Int
(-13) % 10
ghci> 1.5 / 2 :: Ratio Integer
3 % 4

演算子 +-*/ が使える。

ghci> (1 % 6) + (2 % 9)
7 % 18
ghci> (1 % 6) - (2 % 9)
(-1) % 18
ghci> (2 % 3) + 1
5 % 3
ghci> 0.5 - (1 % 2)
0 % 1
ghci> (2 % 3) * (3 % 4)
1 % 2
ghci> (2 % 3) * (-3.5)
(-7) % 3
ghci> (2 % 3) / (3 % 4)
8 % 9
ghci> 3 / (1 % 3)
9 % 1
ghci> ((-5) % 2) / 0.2
(-25) % 2

divmod を使いたいときは、代わりに Data.Fixed モジュールの div'mod'を使う。

ghci> import Data.Fixed
ghci> :t div'
div' :: (Real a, Integral b) => a -> a -> b
ghci> (13 % 5) `div'` (4 % 5)
3
ghci> (99 % 4) `div'` 5
4
ghci> (99 % 4) `div'` (-5)
-5 -- 負の無限大に丸められる
ghci> 2.99 `div'` (1 % 2)
5
ghci> :t mod'
mod' :: Real a => a -> a -> a
ghci> (13 % 10) `mod'` (2 % 5)
1 % 10
ghci> (13 % 10) `mod'` 0.7
3 % 5
ghci> (13 % 10) `mod'` (-0.7)
(-1) % 10
ghci> ((-13) % 10) `mod'` 0.7
1 % 10
ghci> ((-13) % 10) `mod'` (-0.7)
(-3) % 5
ghci> 2.99 `mod'` (1 % 2)
49 % 100

Ratio a 型の値から分子を取り出すには numerator 関数、分母を取り出すには denominator 関数を使う。

ghci> :t numerator
numerator :: Ratio a -> a
ghci> :t denominator
denominator :: Ratio a -> a
ghci> numerator (2 % 3)
2
ghci> denominator (4 % 2)
1 -- 2 % 1

Float、Double 型の数値を Ratio a 型に変換するには、toRational 関数を使う。ただし、誤差が発生することがある。

ghci> :t toRational
toRational :: Real a -> a -> Rational
ghci> toRational (0.5 :: Float)
1 % 2
ghci> toRational (2.4 :: Double)
5404319552844595 % 2251799813685248

なお、Rational は Ratio Integer の型シノニムである。

逆に、Rational 型の分数を小数などに変換するための fromRational 関数も提供されている。こちらも誤差が発生することがある。

ghci> :t fromRational
fromRational :: Fractional a => Rational -> a
ghci> fromRational (1 % 2)
0.5
ghci> fromRational (1 % 3)
0.3333333333333333