第一回 Erlang 基礎勉強会 に行ってきました -2-
後半は、関数型言語としてのErlangの話が中心でした。途中例としてのソースを使った説明がありましたが(そのソースは公開されています。)、ハンズオンではなかったので、その時は自分で実行はしませんでした。後日ソースが公開されましたので、それを参考に、自分でコンパイルし実行してみながら復習した備忘録です。参考リソースは以下。
関数
ここからは、アトム、タプル、リスト等のデータ構造の話がちょくちょく出てきます。それぞれを把握していないと、ついて行けなくなります。以下を参照すると良くわかります。Erlang のおはなし (2)-Re:Creator's Kansai （リクリ）
関数の定義
- アリティー(Arity)が引数の数にあたるもの。
- アリティーの数が違えば、同名でも別の関数になる。
- 最初のexportは外部から呼び出せる関数を定義していることになるらしい。
- サンプル最後のIO/fwriteは実行すると"variable 'IO' is unbound"となった、小文字にしたら実行できた。
サンプルの実行方法は以下。
hostname:erlang host$ erl ・・・ 1> c("my_module.erl"). %c("ファイルパス"). でコンパイルとロード {ok,my_module} 2> my_module:greet(). %モジュール名:関数名 で実行 Hello Erlang ok 3> my_module:greet("World"). %引数を渡してみる Hello World ok
二個目の引数ありのgree(Target)も公開されているので、引数を渡して呼び出せる。
パターンマッチ
- リストやタプルを分解することが出来る。
- Haskellとは異なり、k+1は使えない。
- バイナリも扱えるが、今回は省略
- ソース中の"_Other"等の"_"は、「これは必要ない」ということを意味しているらしい。そして本来は、"_"だけでもいいのだが、それだと可読性が下がるので、補足説明的に名前をつけたりする。もし"Other"としていてもいいが、Otherは束縛された値を使用しないので、コンパイルで「使用されない値がある」的なエラーになるらしい。car,cdrについては、リストのマッチ。後で「ペアのペア」の説明でわかる。
ちなみにサンプルを以下のように実行すると
8> pattern_match:dog_or_cat("dog"). false 9> pattern_match:dog_or_cat('dog'). true
となったことからも、"dog" は文字列、'dog'はアトムで別々のものとういうのがわかる。
ガード条件
- 関数はBIFsのみ使用可能
- BIFsは erl -man erlang を参照
- BIFsとは、C言語で書かれたライブラリモジュールのようです。Cで書かれているため、Erlangよりも高速に動作するため、BIFsにあるのならそちらを使うべきとのこと。(こちらを参考にしました:Erlang Tips)
- ガード条件とは、関数と戻り値の間に "when 真偽を返す式" を書くことで、条件分岐が出来る。
- when 構文は if ガード条件 の繰り返しで書くことが出来る。
- ガード条件は副作用が無い必要があるため、BIFsしか使えない。
- サンプルソースは、これを利用して絶対値を返す関数になっている。また、9行目は abs1(X) -> 0. は、束縛したXを使用しないため、本来は abs1(_X) -> 0. としないと以下のようなエラーが出る。
11> c("guard.erl"). ./guard.erl:9: Warning: variable 'X' is unused ./guard.erl:20: Warning: variable 'X' is unused error
- 同じく、20行目のXも使用しないので_をつけた。Erlangでは束縛した値が使用するのか、しないのかに注意する必要があることがわかる。
- ケースと関数の使い分けについて。
- 簡単な処理であれば、caseでも関数でも書ける場合がある。そこで関数で書く場合とcaseで書く場合の比較の話をされていたが、ここはメモりきれなかったし、思い出せない。ただ、そこでここまでの話からすると、パターンマッチをする場合はcase、ガードが使用したいときは関数という感じなのかと思う。結局Javaでいう if か caseかと同じだと仮定すれば、適材適所なのだろう。
高階関数。
- 無名関数
- A=fun 式 end. で無名関数を作ることが出来る。
- 関数を束縛することが可能。
- ガード、パターン等を使うことが出来る。
- 関数は引数として渡せる。
- 関数を返すことも出来る。
- 以下は関数を作る関数になっている。
- F3のクロージャがF4を定義している。(語弊があるかも)
10> F3=fun(X)->fun(Y)->X+Y end end. #Fun<erl_eval.6.13229925> 11> F4=F3(1). #Fun<erl_eval.6.13229925> 12> F4(1). 2 13> F5=F3(10). #Fun<erl_eval.6.13229925> 14> F5(1). 11
これはJavaScriptで書くとこんな感じ。
F3=function(X){ return function(Y){ return X+Y; } } F4=F3(1); alert(F4(1)); //2
また作成した関数は全て束縛されているので、b().で確認できる。
7> b(). F3 = fun(X) -> fun(Y) -> X + Y end end F4 = fun(Y) -> X + Y end F5 = fun(Y) -> X + Y end ok
関数が束縛されているのが良くわかる。
リスト
- Erlangは[X|Y]でペアを表現する。
- [X|Y]のXとYにはどんな型でも入る。
- リストとは、ペアのペア(ペアのネスと)である。
- その意味で、Erlangにはリストというものは無い。
- ペアーはcar,cdrのイメージ。
つまり、
>[1,2,3]
は
>[1|[2|[3|[]]]].
のシンタックスシューガー
タプル
- Tupleは組を表す。
- Tuple=長さが決まっている。
- List=決まっていない。
- Tupleの方が空間効率がいい。
- Tupleを用いるべきところでリストを使わない。
文字列
- Erlangの文字列は数値のリスト。
- 文字は全部数値のリストなので、文字列処理がリストで可能。
- 逆に数字のリストを評価すると、気を利かせて文字列が返る。
17> "日本". #文字列を評価する。 [26085,26412] #数値のリストが返る 18> [40,65,41]. #数値のリストを評価する "(A)" #文字列が返る。
-
- これを利用してリストの再起処理に文字列を使ったりできる。
- 実は文字列に強かったりする。
また、脱線したとき、CouchDBとSpidermonkeyの話があった。CouchDBの中のMapReduceは、spidermonkeyがJavaScriptを実行しているというもの。何となく聞いたことのある話ではあったが、きちんとはわかってないのでこの辺を参考にさせていただき後で調べる。
リスト
- リストの連結は++で行う。
- しかし、[X|XS]の方が速い。
- X++XSは後ろに繋ぎ、[X|XS]は頭に繋ぐ。
- 後ろに繋ぐ場合は、[X|XS]で頭に付けてlists:reverse()した方が速い。(listsはBIFsなので速い。)
具体例は無かったが、こういうことだと思う。
19> CAR=fun([X|XS]) -> X end. %パターンマッチしてペアを分解する関数。 #Fun<erl_eval.6.13229925> 20> [[A|B]|C]. [[[1,2],3,4],5,6] % ペアでくっ付けた結果 21> CAR([[A|B]|C]). [[1,2],3,4] 22> [A|B]++C. [[1,2],3,4,5,6] % ++でくっ付けた結果 23> CAR([A|B]++C). % パターンマッチしたときに、こうなるためには。。。 [1,2] 24> lists:reverse([C|lists:reverse([A|B])]). %こうやってくっ付けて。。 [[1,2],3,4,[5,6]] 25> CAR(lists:reverse([C|lists:reverse([A|B])])). %するとこう？ [1,2]
ホントか？(汗)
しかし、[X|Y]の連結は「XをYのリストの先頭に追加する」ということになっているので、上述の通り++とは違う振る舞いになっている。つまり最初に定義したCAR関数で切り出す場所が、パイプでの連結と++での連結ではかわる。しかし、++での連結をパイプで表現するためには、reverseを２回する必要がありそうだが、さすがにそれはオーバヘッドな気がする。BIFsはCで書かれてるからこれでも速いのかもしれない。もう少し慣れたらベンチマークを取ってみよう。
- リストの差分は--で行う。
- 差分なので、対応する数しかとらない。
18> [1,1,2,3]--[1]. %差分を取る [1,2,3] % 1は一つだけしか消えない。(1が全部消える訳ではない。)
内包表記
- [X*X || X <- lists:seq(1,5)].
- X*X は構築子、式や関数も可能
- X <- lists:seq(1,5) は生成器
- X のスコープは内包表記内
- ','で区切ると複数の生成器を列挙できる。
- その場合全ての要素の組み合わせが得られる。
- 生成器は左から評価される。
- パターンマッチを使用できる。
- 生成器の後ろにフィルタを記述できる。
- フィルタはBool値を返す式。
- 内包表記と無名関数で、素数を返す関数を記述。
-module(prime). -export([prime/1]). prime(N) -> % 1〜Nまでの素数を調べたい。 [X || X <- lists:seq(2, N), % 2〜Nの値を生成し、一個ずつ下のフィルタで評価。 (fun (Y) -> % Yが素数かどうか評価している。 case [Z || Z <- lists:seq(1, Y), Y rem Z =:= 0] of % 1〜Yまでの値でYを割ったリストを作成。 [1, Y] -> true; %そのリストの中身が1と自分しかなければそれは素数。 _Other -> false %それ以外のものもリストにあったら、素数ではない。ex) [1,2,4] end end)(X) % これは無名関数で最後に引数を渡して実行している。 ].
caseを持った無名関数をフィルタを作成し、それを内包表記のフィルタに使っている。
再起
- erlangはループがないので、全て再起で書く。
- リストを与えると、合計を返す関数の例。
- リストの中身が数値だったら累積器に加算していく。
sum2(XS) -> sum2(XS, 0). % 累積器を初期化し、下を呼び出す。 sum2([], Acc) -> Acc; % リストが空なら累積器を返す。 sum2([X | XS], Acc) when is_number(X) -> sum2(XS, X + Acc); % リストを分解し、先頭が数字なら加算器に加え再起。 sum2([_X | XS], Acc) -> sum2(XS, Acc). % リストの先頭が数字じゃなかったら、それだけ捨てて再起。
しかし、これは累積器無しで書くことが出来る、
sum1([]) -> 0; % 空なら0を返す。 sum1([X | XS]) when is_number(X) -> X + sum1(XS); % リストを分解し、先頭が数値ならそれにcdrの部分の再起を加える。 sum1([_X | XS]) -> sum1(XS). % リストの先頭が数字じゃなかったら、それだけ捨てて再起。
- サンプルの、sum.erlを実行してみる。
- これは、ベンチマークテストを仕込んであるので、一緒にbench.erlも呼んでテストしてみる。
3> c("sum.erl"). {ok,sum} 4> sum:sum1([1,2,3,4,5]). % 累積器無し 15 5> sum:sum2([1,2,3,4,5]). % 累積器有り 15 7> c("bench.erl"). % ベンチマークを読みこむ {ok,bench} 8> sum:test(10). % 実行する。 [{55,0,0},{55,0,0}] 9> sum:test(100). [{5050,0,0},{5050,0,0}] 10> sum:test(100000). [{5000050000,20,23},{5000050000,10,6}] % 値を大きくすると差がわかる。
isortの実装
これらをふまえて insert-sort を実装する。
isort1()
- insert をする関数
- それを呼び出す関数に分かれている。
- 2行目の [Y | _YS]=XS はXS自身以外にXSの先頭が欲しかったため、パターンマッチで後ろを捨てている。
insert1(X, []) -> [X]; %空なら終わり。 insert1(X, [Y | _YS]=XS) when X =< Y -> [X | XS]; %インサートする。 insert1(X, [Y | YS]) -> [Y | insert1(X, YS)]. %インサートしない。 isort1([]) -> []; isort1([X | XS]) -> insert1(X, isort1(XS)).
言葉では説明しにくいが、再起はこんな感じで行われるはず。
isort([4,2,5,1]). insert(4 , isort1(2,5,1)). insert(4 , insert(2 , isort([5,1]))). insert(4 , insert(2 , insert(5 isort(1)))). insert(4 , insert(2 , insert(5,[1])). insert(4 , insert(2 , [1,5])). insert(4 , [1,2,5]). [1,2,4,5]
つまり、isort()で呼び出している insert1() は iserot() を評価しないと戻らないし、insert1() の3行目も、insert1() の評価が戻らないとリストを生成できないので、結果この再起は余り速くない。
他の例を見てみる。
isort2()
- 概要は以下のような感じ。
- 累積器を使用している。
- 空の累積器を常に用意し、要素の追加は既にソート済みの先頭との比較で行われる。
- 比較して追加した数値の方が大きければ、対象の数値は累積器に追加されていく。
- 使いする数値の方が大きくなった時点で、累積器の内部は逆順なので、リバースが入る。
- 重要なのは、遅延評価しないで済むということだろうか。
再起を考える順番
- 再起慣れしていない人向け、再起を考える順番の話。
- 再起を考える順番
- 引数と返り値を決める
- 場合分けをする。
- 簡単な方を定義する。
- 複雑な方を定義する。
- 最適化する。
再起実装演習
- list:seq/2を実装してみる。
- seq(1,10). が[1,2,3,4,5,6,7,8,9,10].を返す関数。
- 先ほどの考え方を参考に作ってみた。累算器を使う方で書いてみる。
-module(test). -export([seq/3]). -export([seq/2]). seq(X,Y) -> seq([],X,Y). seq(ACC,X,X) -> [X|ACC]; seq(ACC,X,Y) when X<Y -> seq([Y|ACC],X,Y-1).
- １個づつ作って累算器の頭に加えていく。その際リバースしないでいいように、大きい方からつなげていった。
- seq(X,Y) when X>Y はlists:seq()だとエラーになるので考えなかった。
実行結果は以下
79> c("test.erl"). {ok,test} 80> test:seq(1,5). [1,2,3,4,5] 81> test:seq(5,5). [5]
多重再起
- いわゆる多重再起。
- 末尾再起ではない。
- スタックオーバーフローの可能性あり。
相互再起
- kai_tcp_server_acceptorで使用されている。
- 中で以下の二つが相互に呼び合っている。
- recv/5
- call_mod/6
listsモジュール
- リストを操作するための標準モジュール。
- よく使うもの
- foreach(func,[])
- map
- filter
- foldl(r)
- これらをつないで使ったりする。
lists:foreach/2
- リストの各要素に関数を適応。
- 第一引数の関数を、第二引数のリストの各要素に適応。
- foreachを再起で定義すると以下のようになる。
foreach(_F,[]) -> ok; % リストが空なら終わり。 foreach(F,[X|XS]) -> F(X),foreach(F,XS); % リストの頭に関数を適用。残りを再起。
正直実行結果がokだけなので、どういう用途が有るかこれだけだと良くわからない。全部の要素に適応しても、それがリストで返ってくる訳ではないから、取得は出来ない。むしろ、リストの中身が条件を見たしているかをチェックしたりする用途なのだろうか。ちょっとその辺も後で調べてみよう。
lists:map/2
- リストの各要素に関数を適応し、新しいリストを返す。
- 第一引数の関数を、第二引数のリストの要素に適応した結果でリストを構築。
- mapを内包表記で定義すると以下のようになる。
map(F,XS) -> [F(X) || X<-XS]. % リストの中から１つづつ取り出し、関数を適用。
こちらは、とてもわかりやすい。リストに対してのダイレクトな操作になっているから、多用しそう。
lists:filter/2
- リストの条件を満たす要素を取り出す。
- 第一引数の関数、第二引数のリストの要素に適用し、真を返すもののみでリストを構築する。
- filterを内包表記で定義すると以下のようになる。
filter(F,XS) -> [X || X <- XS , F(X) ]. % リストから１つづつ取り出した値を、二つ目の関数で評価。 % ','は'and'なので、真偽を返す関数を渡せば、間引くことが出来る。
こちらもわかりやすい。でもこうなると、foreach/2 はこれの戻り値が無い版というイメージでいいのだろうか？
lists:foldl/3
- リストを左から畳む。(foldrは右から。)
- わかりやすく言うと、左から累積器に積み込む。
- foldlは末尾再起だが、foldrは遅延評価になり末尾再起ではない。(遅い)
- リストが非対称でないとか言うらしい。
- 累積器を foldl で書き直せれば list わかってる認定。
- 課題として、foldlとfoldrの定義があるが、こちらの答えは公開されて無いので自分で考えてみる。
- その前に、使い方をみる。
lists:reverse/1 をfoldl/3で実装。
reverse(XS) -> lists:foldl( % 引数は三つ。 fun (X,ACC) -> [X|ACC] end. % 適応する関数、一つの要素を累積器の頭に追加。 [], % 空の累積器。 XS % リスト。 ).
なるほど、第一引数の関数は、リストの１要素と累積器が引数になるのか。
lists:map/2 をfoldl/3で実装。
map(F,XS) -> lists:foldl( fun (X,ACC) -> ACC ++ [F(X)] end, % 適応する関数 [], % 空の累積器 XS % リスト ).
こちらも、リストの頭から関数を適応し、リストに順番につめている。末尾につけるために++を使っているが、これは速度の問題が有ると言っていたから、lists:reverseを使って以下のように書いてみる。
map(F,XS) -> lists:foldl( fun (X,ACC) -> [F(X)|ACC] end, % 適応する関数 [], % 空の累積器 lists:reverse(XS) % リストをここで逆にしてみる。 ).
するとエラーが出た。
11> myLists:myMap(F,X). ** exception error: undefined function lists:revers/1 in function myLists:myMap/2
これはスコープの問題なんだろうか、myMap()内にlists:reverse/1 は定義されていないとのこと。後で調べよう。
foldl/3 の実装
- 使い方もわかってきたので実装してみる。
- 仕様(予測)
- アリティーは３つ、(関数、累積器、リスト)
- リストの中から１づつ取り出し、関数を適応し、累積器につめる。
myFoldl(_F,ACC,[]) -> ACC; myFoldl(F,ACC,[X|XS]) -> myFoldl(F,F(X,ACC),XS).
こんな感じか。
foldr/3 の実装
- 同様に実装。
- foldlの逆順に畳み込む。
- 末尾再起にはならない。
myFoldr(_F,ACC,[]) -> ACC ; myFoldr(F,ACC,[X|XS]) -> F(X,myFoldr(F,ACC,XS)).
filter/3 をFoldlで実装
- 仕様(内包表記では)
- filter(F,XS) -> [X || X <- XS , F(X) ].
- 方針としてはケースで間引くのが良さそう。
myFilter(F,XS) -> lists:foldl( fun(X,ACC) -> case F(X) of true -> [X|ACC]; false -> ACC end end, [], XS).
ガードでも出来そうか後で考えてみる。
まとめ
非常に長くなりましたが、かなりじっくり復習したおかげで大分雰囲気をつかむことが出来ました。そのため、年内にやり終えることが出来ず、年末はずっとErlangづけでした。途中で書いているコードは間違いだらけかもしれませんが、気がついたら直していきます。
とにかく、３時間近くの勉強会(もはや授業)だったので、とにかく内容が濃くて、得るものがたくさん有りました。特に僕のように本当にErlang初心者だった人間にもわかりやすく、スライドも、サンプルのソースも凄く参考になりました。改めて主催のcooldeamonさんには感謝いたします。
まだまだ理解しきれていないところがたくさん有りますが、これでとりあえず入り口は開けられたと思うので、こっからどんどん広げていければと思います。
