自然数対の整列列挙
であるようなが与えられとき,を満す自然数対をで変換したときの大きさの順にならべたリストを生成するプログラムを書け
[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