lists:foldl/3
つい何年か前までは「fold って何？うまいの？」とか言ってたわしだけど、すっかり関数型脳になった今では fold が無い生活なんて考えられない。
map やら foreach は分かるけど、 fold が良く分かりません!
ボクも fold を使いこなしたいです ＞ｗ＜
ということで、調べてみました。
こんな風に使います
> lists:foldl(fun(X, Sum) -> X+Sum end, 0, lists:seq(1,10)).
55
リスト [1,2,3,4,5,6,7,8,9,10] のそれぞれの要素を 足していく式です。
うーん。分ったような分からんような。
それぞれの引数が何を表しているのか、どういう流れで値が変化しているのかが分りにくいや!
困ったときは原典に
foldl(Function, Acc0, List) -> Acc1
Types:
Function = fun(A, AccIn) -> AccOut
List = [A]
Acc0 = Acc1 = AccIn = AccOut = term()Acc0 is returned if the list is empty.
引数が何を表しているのかに注目します。
- lists:foldl/3 の引数を、頭から Function, Acc0, List とします。
- Function は arity 2 (= 引数の数が 2 つ) の関数です。それぞれ A, AccIn とします。
- A はリストの要素です。(foldl の場合、リストの左から要素を取り出します。)
- AccIn は、現在の状態です。
- Acc0 は、初期状態です。
- L は処理対象の要素のリストです。
- L が 空リスト (= []) の場合、結果は Acc0
- Function は arity 2 (= 引数の数が 2 つ) の関数です。それぞれ A, AccIn とします。
最初の例を振り返ると、リストの各要素に対して、
新しい状態 = 要素 + 現在の状態
を行っていることになるんですねー。
動きを詳しく追う
lists:foldl/3 を使った階乗のサンプルの動きを追ってみましょう。
% 5 の階乗
> L = lists:seq(1,5).
[1,2,3,4,5]
> Acc0 = 1.
1
> lists:foldl(fun(E, AccIn) -> E*AccIn end, Acc0, L).
120
状態が変化しつつ持ち越されていることがポイントです。
- リストの最初の要素 1 と 初期状態 1 との積 1 が新しい状態となる
- リスト次の要素 2 と 現在の状態 1 との積 2 が新しい状態となる
- リスト次の要素 3 と 現在の状態 2 との積 6 が新しい状態となる
- リスト次の要素 4 と 現在の状態 6 との積 24 が新しい状態となる
- リスト次の要素 5 と 現在の状態 24 との積 120 が新しい状態となる
表にするとこんな感じです。
| Elem | AccIn | AccOut |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 3 | 2 | 6 |
| 4 | 6 | 24 |
| 5 | 24 | 120 |
一般化してみます。
- 初期状態 (=Acc0) とリストの最初の要素 (=E0) とで Function し、新しい状態 (=Acc1) になる
- Acc1 と E1 とで Function し、Acc2 になる
- Acc2 と (ry
- AccN-1 とEN-1 とで Function し、最後の状態 となる
- 最後の状態 を 返す
foldr と foldl
ちなみに、foldr より foldl の方が末尾再帰を利用しており効率的なのだそうです。
特別な理由がない限り foldl を使うようにすると幸せになれるかもしれません。
foldr differs from foldl in that the list is traversed "bottom up" instead of "top down". foldl is tail recursive and would usually be preferred to foldr.
