8. 高階関数

8.1. 関数型っぽくいこう!

../_images/lambda1.png

すべての関数型プログラミング言語での重要なのは定義した関数を持ってきて他の関数へパラメータとして渡すことができる、という点です。 そのあと、この関数パラメータを関数内の他の変数と同じように変数に束縛して利用出来るのです。 このように関数を渡される関数を 高階関数 といいます。 高階関数はErlangにおいて強力な抽象化の手段であり、最も習得しがいのあるツールの一つです。

また、この概念は数学に端を発していて、主に ラムダ計算 と呼ばれています。 ラムダ計算については深入りしません。なぜなら理解するのは厳しいと感じる人もいますし、いささか範囲外だからです。 しかし、数字も含めて、すべてが関数であるシステムとして簡単に定義してみようと思います。 すべてが関数なので、関数は他の関数をパラメータとして受け入れなければならず、もっと多くの関数で操作できなければいけません!

はい、これはちょっと奇妙に感じるかもしれないので、例から始めてみましょう:

-module(hhfuns).
-compile(export_all).

one() -> 1.
two() -> 2.

add(X,Y) -> X() + Y().

そしてErlangシェルを開いて、このモジュールをコンパイルして続けてみます:

1> c(hhfuns).
{ok, hhfuns}
2> hhfuns:add(one,two).
** exception error: bad function one
in function  hhfuns:add/2
3> hhfuns:add(1,2).
** exception error: bad function 1
in function  hhfuns:add/2
4> hhfuns:add(fun hhfuns:one/0, fun hhfuns:two/0).
3

ややこしいですか?どうやって動作するかわかればそうでもないでしょう。(いつもそうですよね) コマンド2では、 onetwo というアトムが add/2 に渡されています。 この両方のアトムを関数名( X() + Y() )として使っています。 関数名がパラメータなしで書かれた場合、それらの名前はアトムとして解釈されます。 そしてアトムは関数にはなれません。だから呼び出している部分で失敗しているのです。 これがコマンド3も失敗している理由です。値1と2は関数として呼び出せません。 ここでは関数が必要なのです!

これが、関数をモジュールの外から渡すために、新しい記述法が導入されなければならなかった理由です。 これが fun Module:Function/Arity です。この呼び出し方でVMに特定の関数を使うことを伝え、その関数を変数に束縛します。

このような関数を使うと何ができるのでしょうか?理解するにはちょっとした例が必要です。 いくつかの関数を hhfuns に追加します。 この関数はリストの各要素へ再帰的に加算/減算をします。

increment([]) -> [];
increment([H|T]) -> [H+1|increment(T)].

decrement([]) -> [];
decrement([H|T]) -> [H-1|decrement(T)].

この2つの関数がどれだけ似ているか見てください。基本的には同じことをしていますよね。リストをぐるっとたどって、それぞれの要素に関数( + または - )を適用して、再度自分自身を呼んでいます。 ほとんど一緒です。適用されている関数と再帰呼び出しの部分が異なるだけです。 リストへの再帰呼び出しのコアな部分はいつも一緒です。この似ている部分を抽象化して1つの関数( map/2 )にしましょう。 この関数は引数として他の関数を受け取ります:

map(_, []) -> [];
map(F, [H|T]) -> [F(H)|map(F,T)].

incr(X) -> X + 1.
decr(X) -> X - 1.

これをシェルでテストします:

1> c(hhfuns).
{ok, hhfuns}
2> L = [1,2,3,4,5].
[1,2,3,4,5]
3> hhfuns:increment(L).
[2,3,4,5,6]
4> hhfuns:decrement(L).
[0,1,2,3,4]
5> hhfuns:map(fun hhfuns:incr/1, L).
[2,3,4,5,6]
6> hhfuns:map(fun hhfuns:decr/1, L).
[0,1,2,3,4]

結果は一緒になりました。しかし後者はとてもスマートに抽象化されています! リストの各要素に関数を適用させたい場合はいつも map/2 を適用させたい関数と一緒に呼び出せばいいだけです。 しかし、 map/2 に渡したい関数を常にモジュールに書いて、名前をつけて、公開して、コンパイルしたりするのはちょっとじれったいですよね。 事実、ちょっと実用的ではありません。 その場で宣言できる関数が必要ですね...

8.2. 無名関数

無名関数、あるいは fun は、名前をつけないでも、特別なインライン関数を宣言することが出来るようにすることで、先程の問題を解決してくれます。 無名関数では普通の関数でできることは再帰呼び出し以外はすべてできます(無名だったらどうして呼べるでしょうか) 構文は次のとおりです:

