畳み込み

Haskellには、畳み込み(fold)という機能があるの。

畳み込みを使うと、データ構造(たとえばリスト)を単一の値に纏めることができる。
畳み込み関数は2つの引数を取る関数であり、畳み込みに用いる値(アキュムレータ)の初期値、畳み込むリストを受けとる。

リストを走査して何かを返したいときは、畳み込みを使えばよいでせう。
ちなみにリストの走査は右からでも左からでも出来るよ。

2つのリストの値を計算して、その結果をアキュムレータとする…という再帰っぽい操作を繰り返し、最後のアキュムレータの
値を関数は返してくれるんDA

-- アキュムレータ
sum' :: (Num a) => [a] -> a
sum' xs = foldl (\acc x -> acc + x) 0 xs

sum'' :: (Num a) => [a] -> a
sum'' = foldl (+) 0

map'' :: (a -> b) -> [a] -> [b]
map'' f xs = foldr (\x acc -> f x : acc) [] xs

map''' :: (a -> b) -> [a] -> [b]
map''' f xs = foldl (\acc x -> acc ++ [f x]) [] xs

elem' :: (Eq a) => a -> [a] -> Bool
elem' y ys = foldr (\x acc -> if x == y then True else acc) False ys

maximum' :: (Ord a) => [a] -> a
maximum' = foldl1 max

reverse' :: [a] -> [a]
reverse' = foldl (\acc x -> x : acc) []

reverse'' :: [a] -> [a]
reverse'' = foldl (flip (:)) []

product' :: (Num a) => [a] -> a
product' = foldl (*) 1

filter'' :: (a -> Bool) -> [a] -> [a]
filter'' p = foldr (\x acc -> if p x then x : acc else acc) []

last' :: [a] -> a
last' = foldl1 (\_ x -> x)

and' :: [Bool] -> Bool
and' xs = foldr (&&) True xs

sqrtSums :: Int
sqrtSums = length (takeWhile (<1000) (scanl1 (+) (map sqrt [1..]))) + 1

結果

Main> sum' [3,5,2,1]
11
Main> sum'' [3,5,2,1]
11
Prelude> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
Prelude> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
Main> map'' (+3) [1,2,3]
[4,5,6]
Main> map''' (+3) [1,2,3]
[4,5,6]
Main> elem' 3 [1,2,3,4]
True
Main> elem' 0 [1,2,3,4]
False
Main> maximum' [1, 2, 3, 4]
4
Main> reverse' [1, 2, 3, 4]
[4,3,2,1]
Main> reverse'' [1, 2, 3, 4]
[4,3,2,1]
Main> product' [1, 2, 3, 4]
24
Main> filter'' (>5) [1, 2, 3]

Main> last' [1, 2, 3, 5]
5
Main> flip (:) (flip (:) (flip (:) (flip (:) 3) 4) 5) 6
[6,5,4,3]
Main> and' [True,False,True]
False
Main> and' [True,False,True]
False
Main> and' (repeat False)
False
Main> scanl (+) 0 [3,5,2,1]
[0,3,8,10,11]
Main> scanr (+) 0 [3,5,2,1]
[11,8,3,1,0]
Main> scanl1 (\acc x -> if x > acc then x else acc) [3,4,5,3,7,9,2,1]
[3,4,5,5,7,9,9,9]
Main> scanl (flip (:)) [3,2,1]
[,[3],[2,3],[1,2,3]]
Main> sqrtSums
131
Main> sum (map sqrt [1..131])
1005.0942035344083
Main> sum (map sqrt [1..130])
993.6486803921487