既約分数クイズ

30分プログラム、その722。既約分数クイズにチャレンジしました。
今回は力技で解きましたが、クイズと言うからにはきっとクールな解法があるんでしょう。

使い方

*Main> irreducibleFracs 4
[(0,1),(1,1),(1,2),(1,3),(2,3),(1,4),(3,4)]

ソースコード

type Frac a = (a,a)
canReduce :: Integral a => Frac a -> Bool
fracs :: Integral a => a -> [Frac a]
irreducibleFracs :: Integral a => a -> [Frac a]

canReduce (a,b)= gcd a b /= 1
fracs n = [(p,q) |  q <- [1..n], p <- [0..q]]
irreducibleFracs n = [f | f <- fracs n, not $ canReduce f]

参考

• 過去の30分プログラム
• 既約分数クイズ