fun(Args1) ->
    Expression1, Exp2, ..., ExpN;
   (Args2) ->
    Expression1, Exp2, ..., ExpN;
   (Args3) ->
    Expression1, Exp2, ..., ExpN
end

そして次のように使うことが出来ます:

7> Fn = fun() -> a end.
#Fun<erl_eval.20.67289768>
8> Fn().
a
9> hhfuns:map(fun(X) -> X + 1 end, L).
[2,3,4,5,6]
10> hhfuns:map(fun(X) -> X - 1 end, L).
[0,1,2,3,4]

いま、関数型プログラミングっぽくする一つの要素を見ています。とても低レベルなコードを抽象化できることです。 ループのような基本的な概念はこれによって無視され、どうやるかよりも何がされるかに集中することができます。

無名関数はすでにこういった抽象化においてかなり洗練されたものですが、さらに隠れた力を持っています:

11> PrepareAlarm = fun(Room) ->
11>                     io:format("Alarm set in ~s.~n",[Room]),
11>                     fun() -> io:format("Alarm tripped in ~s! Call Batman!~n",[Room]) end
11>                   end.
#Fun<erl_eval.20.67289768>
12> AlarmReady = PrepareAlarm("bathroom").
Alarm set in bathroom.
#Fun<erl_eval.6.13229925>
13> AlarmReady().
Alarm tripped in bathroom! Call Batman!
ok
../_images/batman1.png

電話を切るな、バットマン!何が起きてるんでしょう? ええっと、ます最初に無名関数を宣言してPrepareAlarmに束縛しました。 この関数はまだ実行されていません。 PrepareAlarm("bathroom") が呼ばれたときにだけ実行されます。 このとき、 io:format/2 の呼び出しが評価されて、”Alarm set”が出力されます。 2番目の式(もう1つの無名関数)が呼び出し元に返されて、 AlarmReady に束縛されます。 この関数内では、Roomという変数は「親の」関数( PrepareAlarm )に取られていることに注意してください。 これはクロージャと呼ばれる概念と関係があります。

クロージャを理解するには、まずスコープを理解しなければいけません。 関数のスコープはすべての変数とその値が保存されている場所としてイメージできます。 関数 base(A) -> B = A + 1. では AB はともに base/1 のスコープ内で定義されています。 これはつまり、 base/1 の内部ではどこでも、AとBを参照でき、それらに束縛された値を取得できます。 そして「どこでも」と行ったのは冗談ではありません。これは無名関数でも同様です。

base(A) ->
    B = A + 1,
    F = fun() -> A * B end,
    F().

BとAは base/1 のスコープに結び付けられています。なので関数Fはまだそれらにアクセスできるのです。 これは base/1 のスコープを継承しているからです。 実生活での様々な種類の継承とおなじように、親は子供の持っているものは取得できません:

base(A) ->
    B = A + 1,
    F = fun() -> C = A * B end,
    F(),
    C.

この関数の場合、 B はまだ A + 1 と等しくて、Fはまだちゃんと動いています。 しかし、変数CはFに束縛された無名関数のスコープ内だけです。 base/1 が最後にCの値にアクセスしようとすると、未束縛の変数と見てしまいます。 実際、この関数をコンパイルしようとすると、コンパイラは適合できません。 継承は1方向だけにしか働かないのです。

継承されたスコープは無名関数がどこにあってもちゃんと見えているというのは重要なので覚えておいてください。 たとえ他の関数に渡されたとしてもちゃんと見えています:

a() ->
    Secret = "pony",
    fun() -> Secret end.

b(F) ->
    "a/0's password is "++F().

これをコンパイルすると:

14> c(hhfuns).
{ok, hhfuns}
15> hffuns:b(hhfuns:a()).
"a/0's password is pony"

だれが a/0 のパスワードを伝えたのでしょうか? a/0 自身です。 無名関数が宣言されたときに a/0 のスコープを持っている一方で、先に書いたとおり b/1 で実行されたときにもまだそのスコープを持っています。 これはとても役に立ちます。なぜならこれでパラメータや元々のコンテキストからの内容をもち回すことができるからです。それがコンテキスト全体はもう必要ないような場合にも使えます。(ちょうど前の例でBatmanにしたような感じです)

あなたは多くの引数を持つ関数を定義したときに、たいがい状態を引き回すために無名関数を使うでしょう。 しかし定数も持てます:

16> math:pow(5,2).
25.0
17> Base = 2.
2
18> PowerOfTwo = fun(X) -> math:pow(Base,X) end.
#Fun<erl_eval.6.13229925>
17> hhfuns:map(PowerOfTwo, [1,2,3,4]).
[2.0,4.0,8.0,16.0]

