トップ «前の日記(2007-12-02) 最新 次の日記(2007-12-05)» 月表示 編集

日々の流転


2007-12-04 [長年日記]

λ. 無限オブ無限

稲葉さんの「無限オブ無限」より。

まずは非常に単純な回答。 斜めに列挙するのに比べると、最初の方のリストの要素が出てきやすく、後の方のリストの要素が出てきにくいのが若干問題かも知れないけど。

iflatten :: [[a]] -> [a]
iflatten = foldr interleave []

interleave :: [a] -> [a] -> [a]
interleave (x:xs) ys = x : interleave ys xs
interleave [] ys     = ys

実行結果はこんな感じ。

Main> take 10 $ iflatten [[(i,j)|j<-[1..]] | i<-[1..]]
[(1,1),(2,1),(1,2),(3,1),(1,3),(2,2),(1,4),(4,1),(1,5),(2,3)]

ちなみに、要素が必ず現れるというのは一種の公平性(fairness)なのだけど、こういった方法をより一般化すると Backtracking, Interleaving, and Terminating Monad Transformers (cf. 20050702#p04) でされているような話になるはず。

また、上記のものにあった後の方のリストの要素が出てきにくいという問題も、20050702#p04で書いた bindz のような関数を用いることで解決することが出来るはず。 もちろんこの場合にはもっと単純になると思うけど。

Tags: haskell
本日のツッコミ(全2件) [ツッコミを入れる]
ψ [1..100]>>=pen (2007-12-05 18:12)

interleave xs ys = concat $ transpose [xs, ys]<br>この出現順の重みは大体 y*2^x なのかな?

ψ さかい (2007-12-07 00:20)

おお、なるほど。<br>transposeを使うとn個のinterleaveへの一般化がしやすくて良いですね。<br># それはそうと、[1..100]>>=pen さん、transpose が好きですねぇ (^^;<br><br>重みもそんな感じだと思います。