読者です 読者をやめる 読者になる 読者になる

自然数対の整列列挙

Haskell

 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