無名関数の中で math:pow/2 の呼び出しをスコープ内のBase変数とラップすることで、 hhfuns:map/2 の中でPowerOfTwoの呼び出しが出来、リスト内の整数をBaseの累乗にすることができます。

無名関数を書いているときに陥りやすい罠はスコープを再定義しようとするときに起きます:

base() ->
    A = 1,
    (fun() -> A = 2 end)().

このコードは無名関数を宣言して実行しています。 無名関数は base/0 のスコープを継承しているので、 = 演算子は2と変数 A を比較しようとします。(Aは1に束縛されています) これは間違いなく失敗します。しかしもし入れ子になった関数の先頭であれば変数を再定義できるのです:

base() ->
    A = 1,
    (fun(A) -> A = 2 end)(2).

これは動きます。これをコンパイルしてみると、シャドーイングについての警告がでます。 (“Warning: variable ‘A’ shadowed in ‘fun’”). シャドーイングとは新しい変数を親のスコープで定義されているのと同じ名前で定義するような行為を表す言葉です。 ミスを避けるためにこういった名前が付けられています。(たいていミスの原因となります) なので、こういう場合は変数名を最高することをおすすめします。

../_images/erland1.png

無名関数に関する理論はちょっと置いといて、前の章の最後のほうでお約束した、再帰関数を書くことを避ける一般的な抽象化について色々と見てみましょう。

8.3. Map, filter, fold などなど

この章の始めで、 map/2 関数を使ってどうやって2つの似た関数を抽象化するか簡単にお見せしました。 map/2 関数は各要素に対して何かさせたい時にはどんなリストにも使えるといいました。 定義は次のようなものでした:

map(_, []) -> [];
map(F, [H|T]) -> [F(H)|map(F,T)].

しかし、よく書かれる再帰関数も同様に抽象化されることが多々あります。 まずはこの2つの関数について見てみましょう:

%% only keep even numbers
even(L) -> lists:reverse(even(L,[])).

even([], Acc) -> Acc;
even([H|T], Acc) when H rem 2 == 0 ->
    even(T, [H|Acc]);
even([_|T], Acc) ->
    even(T, Acc).

%% only keep men older than 60
old_men(L) -> lists:reverse(old_men(L,[])).

old_men([], Acc) -> Acc;
old_men([Person = {male, Age}|People], Acc) when Age > 60 ->
    old_men(People, [Person|Acc]);
old_men([_|People], Acc) ->
    old_men(People, Acc).

最初の関数は数字のリストを受け取って偶数のものだけ返します。 2つ目の関数は {性別, 年齢} という形式の人間のリストをたどって、60歳以上の男性だけ残すというものです。 類似点を探すのはちょっと難しいですが、共通点を見つけました。 両方の関数ともにリストを操作して、なんらかのテストを通過した要素だけ残すという目的を持っています。 ( 属性 ともいいます)そして残りを捨てます。 このような一般化から、必要な情報だけ抜きだして抽象化することができます:

filter(Pred, L) -> lists:reverse(filter(Pred, L,[])).

filter(_, [], Acc) -> Acc;
filter(Pred, [H|T], Acc) ->
    case Pred(H) of
        true  -> filter(Pred, T, [H|Acc]);
        false -> filter(Pred, T, Acc)
    end.

フィルタ関数を使うには、テスト関数だけを用意してやればいいことになります。 hhfuns モジュールをコンパイルして試してみます:

1> c(hhfuns).
{ok, hhfuns}
2> Numbers = lists:seq(1,10).
[1,2,3,4,5,6,7,8,9,10]
3> hhfuns:filter(fun(X) -> X rem 2 == 0 end, Numbers).
[2,4,6,8,10]
4> People = [{male,45},{female,67},{male,66},{female,12},{unkown,174},{male,74}].
[{male,45},{female,67},{male,66},{female,12},{unkown,174},{male,74}]
5> hhfuns:filter(fun({Gender,Age}) -> Gender == male andalso Age > 60 end, People).
[{male,66},{male,74}]

これらの2つの例は filter/2 関数を使うことで、プログラマは属性を作ることとリストを作ることだけ考えればよくなります。 リストをたどっていらない要素を捨てるという動作については考えなくていいのです。 これは抽象的な関数型のコードを考える上で大事な点です。常に同じものは取り除いて、プログラマに変化する部分だけ作らせるのです。

前の章で挙げた他の再帰的な操作の例としては、リストのすべての要素をみて1つの答えに収束させるというものでした。 これは畳み込み(fold)と呼ばれるもので、次のような関数で使えます:

%% find the maximum of a list
max([H|T]) -> max2(T, H).

