Copyright © 2019 TAKEHANA TADASHI
著作日時： 2019.12.11.水. 12:03:00 著作者、竹花 忠
Haskell言語の予備知識：
Haskell言語でのリストは、同型のデーターをカンマで区切って並べたものである。
たとえば、[1,2,3,4]とか["ab","cdef","g"]とか。
また、Haskell言語では、変数に再代入が許されていない。
たとえば、最初に、a = 1と代入するのはいいが、そのあと、a = 3 とかa = 0とか、一旦代入済みの変数aに再度、値を代入することは許されていない。
Haskell言語では、整数の加減乗除は、それぞれ、+, -, *, divで表す。
たとえば、2 * 5の返り値は、10である。13 div 3の返り値は、4である。
Haskell言語では、表面上・見かけ上、は異なっているが、同一のものを表している表現があって、それを構文糖衣、と言う。
たとえば、文字列"abcde"は、文字型のリスト['a','b','c','d','e']の糖衣構文である。
つまり、"abcde"は、['a','b','c','d','e']と同一である。
['a','b','c','d','e']の別の表現形式が"abcde"で、それは、['a','b','c','d','e']と完全に同一ということ、表面上は・見かけ上は、異なっているけれども。
ところで、関数の定義の記述に、その関数の呼び出しが含まれている時、再帰呼び出し関数と呼ばれる。
なお、関数呼び出しの記述はの、その定義の記述に置き換えられなければならない。
定義の記述の中に、関数呼び出しの記述が含まれていたなら、その関数呼び出しの記述もその定義の記述に置き換えられなければならない。
以上は、関数呼び出しを読解する時の規準である。
リスト構築子 ：（＝コンス）は、その右にリストが位置し、：の左には、：の右に位置しているリストの左に追加する1要素を位置させて使用する。
つまり、10 : [1,2,3]ならその返り値は、[10,1,2,3]。
5 : [1]ならその返り値は、[5,1]。
3 : []ならその返り値は、[3]。
ちなみに、[]は、中身が空のリスト、空リスト、である。
空リストもリストである。
ただし、空リストは、リストとそのリストの先頭に追加する1要素とに分解して表現することのできないリストである。
[1,2,3]であれば、(1:[2,3])というように分解して表現できる。また、[2]でも、(2:[])と分解して表現できる。
しかし、[]・空リスト、は、[]・空リスト、の先頭に無の1要素を追加して得られるリストであるけれども、無の1要素を表す表記が存在しない。
なので、[]・空リスト、は、(x:xs)という形式で表現することのできないリストである。
なお、ここでxは、先頭の1要素を表し、xsは後続のリストを表す。
空リスト・[]は、そのまま、[]として表現するしかない。
ちなみに、[1,2,3]は、1:2:3:[]と同一である。
ところで、:は、右結合の演算子である。
:の演算子が、上記のように複数列挙されて使用されていた場合、その演算の実行は、右結合なので右側の位置の:から順に実行すする。
であるから上記の場合まず、空リストの先頭に3が取り込まれて、1:2:[3]となる。
次に、リスト[3]の先頭に2が取り込まれて、1:[2,3]となる。
さらに、リスト[2,3]の先頭に1が取り込まれて[1,2,3]となる。
つまり、[1,2,3]は1:2:3:[]の構文糖衣である。
関数呼び出しの記述が、具体的に、あるいは、類型的に、一致するのがどれなのかがラインナップしている、関数の定義セットの記述部分には。
そして、そのラインナップのそれぞれごとに、それぞれに一致した時に、関数呼び出しの記述をそれに置き換えてしまうべき、定義の記述が存在している。
たとえば、
kansuu [] = 0
kansuu (x:xs) = (x - 1) + kansuu xs
というように。この場合、上記2行が、関数の定義セットの記述部分の全容である。
ちなみに、この定義の意味は、下記の通りである。
具体的なkansuu []という関数呼び出しと一致した時には、その定義0に置き換える。
あるいは、類型的なkansuu (x:xs)という関数呼び出しと一致した時には、その定義(x - 1) + kansuu xsに置き換える。
さて、関数の定義セットの記述部分に、類型的な関数呼び出しをラインナップさせる時には、上記の例のように、パラメーターの位置の表現に、(x:xs)を用いる時がある。
その場合(x:xs)は、当該位置のパラメーターが、リストxsとそのリストの先頭に1要素xが追加されてできている形式のリストであることを表している。
つまり、当該位置のパラメーターがリストであり、そのリストが、先頭要素xとそれに後続するリストxsとからできているリストであることを表している。
つまり、(x:xs)は、当該位置のパラメーターが、空リスト以外のリストであることを表している。
つまり、kansuu (x:xs)は、[]以外のリストが設定されて関数が呼び出されている時のすべてに一致する、関数呼び出しの形式を表している。
であるから、
kansuu [] = 0
kansuu (x:xs) = (x - 1) + kansuu xs
という定義が行われていた時、kansuu [1,2]という関数呼び出しが行われたなら、パラメーター[1,2]は(1:[2])と解釈されて、kansuu (x:xs)に一致する。
その結果、その定義の記述(x - 1) + kansuu xsは、xに1、xsに[2]が当てはまるので、(1 - 1) + kansuu [2]となる。そして、kansuu [1,2]は、それに置き換えられる。
置き換えられた式(1 - 1) + kansuu [2]の一部に、関数呼び出しkansuu [2]が含まれている。
なのでこれもその定義の記述に置き換えなければならない。
パラメーター[2]は、(2:[])と解釈されるので、kansuu [2]は、kansuu (x:xs)に一致する。
その結果、その定義の記述(x - 1) + kansuu xsは、xに2、xsに[]が当てはまる。なので、(2 - 1) + kansuu []となる。
なので、先に得られた式(1 - 1) + kansuu [2]は、(1 - 1) + (2 - 1) + kansuu []に置き換えられる。
この式の中にも、関数呼び出しkansuu []が含まれているので、これもその定義の記述に置き換えなければならない。
関数のパラメーターが[]なのは、定義セットの1行目のkansuu []なので、今回はkansuu (x:xs)ではなく、kansuu []が一致する。
なのでそれが採用されて、その定義の記述に置き換えられる。
この定義の記述は0なので、kansuu []は0に置き換えられる。
なので先ほどまでに得られた式(1 - 1) + (2 - 1) + kansuu []は、(1 - 1) + (2 - 1) + 0に置き換えられる。
以上によって、kansuu [1,2]は、まず、
(1 - 1) + kansuu [2]に置き換えられ、次に、
(1 - 1) + (2 - 1) + kansuu []に置き換えられ、さらに、
(1 - 1) + (2 - 1) + 0に置き換えられる。
以上で関数呼び出しはなくなったので、あとは、運算をする。
(1 - 1) + (2 - 1) + 0 = 0 + 1 + 0 = 1。
なので結局、
kansuu [1,2]、は1に置き換えられる・の返り値は1である。
再帰呼び出し関数の定義セットは、典型的には、2種類の呼び出し形式と、そのそれぞれに対しての定義の記述、によって構成される。
2種類のうちの1つは、再帰呼び出しを終了させる時の呼び出し形式とそれに対しての定義の記述から構成される。
典型的には、saikiyobidashikansuu []、が、再帰呼び出しを終了させる時の呼び出し形式である。
つまり、関数saikiyobidashikansuuに渡されてきたパラメーターが、空リスト・[]、であった時、再帰呼び出しを終了させてしまう定義を行うようにする。
ここでは、定義に、0を設定してみる。
つまり、
saikiyobidashikansuu [] = 0
次に、再帰呼び出し関数の定義セットを構成する2種類のうちのもう1つは、再帰呼び出しを、繰り返す時・行う時、の呼び出し形式とそれに対しての定義の記述から構成される。
典型的には、saikiyobidashikansuu (x:xs)、が、再帰呼び出しを、繰り返す時・行う時、の呼び出し形式である。
saikiyobidashikansuu (x:xs)は、つまり、関数saikiyobidashikansuuに渡されてきたパラメーターが、リストでありその先頭要素がxであって、その後続のリストがxsである、ということを表している。
たとえば、saikiyobidashikansuu [1,2,3]であったなら、xは2、xsは[2,3]である。
だからたとえば、saikiyobidashikansuu [3]であったなら、xは3、xsは[]である。
さらにたとえば、saikiyobidashikansuu []であったなら、[]は、(x:xs)には一致しない。
saikiyobidashikansuu []であったなら、それは、先に記述した、saikiyobidashikansuu [] = 0、のsaikiyobudashikansuu []に一致する。
つまり、saikiyobidashikansuu (x:xs)の(x:xs)は、空リスト以外のリストに一致する。
典型的には、空リスト以外のリストが、関数saikiyobidashikansuuのパラメーターだった時、つまり、saikiyobidashikansuu (x:xs)だった時、リストの先頭要素xに対しての処理を行い、そして、リストの先頭の1要素を削除したリストxsをパラメーターとして同じ関数saikiyobidashikansuuを呼び出す。
ここではリストの先頭要素xを2倍する処理を実行することとし、その処理結果と再帰呼び出しsaikiyobidashikansuu xsとの和、つまり、(x * 2) + saikiyobidashikansuu xs、を定義に設定してみる。
つまり、
saikiyobidashikansuu (x:xs) = (x * 2) + saikiyobidashikansuu xs
以上のように2種類の定義によって、再帰呼び出し関数の定義セットが完成する。
再帰呼び出し関数saikiyobidashikansuuの定義セットは、
saikiyobidashikansuu [] = 0
saikiyobidashikansuu (x:xs) = (x * 2) + saikiyobidashikansuu xs
である。
この定義セットでは、saikiyobidashikansuu [1,2,3]の時、(1 * 2) + (2 * 2) + (3 * 2) + 0 で、12が返り値となる。
まず最初に、saikiyobidashikansuu [1,2,3]が与えられた。
これは定義のsaikiyobidashikansuu (x:xs)に一致する。したがってその定義の(x * 2) + saikiyobidashikansuu xsに置き換わる。
なので、まず第1段階で、
(1 * 2) + saikiyobidashikansuu [2,3]、になる。次に、saikiyobidashikansuu [2,3]が式の一部に与えられている。これも、saikiyobidashikansuu (x:xs)に一致する。したがってその定義の(x * 2) + saikiyobidashikansuu xsに置き換わる。
なので第2段階で、
(1 * 2) + (2 * 2) + saikiyobidashikansuu [3]、になる。次に、saikiyobidashikansuu [3]が式の一部に与えられている。これも、saikiyobidashikansuu (x:xs)に一致する。したがってその定義の(x * 2) + saikiyobidashikansuu xsに置き換わる。
なので第3段階で、
(1 * 2) + (2 * 2) + (3 * 2) + saikiyobidashikansuu []、になる。次に、saikiyobidashikansuu []が式の一部に与えられている。これは、saikiyobidashikansuu []に一致する。したがってその定義の0に置き換わる。
なので第4段階で、
(1 * 2) + (2 * 2) + (3 * 2) + 0、になる。もう式の中に関数呼び出しが含まれていないので、あとはただこの式を運算するだけである。
2 + 4 + 6 + 0なので、12、である。
したがって、saikiyobidashikansuu [1,2,3] の返り値は12である・は12に置き換わる。
再帰呼び出しの記述は、その呼び出し形式に一致したところの定義の記述に置き換える。通常、この置き換えがいくつか連鎖する。
ただしいずれ、再帰呼び出しを定義に含まない呼び出し形式に至る。するとそこで、再帰呼び出しによる置き換えの連鎖が終結する。
そこに至って、運算が実行できて、返り値が確定する。
リストの先頭の要素を処理した結果を、ある演算記号で、再帰呼び出しと連結したものが、再帰呼び出しを含む定義の実態である。
この定義の記述は、再帰呼び出しの連鎖によって結局、各段階でのリストの先頭要素を処理した結果同士を、再帰呼び出しを連結していた演算記号で連結した運算結果を返り値にすることになる。
つまり、
saikiyobidashikansuu [] = 0
として、
saikiyobidashikansuu (x:xs) = (x * 2) + saikiyobidashikansuu xs
は、
(x * 2) + (x' * 2) + (x'' * 2) + (x''' * 2) + ・・・ + 0
を返り値とする。
ここで、再帰呼び出しを連結していた演算記号の+が、各段階でのリストの先頭要素を処理した結果同士を連結している。
saikiyobidashikansuu に与えられたリストが[1,2,3,4,5,6]だった場合、上の式の、xは1で、x'は2で、x''は3で、x'''は4である。
つまり、1回目の呼び出しでのリストの先頭要素はリストの先頭要素であるが、2回目の呼び出しの際には、リストの先頭要素を削除したリストを設定して呼び出しているのでそもそものリストの2番目の要素になる。
3回目の呼び出しの際には、さらにリストの先頭要素を削除したリストを設定しての呼び出しなので、そもそものリストの3番目の要素が先頭要素となっている。
4回目の呼び出しの際には、さらにリストの先頭要素を削除したリストを設定しての呼び出しなので、そもそものリストの4番目の要素が先頭要素となっている。
以下同様に、順次、1個ずつ後方にズレた要素が先頭要素になっていく。
なので、1番目の要素から順にすべての要素を2倍した値、の足し合わせ値が、このsaikiyobidashikansuuの返り値となる。
各段階でのリストの先頭要素を処理した結果同士を、足し合わせた結果ではなく、各段階でのリストの先頭要素を処理した結果同士を、リストに構成した結果を、返り値としたいならどうすればいいか。
それは、
saikiyobidashikansuu [] = []
saikiyobidashikansuu (x:xs) = (x * 2) : saikiyobidashikansuu xs
とすればいい。
再帰呼び出しを連結する演算記号を、+にすると足し合わせ結果が得られる。
ここを、リスト構築子の:にすれば、各段階でのリストの先頭要素を処理した結果をリストに構成した結果が得られる。
なぜなら、再帰呼び出しによって、
(x * 2) : (x' * 2) : (x'' * 2) : (x''' * 2) : ・・・ : []
がもたらされるからである。
saikiyobidashikansuu [1,2,3,4,5,6]が与えられたなら、
(1 * 2) : (2 * 2) : (3 * 2) : (4 * 2) : (5 * 2) : (6 * 2) : []
がもたらされる。これはつまり、
2 : 4 : 6 : 8 : 10 : 12 : []
である。そしてこれはつまり、
2 : 4 : 6 : 8 : 10 : [12]
であり、
2 : 4 : 6 : 8 : [10,12]
であり、
2 : 4 : 6 : [8,10,12]
であり、
2 : 4 : [6,8,10,12]
であり、
2 : [4,6,8,10,12]
であり、
[2,4,6,8,10,12]
である。
したがって、
saikiyobidashikansuu [1,2,3,4,5,6]が与えられたなら、
[2,4,6,8,10,12] が返り値となる・に置き換えられる。