自然数対の整列列挙

 x_1 \le x_2 \quad\wedge\quad y_1 \le y_2 \quad\Rightarrow\quad f(x_1,y_1) \le f(x_2,y_2)であるような fが与えられとき, a,b \in \mathbb{N} \quad\wedge\quad 1 \le a \le bを満す自然数 (a,b) fで変換したときの大きさの順にならべたリストを生成するプログラムを書け

[id:route150:20110501#1304207462]に綺麗な解が.それをすこしアレンジして写経した.

enumerate :: (Integral a, Ord b) => ((a,a) -> b) -> [(a,a)]
enumerate f = foldr1 (mergeTail f) [[(x,y) | y <- [x..]] | x <- [1..]]

mergeTail :: (Ord b) => (a -> b) -> [a] -> [a] -> [a]
mergeTail f (x:xs) yys = x : mergeBy f xs yys
mergeTail _ xxs    []  = xxs
mergeTail _ []     yys = yys

mergeBy :: (Ord b) => (a -> b) -> [a] -> [a] -> [a]
mergeBy f xxs@(x:xs) yys@(y:ys)
  | f x <= f y = x : mergeBy f xs yys
  | otherwise  = y : mergeBy f xxs ys
mergeBy _ [] yys = yys
mergeBy _ xxs [] = xxs