2007-12-05

k.inabaさんとこ(http://www.kmonos.net/wlog/80.html#_0950071204)のお題「無限リストの無限リストに含まれる要素を、どの要素もいつかはでてくるように列挙」をやってみた。haskellで書いちゃったので題意は満たさない。

「ナナメに列挙」で。最初、インデックスアクセスを使って書いてたら『「有限か無限かわからんリストの有限か無限かわからんリスト」に対しても適切に動作する』が上手く書けなかったので、再帰処理にした。
「有限個の無限リスト」を状態として保持しておいて、その各先頭要素を列挙、次の状態を、「各先頭要素を削除したもの+次の無限リスト」として再帰。

inf c = map ((c:).show) [1..]
inf_of_inf = map inf (cycle ['A'..'Z']) -- 無限オブ無限

fin c = map ((c:).show) [1..100]
fin_of_fin = map fin ['A'..'Z'] -- 有限オブ有限

mixed = [inf 'a'] ++ fin_of_fin ++ [inf 'z'] -- 有限オブ有限に二つの無限追加

f_2 (hd:rest) = f_2' [hd] rest

f_2' heads list | null front && null list = []
                | otherwise 
                    = front ++ if (null list) then
                                   f_2' (next_heads) []
                               else
                                   f_2' (next_heads++[head list]) (tail list)
    where
      front = concat front'
      next_heads = concat next_heads'
      (front',next_heads') = unzip $ map split heads
      split [] = ([],[])
      split (hd:[]) = ([hd],[])
      split (hd:rest) = ([hd],[rest])

で、こうなる。最後のは有限のリストは列挙されきって無限リストの要素だけが残ってる例。

 *Main> take 20 $ f_2 inf_of_inf
["A1","A2","B1","A3","B2","C1","A4","B3","C2","D1","A5","B4","C3","D2","E1","A6","B5","C4","D3","E2"]
 *Main> take 20 $ f_2 fin_of_fin
["A1","A2","B1","A3","B2","C1","A4","B3","C2","D1","A5","B4","C3","D2","E1","A6","B5","C4","D3","E2"]
 *Main> length $ f_2 fin_of_fin
2600
 *Main> take 20 $ f_2 mixed
["a1","a2","A1","a3","A2","B1","a4","A3","B2","C1","a5","A4","B3","C2","D1","a6","A5","B4","C3","D2"]
 *Main> take 20 $ drop 10000 $ f_2 mixed
["z3687","a3715","z3688","a3716","z3689","a3717","z3690","a3718","z3691","a3719","z3692","a3720","z3693","a3721","z3694","a3722","z3695","a3723","z3696","a3724"]

n次元への拡張もしたいなあ。

追記

「このロジックならRuby版も簡単に書けそうだな」とか思ってたら、ku-ma-meさんとこ(http://d.hatena.ne.jp/ku-ma-me/20071204/p1)にRuby版が。みじけえ！

sshi.Continual

「無限オブ無限」をやってみた

追記