max2([], Max) -> Max;
max2([H|T], Max) when H > Max -> max2(T, H);
max2([_|T], Max) -> max2(T, Max).

%% find the minimum of a list
min([H|T]) -> min2(T,H).

min2([], Min) -> Min;
min2([H|T], Min) when H < Min -> min2(T,H);
min2([_|T], Min) -> min2(T, Min).

%% sum of all the elements of a list
sum(L) -> sum(L,0).

sum([], Sum) -> Sum;
sum([H|T], Sum) -> sum(T, H+Sum).
../_images/foldr1.png

foldがどのように動作すべきかを見つけたいなら、これらの関数での共通点と相違点を探す必要があります。 上で言ったとおり、リストから1つの値に減らす必要があります。 結果的に、foldはイテレーションと1つの要素を保存することだけ考えていればよく、リストの作成は必要ありません。 ガードは無視して構いません。なぜなら常にガードがあるわけではないからです。 ガードはユーザの関数の中にあればよいのです。 こういった観点から、畳み込み関数は合計関数(sum)と似ているとも言えます。

これら3つの関数でまだ触れていないところで捉えにくい点は、すべての関数には数えはじめるときに初期値が必要だということです。 sum/2 の場合は、足し算をするので0を初期値とします。 X = X + 0 とすれば、値は中立で計算をめちゃくちゃにすることは出来ません。 掛け算をするなら、1を初期値として X = X * 1 とすればいいでしょう。 関数 min/1max/1 は初期値を持てません。 もしリストに負数しかなければ、初期値は0したら答えは間違ってしまいます。 そのような場合はリストの最初の要素を初期値にします。 悲しいことに、常にこういった具合に簡単に決められるわけではないので、このような判断はプログラマに委ねられています。 これらの要素を取り入れて、次のように抽象化をすることができます:

fold(_, Start, []) -> Start;
fold(F, Start, [H|T]) -> fold(F, F(H,Start), T).

では試してみましょう:

6> c(hhfuns).
{ok, hhfuns}
7> [H|T] = [1,7,3,5,9,0,2,3].
[1,7,3,5,9,0,2,3]
8> hhfuns:fold(fun(A,B) when A > B -> A; (_,B) -> B end, H, T).
9
9> hhfuns:fold(fun(A,B) when A < B -> A; (_,B) -> B end, H, T).
0
10> hhfuns:fold(fun(A,B) -> A + B end, 0, lists:seq(1,6)).
21

リストを1要素に減らすような考えうるどんな関数でもfoldとして表現できます。

おもしろいのは、アキュムレータを1要素として(あるいは1変数として)表現でき、アキュムレータはリストにもなれるということです。 それ故、foldをリストを作るときにも使えます。 これはつまりfoldがリストに対してどんな再帰関数を作るときにもfoldを使えるということです。たとえそれがmapだろうとfilterだろうとです:

reverse(L) ->
    fold(fun(X,Acc) -> [X|Acc] end, [], L).

map2(F,L) ->
    reverse(fold(fun(X,Acc) -> [F(X)|Acc] end, [], L)).

filter2(Pred, L) ->
    F = fun(X,Acc) ->
        case Pred(X) of
            true  -> [X|Acc];
            false -> Acc
        end
    end,
    reverse(fold(F, [], L)).

これらは前に手で書いたものと同様に動作します。なんて強力な抽象化でしょう!

map, filter, foldはErlangの標準ライブラリで提供されているリストに対する多くの抽象化機能の一つです。 ( lists:map/2, lists:filter/2, lists:foldl/3 and lists:foldr/3 を各々参照のこと) all/2any/2 はテストを受け取って、前者はすべての要素が、後者は少なくとも1つの要素がtrueを返すか判定する関数です。 dropwhile/2 はリストを頭からたどっていって、条件に一致する要素が出てくるまで、それ以前の要素を捨てます。 逆に takewhile/2 は条件に一致しない要素が出てくるまで要素を保持します。 今の2つの関数の補完的な関数としては partition/2 です。これはリストを受け取ってそれを2つに分けます。1つは条件を満たす要素を集めたもので、もう1つはそうでないもののを集めたものです。 他によく使われるリスト関数としては flatten/1, flatlength/1, flatmap/2, merge/1, nth/2, nthtail/2, split/2 などがあります。

ほかにも zip関数(あとの章で触れます)やuznip関数、それらをmapやfoldと組み合わせたものなどがあります。 リストのドキュメント を読んで、何が出来るか確認することをおすすめします。 読めば、賢い人達がすでに抽象化してくれた関数を使えば自分で再帰関数を書く必要なんてほとんどないことを思い知らされます。