練習問題

入門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]]