畳み込み - fold(l|r), reduce

RubyとPythonの場合
http://d.hatena.ne.jp/nullpobug/20080609/1212994658

Haskellだとfoldl(fold-left)とfoldr(fold-right)らしい。
定義を拾ってきた

-- fold-left
foldl            :: (a -> b -> a) -> a -> [b] -> a
foldl f z []     =  z
foldl f z (x:xs) =  foldl f (f z x) xs


-- fold-right
foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)

Haskellの関数定義はいかにも仕様定義って感じがする。さすが数学臭い言語。
それはさておき、動作を確認してみますん。

Prelude> foldl (-) 0 [1..5]
-15
--((((0-1)-2)-3)-4)-5=-15

Prelude> foldr (-) 0 [1..5]
3
--1-(2-(3-(4-(5-0)))) = 3

へー。

畳み込み関数はLispの方が好きかな。
オプショナル引数で動作と初期値を指定できる。

CL-USER > (reduce #'-
                  (loop for x from 1 to 5 collect x)
                  :initial-value 0)
-15

CL-USER > (reduce #'-
                  '(1 2 3 4 5)
                  :from-end t)
3

わかりやすい例は

CL-USER > (reduce #'list '(1 2 3)
                  :initial-value 0)
(((0 1) 2) 3)

CL-USER > (reduce #'list '(1 2 3)
                  :initial-value 0
                  :from-end t)
(1 (2 (3 0)))