『自然数対の整列列挙』に挑戦

お題： 2011-04-30

http://d.hatena.ne.jp/route150/20110428/1303994639 似ているのだが f が不定である。

id:route150 氏から

遅延評価(主にfoldrとmerge)は相性がいい

と教えてもらったのに自力で解いたらこうなった。

import Control.Monad
import Data.List

enumerate f = do n <- [1..]
                 let min = f(1,n)
                 let max = f(1,n+1)
                 p <- sort $ do x <- [1..n]
                                y <- [x..n]
                                let v = f(x,y)
                                guard (min <= v && v < max)
                                return (v, (x,y))
                 return (snd p)

かなり効率が悪いと思う。

2011-05-05 追記

面積のときの手法が使えなかった理由

• f を適用した結果が整数になるとは限らないため行にマッピングできなかった
• f の逆関数が分かっていない

無限リストでも小分けにすれば sort できる。
merge の手法を使えばよいので利用する場所が思いつかないがメモしておく。