日: 2006年5月20日

cf. id:takatoh:20060519:pythagorean

昨日のダメダメなのを修正するぞ。
いや，実はアップしてからすぐに気が付いたんだけど時間がないから後にしよう，なんて考えたら，案の定ツッコまれた。
というかアップする前に気づけ。

というわけで，昨日のでは条件が足りなかったようだ。必要な条件は次の３つ。１つ目だけは昨日のにも入っていた。

• m > n
• m と n は互いに素
• m – n が奇数

で，こうなった。

pPythagorean a = [(m*m-n*n, 2*m*n, z) | m <- [1..a], n <- [1..a], m>n, gcd m n == 1, odd (m-n), let z = m*m+n*n, z <= a]

結果。

*Main> pPythagorean 100
[(3,4,5),(5,12,13),(15,8,17),(7,24,25),(21,20,29),(9,40,41),(35,12,37),(11,60,61
),(45,28,53),(33,56,65),(13,84,85),(63,16,65),(55,48,73),(39,80,89),(77,36,85),(
65,72,97)]

これでOKかな。

「入門Haskell―はじめて学ぶ関数型言語」　p.87 より。

lattice 関数を改良し，現在の2次元格子点限定から任意のn次元格子点に対応するように Integer -> Integer -> [ [Integer] ] の型 を持つようにしなさい。また，それを利用して all_lattice も n次元格子点をすべて順番に列挙するように改良しなさい。

※注意：ヒントにtypo というか文字の取り違えがある。紛らわしい。

これは簡単。

lattice 1 n = [[n]]
lattice d n = [a:b | a <- [0..n], b <- lattice (d-1) (n-a)]

all_lattice d = concat [lattice d i | i <- [0..]]

結果。

*Main> take 50 $ all_lattice 2
[[0,0],[0,1],[1,0],[0,2],[1,1],[2,0],[0,3],[1,2],[2,1],[3,0],[0,4],[1,3],[2,2],[
3,1],[4,0],[0,5],[1,4],[2,3],[3,2],[4,1],[5,0],[0,6],[1,5],[2,4],[3,3],[4,2],[5,
1],[6,0],[0,7],[1,6],[2,5],[3,4],[4,3],[5,2],[6,1],[7,0],[0,8],[1,7],[2,6],[3,5]
,[4,4],[5,3],[6,2],[7,1],[8,0],[0,9],[1,8],[2,7],[3,6],[4,5]]
*Main> take 50 $ all_lattice 3
[[0,0,0],[0,0,1],[0,1,0],[1,0,0],[0,0,2],[0,1,1],[0,2,0],[1,0,1],[1,1,0],[2,0,0]
,[0,0,3],[0,1,2],[0,2,1],[0,3,0],[1,0,2],[1,1,1],[1,2,0],[2,0,1],[2,1,0],[3,0,0]
,[0,0,4],[0,1,3],[0,2,2],[0,3,1],[0,4,0],[1,0,3],[1,1,2],[1,2,1],[1,3,0],[2,0,2]
,[2,1,1],[2,2,0],[3,0,1],[3,1,0],[4,0,0],[0,0,5],[0,1,4],[0,2,3],[0,3,2],[0,4,1]
,[0,5,0],[1,0,4],[1,1,3],[1,2,2],[1,3,1],[1,4,0],[2,0,3],[2,1,2],[2,2,1],[2,3,0]
]

OK。…と思ったら型が合わない。

*Main> :t lattice
lattice :: (Num a, Num a1, Enum a) => a1 -> a -> [[a]]

ああ，そうか。Int でもかまわないものな。それに，引数に整数以外を与えてしまうとおかしなことになる。
これは宣言してやればいいだけだ。

lattice :: Integer -> Integer -> [[Integer]]