Haskell でいろいろと列挙する

* 自然数を列挙する

[1..]

* 正の奇数を列挙する

[1,3..]

* 整数（負の数を含む）を列挙する

ほぼ [1] の記事からの引用。ゼロが特別扱いで後つけになる。

0:[ s * x | x <- [1..], s <- [1, -1] ]

* 正の整数の対を列挙する

[2] の論文の冒頭で「遅延評価の関数型言語のプログラマならみんな知っている方法」（本当ですか？）として挙がっていたのをちょっと改変した（有理数じゃなく整数の対にしただけ）のがこれ。

intPairs :: [(Integer, Integer)]
intPairs = concat (diags [[(m, n) | m <- [1..]] | n <- [1..]])

diags = diags' []
          where diags' xss (ys:yss) = map head xss:diags' (ys:map tail xss) yss

私は関数が適用される様子をノートに書いてじっくり考えないと分かりませんでした。

でもこれって以下のように書いたほうが直接的で分かりよくないだろうかと思った。（あと上の方法って数が大きくなるにつれてメモリ使用量が上がっていくような気もするのだがこれは検証していない）

intPairs2 :: [(Integer, Integer)]
intPairs2 = iterate nextIntPair (1, 1)

nextIntPair :: (Integer, Integer) -> (Integer, Integer)
nextIntPair (x, y) | x == 1    = (y + 1, 1)
                   | otherwise = (x - 1, y + 1)

* 整数（負の数を含む）の対を列挙する

2次元座標をぐるぐる巻きになぞるようにしてみた。もっと賢い書き方がきっとありそう。

intPairs3 :: [(Integer, Integer)]
intPairs3 = iterate nextIntPair3 (0, 0)

nextIntPair3 :: (Integer, Integer) -> (Integer, Integer)
nextIntPair3 (0, 0) = (1, 0)
nextIntPair3 (x, y) | x > 0 && (abs x) >  (abs y) = (x, y - 1)
                    | y > 0 && (abs x) <= (abs y) = (x + 1, y)
                    | x < 0 && (abs x) >= (abs y) = (x, y + 1)
                    | y < 0 && (abs x) <= (abs y) = (x - 1, y)

* 使い道

数学的センスが無い私のような人が問題をコンピュータにブルートフォースで解かせるのに役立ちます。

問題: 82r + 17s = 1 を成立させるような整数 r,s を1組挙げよ

Main> take 1 [(r, s) | (r, s) <- intPairs3, (82 * r) + (17 * s) == 1]
[(-6,29)]

ちなみに [2] の論文のメインは重複しない正の有理数を列挙する方法についてのものですが、私はまだ読んでいません。同じアルゴリズムを以前結城浩さんが「既約分数クイズ」[3] として紹介してブーム?になったそうです。

[1] http://haskell.g.hatena.ne.jp/hyuki/20060621/lc
[2] http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/rationals.pdf
[3] http://www.hyuki.com/diary/dia0312.html#i30