mapいろいろ
mymapFoldR, mymapTrad
結城さんのhttp://www.hyuki.com/haskell/20041222145051の
mymapFoldR :: (a -> b) -> [a] -> [b] mymapFoldR f = foldr ((:) . f) []
は*1、
mymapFoldR f (x:xs) => f x:mymapFoldR f xs
と評価されます。したがって、
mymapTrad f [] = [] mymapTrad f (x:xs) = f x:mymapTrad f xs
と同じです。リストの長さに対して計算量はO(n)で、無限リストにも適用できます。
mymapFoldL
今度はfoldlでmapを定義してみます。foldlの型は、リストを返そうとおもうと
foldl :: ([a] -> b -> [a]) -> [a] -> [b] -> [a]
なので、
mymapFoldL f = foldl (\xs x -> xs ++ [f x]) []
となります。これは、http://www.hyuki.com/haskell/20041220220712と同じですが、(++)で先頭からリストを辿るので、O(n^2)になってしまいます*2。無限リストにも適用できません。
mymapCPS
CPSの
mymapCPS f k [] = k [] mymapCPS f k (x:xs) = mymapCPS f (k . (f x:)) xs
は、上のどちらとも違います。
例えば、
mymapCPS show id [1..5]
ならば、
((((((id . (show 1:)) . (show 2:)) . (show 3:)) . (show 4:)) . (show 5:)) [])
のように、最初に show 5:[] ができます。
リストが尻尾の方からできていくところがミソです。効率が良くO(n)ですが、無限リストには対応できません。
発展
mapFoldRがあればいいと思うかも知れませんが、CPSの、ちゃんとリストの尻尾まで評価するという性質が役にたつことがあるのです。それはリストを作る関数の未評価の式が、評価結果よりずっと大きくてメモリをとる場合です。
捕捉
tail-recursiveな(リストを処理する)関数は基本的にfoldlになります。
