再帰定義とリスト操作
今回は再帰定義を使ってリストを操作する関数を作ってみましょう。
●リスト操作の基本
最初にリストを操作する基本的な関数を作ります。先頭の要素を求める関数 head/1 と、先頭の要素を取り除いた残りのリストを求める関数 tail/1 は、リストのパターンマッチングを使えば簡単にプログラムできます。
リスト : head/1 と tail/1 -module(lst). -export([head/1, tail/1]). head([X | _]) -> X. tail([_ | Xs]) -> Xs.
これだけで OK です。では、実行してみましょう。
> lst:head([1, 2, 3, 4]). 1 > lst:tail([1, 2, 3, 4]). [2,3,4]
head も tail もリストとパターン [X | Xs] をマッチングさせ、必要なデータを取り出します。なお、Erlang には同等の機能を持つ組み込み関数 hd/1, tl/1 が用意されています。
> hd([1, 2, 3, 4]). 1 > tl([1, 2, 3, 4]). [2,3,4]
次に、リストの先頭にデータを追加する関数を作りましょう。
リスト：先頭にデータを追加 cons(X, Y) -> [X | Y].
名前は Lisp / Scheme の関数 cons から拝借しました。これも簡単ですね。実行結果を示します。
> lst:cons(1, 2). [1|2] > lst:cons(1, []). [1] > lst:cons(1, [2]). [1,2] > lst:cons(1, [2, 3, 4, 5]). [1,2,3,4,5]
hd, tl, cons の関係を図に表すと次のようになります。
この関係はリストを操作する関数を作る場合の基本になります。
●参照
それでは、再帰定義を使ってリストを操作する関数を作りましょう。実は、リスト操作と再帰定義は相性がとても良いのです。まず、リストの n 番目の要素を求めるプログラムを作ってみましょう。Lisp ではリストの要素を 0 から数えますが、Erlang では 1 から数えるようなので、これから作るプログラムもそれに従います。
リストはパターン [X | Xs] とマッチングすると、X には先頭の要素が、Xs には残りのリストがセットされますね。したがって、n 番目の要素を求めるには、Xs とマッチングしたリストに対して n - 1 番目の要素を求めればいいわけです。これは、再帰定義を使えば簡単にプログラムすることができます。次のリストを見てください。
リスト：参照 nth(1, [X | _]) -> X; nth(N, [_ | Xs]) when N > 1 -> nth(N - 1, Xs).
関数 nth(N, Xs) は、リスト Xs の N 番目の要素を返します。最初の節で、N が 1 の場合は先頭の要素を取り出て返します。これが再帰定義の停止条件となります。
次の節では、パターンマッチングを使ってリストを分解しています。第 2 引数に与えられるリストは [_ | Xs] とマッチングするので、変数 Xs には残りのリストがセットされます。あとは、ガードで N の範囲をチェックして、nth(N - 1, Xs) を再帰呼び出しすればいいわけです。それでは実行してみましょう。
> lst:nth(1, [1, 2, 3, 4, 5]). 1 > lst:nth(5, [1, 2, 3, 4, 5]). 5 > lst:nth(0, [1, 2, 3, 4, 5]). ** exception error: no function clause matching lst:nth(0,[1,2,3,4,5]) > lst:nth(6, [1, 2, 3, 4, 5]). ** exception error: no function clause matching lst:nth(1,[])
正常に動作していますね。なお Erlang には nth と同様の動作を行う関数 nth/2 がモジュール lists に用意されています。
> lists:nth(1, [1, 2, 3, 4, 5]). 1 > lists:nth(5, [1, 2, 3, 4, 5]). 5
詳細はリファレンスマニュアル Erlang -- lists をお読みくださいませ。
●挿入
次は、リストの n 番目にデータを挿入する関数 insert_at/3 を作りましょう。insert_at(N, X, Xs) は、リスト Xs の N 番目にデータ X を挿入します。基本的な考え方は関数 nth/2 と同じです。リストを分解して、N が 1 になったらリストの先頭にデータを挿入します。これは簡単にできますね。あとは、取り除いたデータを再度挿入して、リストを組み立てていけばよいのです。プログラムは次のようになります。
リスト：挿入 insert_at(1, X, Xs) -> [X | Xs]; insert_at(N, X, [Y | Ys]) when N > 1 -> [Y | insert_at(N - 1, X, Ys)].
最初の節で、第 1 引数が 1 の場合はリスト Xs の先頭にデータ X を挿入します。次の規則で、再帰定義を使ってリストを分解します。insert_at の 3 番目の引数 [Y | Ys] で、リストは先頭要素 Y と残りのリスト Ys に分解されます。このリスト Ys に対して insert_at を再帰呼び出しします。返り値はリストなので、その先頭に取り除いた Y を追加します。この処理は関数 cons を使わなくても [Y | insert_at(...)] で行うことができます。これで分解したリストを再び組み立てることができます。
それでは、実行してみましょう。
> lst:insert_at(1, a, [1, 2, 3, 4, 5]).
[a,1,2,3,4,5]
> lst:insert_at(5, a, [1, 2, 3, 4, 5]).
[1,2,3,4,a,5]
> lst:insert_at(6, a, [1, 2, 3, 4, 5]).
[1,2,3,4,5,a]
> lst:insert_at(0, a, [1, 2, 3, 4, 5]).
** exception error: no function clause matching lst:insert_at(0,a,[1,2,3,4,5])
> lst:insert_at(-1, a, [1, 2, 3, 4, 5]).
** exception error: no function clause matching
lst:insert_at(-1,a,[1,2,3,4,5])
正常に動作していますね。
●削除
次は、データを削除する関数 delete_at/2 を作りましょう。delete_at(N, Xs) はリスト Xs の N 番目の要素を削除します。基本的な考え方は関数 insert_at/3 と同じです。リストを分解して、N が 1 になったらリストの先頭要素を削除するだけです。プログラムは次のようになります。
リスト：削除 delete_at(1, [_ | Xs]) -> Xs; delete_at(N, [X | Xs]) when N > 1 -> [X | delete_at(N - 1, Xs)].
最初の節は、N が 1 の時にリストの先頭要素を削除することを表しています。先頭要素を取り除いたリスト Xs を返します。次の節で、insert_at と同様にリストを分解して delete_at を再帰呼び出しします。そして、返り値の先頭に X を追加して、分解したリストを再び組み立てます。
それでは実行してみましょう。
> lst:delete_at(1, [1, 2, 3, 4, 5]). [2,3,4,5] > lst:delete_at(3, [1, 2, 3, 4, 5]). [1,2,4,5] > lst:delete_at(5, [1, 2, 3, 4, 5]). [1,2,3,4] > lst:delete_at(0, [1, 2, 3, 4, 5]). ** exception error: no function clause matching lst:delete_at(0,[1,2,3,4,5]) > lst:delete_at(-1, [1, 2, 3, 4, 5]). ** exception error: no function clause matching lst:delete_at(-1,[1,2,3,4,5])
●リストの長さ
次は、リストの長さを求める関数 length1/1 を作りましょう。 Erlang には length という同等の機能を持つ組込み関数が用意されていますが、再帰定義を使えば簡単に作ることができます。
まず、いちばん簡単な場合を考えます。引数が空リストであれば 0 を返せばいいですね。あとは、リストが空リストになるように分解していけばいいのです。つまり、リスト Xs の長さを求めるには、リスト Xs に tl を適用したリストの長さがわかればいい、と考えるのです。それに 1 を足せば、リストの長さを求めることができます。これをプログラムすると、次のようになります。
リスト : リストの長さを求める length1([]) -> 0; length1([_ | Xs]) -> 1 + length1(Xs).
length1 の引数が空リストであれば 0 を返します。そうでなければ、引数のリストを分解して length1 を再帰呼び出しします。リストを分解していくと最後は空リストになります。ここで再帰呼び出しが止まって 0 を返します。そうすると、1 + length1(Xs) によって length1 の返り値に 1 を足した値を返していきます。すなわちリストを分解した回数だけ 1 が加算されるわけです。
それでは実行してみましょう。
> lst:length1([1, 2, 3, 4, 5]). 5 > lst:length1([]). 0
正常に動作していますね。なお、length1/1 を末尾再帰で書き直すと次のようになります。
リスト : 末尾再帰版 length2([], A) -> A; length2([_ | Xs], A) -> length2(Xs, A + 1). length2(Xs) -> length2(Xs, 0).
lenght2/2 は引数 A を累積変数として使います。最初の節で、第 1 引数が空リストになったら A を返します。次の節で length2/2 を再帰呼び出しするときに A の値を +1 します。あとは、length2/1 から length2/2 を呼び出すだけです。このとき、累積変数 A は 0 に初期化します。
それでは実行してみましょう。
> lst:length2([1, 2, 3, 4, 5]). 5 > lst:length2([]). 0
正常に動作していますね。
●リストの連結
次はリストを連結する関数 append/2 を作ってみましょう。引数としてリスト Xs と Ys を渡して、それを連結したリストを返します。なお Erlang には、リストを連結する演算子 ++ があります。また、モジュール lists にはリストを連結する関数 append/2 が用意されています。
処理手順ですが、簡単な場合から考えていきましょう。まず、リスト Xs が空リストならば、リスト Ys を返すだけでいいですね。次に、リスト Xs に要素が複数ある場合を考えてください。リスト Xs をパターンマッチング [X1 | Xs1] で分解します。そして、Xs1 と Ys を連結したリストを求め、そのリストの先頭に X1 を追加すれば Xs と Ys を連結することができます。これを図に示すと次のようになります。
これをプログラムすると次のようになります。
リスト : リストの結合 append([], Ys) -> Ys; append([X | Xs], Ys) -> [X | append(Xs, Ys)].
最初の節で、第 1 引数が空リストであればリスト Ys をそのまま返します。これが再帰呼び出しの停止条件になります。そうでなければ、第 1 引数を [X | Xs] で分解し、Xs を append に渡して再帰呼び出しします。そして、その返り値の先頭に X を追加します。これでリストを連結することができます。
それでは実行してみましょう。
> lst:append([1, 2, 3], [4, 5, 6]). [1,2,3,4,5,6] > lst:append([], [4, 5, 6]). [4,5,6] > lst:append([1, 2, 3],[]). [1,2,3]
次はリスト Xs と Ys の要素を交互に並べたリストを返す関数 interleave/2 を作ります。次のリストを見てください。
リスト : リストの要素を交互に並べる interleave([], Ys) -> Ys; interleave([X | Xs], Ys) -> [X | interleave(Ys, Xs)].
関数 interleave は引数に 2 つのリストを受け取ります。そして、第 1 引数のリストの要素を新しいリストに格納したら、次は第 2 引数のリストの要素を新しいリストに格納します。これは interleave() を再帰呼び出しするとき、引数の順番を交換するだけです。これで 2 つのリストの要素を交互に並べることができます。
簡単な実行例を示しましょう。
> lst:interleave([1, 3, 5, 7, 9], [2, 4, 6, 8]). [1,2,3,4,5,6,7,8,9] > lst:interleave([], [1, 2, 3]). [1,2,3] > lst:interleave([1, 2, 3], []). [1,2,3]
●リストの反転
今度はリストの要素を反転する関数 reverse/1 を作ってみましょう。Erlang にはモジュール lists に同等の機能を持つ関数 reverse/1 が用意されていますが、私達でも簡単に作ることができます。reverse は引数のリスト Xs を [X1 | Xs1] で分解し、Xs1 を反転させてから X1 を最後尾に追加することで実現できます。次の図を見てください。
これをプログラムすると、次のようになります。
リスト 8 : リストの反転 reverse([]) -> []; reverse([X | Xs]) -> reverse(Xs) ++ [X].
最初の規則で、引数が空リストの場合は [ ] を返します。そうでなければ、reverse を再帰呼び出しして Xs を反転し、演算子 ++ で反転したリストの最後尾に先頭の要素 X を追加します。
それでは実際に試してみましょう。
> lst:reverse([1, 2, 3, 4, 5]). [5,4,3,2,1] > lst:reverse([]). []
正常に動作していますね。なお、このプログラムはリストを連結する ++ 演算子を使っているので、左辺のリストがコピーされてしまい、効率的ではありません。末尾再帰で書き直すと次のようになります。
リスト : 末尾再帰版 reversei([], A) -> A; reversei([X | Xs], A) -> reversei(Xs, [X | A]). reversei(Xs) -> reversei(Xs, []).
reversei/2 はリストを [X | Xs] で分解し、再帰呼び出しするときに X を累積変数 A の先頭に追加するだけです。これリストを逆順にすることができます。
それでは実行してみましょう。
> lst:reversei([1, 2, 3, 4, 5]). [5,4,3,2,1] > lst:reversei([]). []
●リストの探索
次は、リストからデータを探索する関数 member/2 を作ってみましょう。Erlang にはデータを見つけたら true を返し、見つからない場合は false を返す関数 member/2 がモジュール lists にありますが、私達でも簡単に定義することができます。
プログラムは次のようになります。
リスト : リストの探索 member(_, []) -> false; member(X, [X | _]) -> true; member(X, [_ | Xs]) -> member(X, Xs).
最初の節で、リストが空になったならばデータが見つからなかったので false を返します。次の節で、引数 X がリストの先頭要素と等しい場合は true を返します。最後の節で、リストを [_ | Xs] で分解し、member を再帰呼び出しして次の要素を調べます。
それでは、簡単な実行例を示します。
> lst:member(1, [1, 2, 3, 4, 5]). true > lst:member(3, [1, 2, 3, 4, 5]). true > lst:member(5, [1, 2, 3, 4, 5]). true > lst:member(0, [1, 2, 3, 4, 5]). false > lst:member(6, [1, 2, 3, 4, 5]). false
Lisp / Scheme の関数 member のように、要素が見つからない場合は空リストを返し、等しい要素が見つかったならば、それ以降のリストを返すこともできます。プログラムは次のようになります。
リスト : リストの探索 (2) member1(_, []) -> []; member1(X, [X | Xs]) -> [X | Xs]; member1(X, [_ | Xs]) -> member1(X, Xs).
2 番目の節で、X とリストの先頭要素が等しい場合はリスト [X | Xs] を返します。これで、Lisp / Scheme の member と同じ動作になります。
それでは実行してみましょう。
> lst:member1(1, [1, 2, 3, 4, 5]). [1,2,3,4,5] > lst:member1(3, [1, 2, 3, 4, 5]). [3,4,5] > lst:member1(5, [1, 2, 3, 4, 5]). [5] > lst:member1(10, [1, 2, 3, 4, 5]). []
●リストの生成
次は数列 (要素が整数のリスト) を生成する関数 iota(N, M) を作りましょう。iota は N から M までの整数を格納したリストを返します。たとえば、iota(1, 4) で生成されるリストは [1, 2, 3, 4] となります。なお、Erlang には同等の機能を持つ関数 seq/2 が lists モジュールに用意されています。また、増分値を指定できる seq/3 もあります。
プログラムは次のようになります。
リスト : リストの生成 iota(N, M) when N > M -> []; iota(N, M) -> [N | iota(N + 1, M)].
最初の節が再帰定義の停止条件です。N が M より大きい場合は空リストを返します。N が M 以下の場合、次の節が選択されます。iota を再帰呼び出しして N + 1 から M までのリストを生成し、その先頭に N を追加するだけです。
それでは実行してみましょう。
> lst:iota(1, 8). [1,2,3,4,5,6,7,8]
iota を末尾再帰に変換すると、次のようになります。
リスト : リストの生成 (末尾再帰) iotai(N, N, A) -> [N | A]; iotai(N, M, A) -> iotai(N, M - 1, [M | A]). iotai(N, M) when N > M -> []; iotai(N, M) -> iotai(N, M, []).
iotai/3 の引数 A が累積変数になります。iotai は iota とは逆に、M の値を減らしながらリストを生成していることに注意してください。第 1 引数と第 2 引数の値が等しい場合が再帰呼び出しの停止条件になります。
簡単な実行例を示します。
> lst:iotai(1, 8). [1,2,3,4,5,6,7,8]
●リスト内包表記
Erlang でリストを生成する場合、「リスト内包表記 (List Comprehensions)」を使うと便利です。基本的な構文を次に示します。
[式 || パターン <- 式, 条件式]
角カッコ [ ] の最初にリストの要素を生成する式 (コンストラクタ) を記述します。次に || で区切ったあと、"パターン <- 式" を記述します。これを「生成器 (generator)」と呼びます。式の値はリストでなければなりません。式はリストをそのまま指定してもかまいません。<- はリストの先頭から順番に要素を取り出し、パターンとマッチングを行います。また、カンマで区切ったあと、条件式を指定することができます。この条件式はガードとは違って、真偽値を返す関数であれば何でもかまいません。
簡単な例を示しましょう。
> [X * X || X <- [1, 2, 3, 4, 5]]. [1,4,9,16,25] > [X * X || X <- [1, 2, 3, 4, 5], X rem 2 =:= 0]. [4,16] > [X * X || X <- [1, 2, 3, 4, 5], X rem 2 =/= 0]. [1,9,25]
最初の例は要素を 2 乗したリストを生成します。次の例は、偶数の要素を取り出して 2 乗します。最後の例は奇数の要素を取り出して 2 乗します。
リスト内包表記は複数の生成器を指定することもできます。次の例を見てください。
> [{X, Y} || X <- [a, b, c], Y <- [1, 2, 3]].
[{a,1},{a,2},{a,3},{b,1},{b,2},{b,3},{c,1},{c,2},{c,3}]
これは次に示すリスト内包表記と同じ動作になります。
> [[{X, Y} || Y <- [1, 2, 3]] || X <- [a, b, c]].
[[{a,1},{a,2},{a,3}],
[{b,1},{b,2},{b,3}],
[{c,1},{c,2},{c,3}]]
リスト内包表記が入れ子になっていることに注意してください。最初に、X が a とマッチングし、それからコンストラクタで指定したリスト内包表記が動作します。したがって、X の値が a のままで、Y の値がリスト [1, 2, 3] とマッチングしてタプル {a, 1}, {a, 2}, {a, 3} が生成され生ます。次に、X の値が b に束縛されて内側のリスト内包表記が動作するので、タプル {b, 1}, {b, 2}, {b 3} が生成されます。最後に、X が c に束縛されてからリスト内包表記が動作するので、タプル {c, 1}, {c, 2}, {c, 3} が生成されます。
リスト内包表記を入れ子にするよりも、最初の書き方のほうが読みやすいですね。また、それぞれの生成器のあとに条件式を設定することもできます。簡単な例を示します。
> [{X, Y} || X <- lists:seq(1, 10), X rem 2 =:= 0, Y <- lists:seq(11, 20), Y rem 2 =/= 0].
[{2,11},
{2,13},
{2,15},
{2,17},
{2,19},
{4,11},
{4,13},
{4,15},
{4,17},
{4,19},
{6,11},
{6,13},
{6,15},
{6,17},
{6,19},
{8,11},
{8,13},
{8,15},
{8,17},
{8,19},
{10,11},
{10,13},
{10,15},
{10,17},
{10,19}]
●要素の削除
簡単な例として、リストからデータ X と等しい要素をすべて削除する関数 delete/2 を作ってみましょう。なお、Erlang の lists モジュールにある関数 delete/2 はすべての要素を削除するのではなく、最初に見つけた要素だけを削除します。動作が異なるので注意してください。
再帰定義でプログラムすると次のようになります。
リスト : 要素の削除 delete(_, []) -> []; delete(X, [X | Xs]) -> delete(X, Xs); delete(X, [Y | Ys]) -> [Y | delete(X, Ys)].
最初の節で、引数のリストが空であれば空リストを返します。次の節で、リストの先頭要素が X と等しい場合は delete を再帰呼び出しします。このとき、X は返り値のリストに追加しません。最後の規則で、X と先頭要素 Y が異なる場合、delete を再帰呼び出しして、その返り値のリストに Y を追加します。これで、X と等しい要素をすべて削除することができます。
実行例を示します。
> lst:delete(1, [1, 2, 3, 1, 2, 3, 1, 2, 3]). [2,3,2,3,2,3] > lst:delete(3, [1, 2, 3, 1, 2, 3, 1, 2, 3]). [1,2,1,2,1,2]
内包表記でプログラムすると、次のようになります。
リスト : 要素の削除 (内包表記) delete1(X, Xs) -> [Y || Y <- Xs, X =/= Y].
リスト Xs から要素を Y に取り出し、X と Y が異なればリストに追加します。とても簡単ですね。
それでは実行してみましょう。
> lst:delete1(1, [1, 2, 3, 1, 2, 3, 1, 2, 3]). [2,3,2,3,2,3] > lst:delete1(3, [1, 2, 3, 1, 2, 3, 1, 2, 3]). [1,2,1,2,1,2]
このように、Erlang の内包表記はとても強力な機能です。上手に使えば、プログラムがとても簡単になります。
●case 式
Erlang のパターンマッチングは、演算子 = や関数呼び出しだけではなく、case 式で行うこともできます。case 式の構文を示します。
case 式 of pattern_1 when 条件式 -> 式, ..., 式; pattern_2 when 条件式 -> 式, ..., 式; ... pattern_n when 条件式 -> 式, ..., 式 end
構文は if とよく似ていますが、case は式の評価結果と pattern をパターンマッチングするところが異なります。そして、マッチングに成功した節を選択して、右辺の式を評価します。たとえば、式の結果と pattern_1 がマッチングした場合、右辺を評価してその結果が case 式の返り値になります。マッチングしない場合は次のパターンを調べます。マッチングするパターンが見つからない場合はエラーになります。なお、一度マッチングに成功して節が選択された場合、それ以降の節は選択されません。
簡単な例を示しましょう。case 式を使って階乗を求める関数 fact を定義すると次のようになります。
リスト : 階乗
fact1(N) ->
case N of
0 -> 1;
M when M > 0 -> M * fact1(M - 1)
end.
最初の定義はパターンが 0 なので、引数が 0 の場合にマッチングします。パターンが変数の場合はどんな値とでもマッチングします。そして、変数はその値に束縛されます。したがって、N が 0 以外の場合は 2 番目のパターンと一致し、変数 M の値は N になります。ここで再帰呼び出しが行われます。
変数 M は N と同じ値なので、パターンに無名変数を使って次のように定義してもかまいません。
リスト : 階乗 (2)
fact2(N) ->
case N of
0 -> 1;
_ when N > 0 -> N * fact1(N - 1)
end.
それでは実行してみましょう。
> fact:fact1(10).
3628800
> fact:fact1(-10).
** exception error: no case clause matching -10
in function fact:fact1/1
> fact:fact2(10).
3628800
> fact:fact2(-10).
** exception error: no case clause matching -10
in function fact:fact2/1
パターンマッチングを使うときは、節を定義する順番に気をつけてください。fact の場合、最初にパターン _ を定義すると、引数が 0 の場合でもマッチングするので、パターン 0 の節が実行されることはありません。特定のパターンから定義するように注意してください。
●リストのパターンマッチング
ところで、リストを表すパターンは [X | Xs] だけではありません。よく使われるパターンを次に示します。
(1) [X] 要素が 1 つのリストとマッチング (2) [X, Y] 要素が 2 つのリストとマッチング (3) [X | Xs] 要素が 1 つ以上あるリストとマッチング (4) [X, Y | Ys] 要素が 2 つ以上あるリストとマッチング
また、もっと複雑なリストもパターンで表すことができます。
(1) [{X, Y} | Xs] 要素がタプルのリストとマッチング
ex) [{1, 2}, {3, 4}, {5, 6}] => X = 1, Y = 2, Xs = [{3, 4}, {5, 6}]
(2) [[X | Xs] | Ys] 要素がリストのリストとマッチング
ex) [[1, 2, 3], [4, 5], [6]] => X = 1, Xs = [2, 3], Ys = [[4, 5], [6]]
たとえば、複数のリストを格納しているリストから、各々のリストの先頭要素を取り出す処理は次のようにプログラムすることができます。
> [X || [X | _] <- [[1, 2], [3, 4, 5], [6, 7, 8, 9]]]. [1,3,6]
逆に、先頭要素を取り除く処理は次のようになります。
> [Xs || [_ | Xs] <- [[1, 2], [3, 4, 5], [6, 7, 8, 9]]]. [[2],[4,5],[7,8,9]]
もうひとつ、簡単な例を示しましょう。リストの中で要素 X の右隣に要素 Y があるかチェックする関数 adjacent(X, Y, Xs) を作ります。次のリストを見てください。
リスト : X と Y は隣り合っているか adjacent(X, Y, [X, Y | _]) -> true; adjacent(_, _, [_, _]) -> false; adjacent(X, Y, [_ | Xs]) -> adjacent(X, Y, Xs).
関数 adjacent の定義は簡単です。リストが [X, Y | _] とマッチングすれば、X と Y が隣り合っていることがわかります。そうではなく、リストの要素が 2 つしかない場合は、2 番目の規則とマッチングします。X と Y は隣り合っていないので false を返します。リストの要素が 2 つより多い場合は、最後の規則で先頭の要素を取り除き、adjacent を再帰呼び出しして残りのリスト Xs から探します。
簡単な実行例を示します。
> lst:adjacent(c, d, [a,b,c,d,e]). true > lst:adjacent(c, e, [a,b,c,d,e]). false > lst:adjacent(a, b, [a,b,c,d,e]). true > lst:adjacent(d, e, [a,b,c,d,e]). true
●zip と unzip
二つのリスト Xs, Ys の要素を xi, yi とすると、Xs と Ys からリスト [ ..., {xi, yi}, ... ] を生成する関数を zip/2 といい、その逆操作を行う関数を uzip/1 といいます。Erlang では、どちらの関数もモジュール lists に用意されています。なお、lists の zip はリストの長さが異なるとエラーになりますが、短いリストに合わせることもできます。実際、他のプログラミング言語では、そのほうが多いように思います。ここではその仕様でプログラムを作ってみましょう。
リスト : zip/2 と unzip/1
zip([], _) -> [];
zip(_, []) -> [];
zip([X | Xs], [Y | Ys]) -> [{X, Y} | zip(Xs, Ys)].
unzip([]) -> {[], []};
unzip([{X, Y} | Zs]) -> {Xs, Ys} = unzip(Zs), {[X | Xs], [Y | Ys]}.
zip はリストの要素 X, Y を取り出してタプルにまとめ、それをリスト追加していくだけです。unzip はパターンマッチングで先頭のタプルの要素を変数 X, Y に取り出します。残りのリスト Zs を unzip で分解して、その結果を変数 Xs, Ys に受け取ります。あとは、X を Xs に、Y を Ys に追加して、それをタプルにまとめて返すだけです。
それでは実際に試してみましょう。
> lst:zip([1, 2, 3, 4, 5], [6, 7, 8, 9, 10]).
[{1,6},{2,7},{3,8},{4,9},{5,10}]
> lst:zip([1, 2, 3, 4, 5], [6, 7, 8]).
[{1,6},{2,7},{3,8}]
> lst:zip([1, 2, 3], [6, 7, 8, 9, 10]).
[{1,6},{2,7},{3,8}]
> A = lst:zip([1, 2, 3, 4, 5], [6, 7, 8, 9, 10]).
[{1,6},{2,7},{3,8},{4,9},{5,10}]
> lst:unzip(A).
{[1,2,3,4,5],[6,7,8,9,10]}
> lst:unzip([]).
{[],[]}
●パスカルの三角形
再帰定義 では、組み合わせの数を求める関数 combination_number/2 を使って「パスカルの三角形」を作りました。ここではリストを使ってパスカルの三角形を作ってみましょう。パスカルの三角形は、両側がすべて 1 で内側の数はその左上と右上の和になっています。したがって、n 段の三角形を作る場合、一段前の値を記憶しておいて隣同士の要素を足し算すればいいわけです。一段前の値をリストに格納すると、プログラムは次のようになります。
リスト : パスカルの三角形
pascal_sub([_]) -> [1];
pascal_sub([X, Y | Zs]) -> [X + Y | pascal_sub([Y | Zs])].
% 別解
pascal_sub1(Xs) -> [A + B || {A, B} <- lists:zip(Xs, reverse(Xs))].
pascal(0, _) -> ok;
pascal(N, Xs) when N > 0 ->
io:format('~p~n', [Xs]), pascal(N - 1, pascal_sub([0 | Xs])).
pascal(N) -> pascal(N, [1]).
関数 pascal_sub/1 は、リストの隣同士の要素を足した値をリストに格納して返します。この処理は再帰呼び出しを使えば簡単です。リストの先頭要素 X と次の要素 Y を足し算し、その値を再帰呼び出しの返り値 (リスト) の先頭に追加すればいいわけです。リストの要素がひとつになったらリスト [1] を返します。これが再帰呼び出しの停止条件になります。
pascal/2 は引数 Xs にパスカルの三角形の値 (リスト) を保持します。最初に format で Xs を表示して、pascal を再帰呼び出しします。このとき、引数 N を -1 して、pascal_sub を呼び出して Xs を次の段に更新します。ここで、Xs の先頭に 0 を追加することを忘れないでください。これで、リストの先頭と最後尾を 1 にすることができます。
pascal_sub1 は pascal_sub の別解です。Xs とそれを反転したリストを zip でまとめると、タプルには隣り合った要素が格納されます。たとえば [1, 2, 1] の場合、Xs には [0, 1, 2, 1] が渡されます。それと [1, 2, 1, 0] を足し算することになるので、結果は [1, 3, 3, 1] になります。
実行結果は次のようになります。
> lst:pascal(16). [1] [1,1] [1,2,1] [1,3,3,1] [1,4,6,4,1] [1,5,10,10,5,1] [1,6,15,20,15,6,1] [1,7,21,35,35,21,7,1] [1,8,28,56,70,56,28,8,1] [1,9,36,84,126,126,84,36,9,1] [1,10,45,120,210,252,210,120,45,10,1] [1,11,55,165,330,462,462,330,165,55,11,1] [1,12,66,220,495,792,924,792,495,220,66,12,1] [1,13,78,286,715,1287,1716,1716,1287,715,286,78,13,1] [1,14,91,364,1001,2002,3003,3432,3003,2002,1001,364,91,14,1] [1,15,105,455,1365,3003,5005,6435,6435,5005,3003,1365,455,105,15,1] ok
改訂 2018 年 12 月 16 日