読者です 読者をやめる 読者になる 読者になる

【CommonLisp】リストを食べる関数の代表例。リストの長さを計算する関数

今日も「Land of Lisp」から。

リストを食べる関数というのは、
リストを再帰的に処理していく中で、nilになるまで処理を続けていくということ。
リストを頭から食べていって空リストを検出することはLispの関数でよく使われるみたい。

関数型の言語は触ったことがほとんどないので、そもそも再帰処理に慣れてない。
たま〜に関数内で自身を呼び出すことはあるけど、再帰処理として使っている感はないし。


Land of Lispのなかで、Lispの古典的なスタイルとして以下の(ような)関数が紹介されていた。
リストの長さを返す関数だ。

(defun my-length(list)
    (if list
        (1+ (my-length(cdr list)))
        0))

(my-length '(cat dog fox))  ;=> 3

my-length関数の引数にデータ型リスト(cat dog fox)を渡すと、ちゃんと3つと返ってくる、
他の言語でもド定番の関数だ。

ただ、内部処理を読むと再帰処理を行っており、私の頭はパニックになった。
ちんぷんかんぷんになった(笑)

ifの部分。

(if list
    (1+ (my-length(cdr list)) 
    0))

引数のリストが空でない場合、
(1+ (my-length(cdr list))
が実行される。
リストが空の場合は、
0が返される。

ここまではいいだろう。Lisp初心者の私でもちゃんとわかる。

(1+ 引数)関数

(1+ (my-length(cdr list)) 

これは、引数の値に1を加算するという関数だ。
なので、(my-length(cdr list) + 1 ということになる。

(cdr list)

これは、listの2つ目以降の値を取り出す。(cat dog fox)だとすれば、
(cdr '(cat dog fox))は(dog fox)になる。

ということはだ。
(1+ (my-length(cdr list)) は、
(my-length '(dog fox)) + 1 という意味になる。

じゃあ、my-length関数の返り値に1を足せばいいんだ!と思うわけだが、
my-length関数は自分自身だ。
呼び出し先でまたmy-length関数を呼び出しているのである。
そしてその先でも呼び出しを。。あれ?じゃあいつ値は返ってくるんだ!?!?

ここでパニックになった(笑)

いつまでたっても1を足す対象の値が返ってくる気がしないので、何をしているのかわからなくなってしまった。
f:id:AddyPlusy:20160925230024p:plain
ここで、冒頭を思い出した。
リストを食べる関数なのだ。リストが空になるまで食べ続け、空リストを検出するまで再起する関数なのだ。

冷静になって図に書いてみるとよくわかる。
cdr関数によってリストの先頭から落とされている間で、リストの個数分再帰したあと空リストになる。
f:id:AddyPlusy:20160925230020p:plain
さて、Lispは空リストは偽となるためmy-length関数内のif文は0を返す。
ここで初めて再帰処理が終わった。ついに0という値が返されたのだ。
0が返されたということは、

(1+ my-length(cdr list))

の部分は、

(1+ 0)

となり1という値になる。
このようにして再帰したぶんだけまた関数呼び出し部にもどっていく。
f:id:AddyPlusy:20160925230551p:plain
これで無事3が帰ってきた。


こんな簡単な関数にこれだけ理解に時間がかかってしまった。
自分がいかに関数脳でないかがわかる(笑)

でも、今回のLand of Lispの例題で再帰のすばらしさを体感した。

def my_length(list)
    count = 0
    list.each do
        count += 1
    end
    return count
end

list = ["cat", "dog", "fox"]
puts my_length(list)

Rubyで今まで通りに書いてみるとmy_length関数はこう書ける。というか書いてた。
Lispでの書き方との決定的な違いはカウンタ変数の有無だ。
それどころか、Lisp側には変数が1つもない。
1つの引数に対して1つの値を返すという関数だけを使って上の関数と同じことをしている。

しゅごい。