Scheme手習い (2) 初めての再帰

第2章「一度、もう一度、さらにもう一度、またもう一度、……」ではラットの再帰を学びます
ラット(lat)はこの本だけの用語で、アトムだけが並んだリストのことです
List of ATomsのことだと思われます

引数がラットであるかどうかを判定する関数lat?です

(define lat?
  (lambda (l)
    (cond
      ((null? l) #t)
      ((atom? (car l)) (lat? (cdr l)))
      (else #f))))

この関数に引数として(bacon and eggs)を与えてやったときの動きを1行ずつ
じっくりと追いかけていきます
こんな感じです 一部略してます

(lat? l)の最初の質問は何ですか。
(null? l)です。(略)
次のcond行 ( (null? l) #t) の意味は何ですか。
(null? l)は引数lが食うリストかどうか質問します。(略)
次の質問は何ですか。
(atom? (car l))です。
行( (atom? (car l)) (lat? (cdr l))) の意味は何ですか。(略)
(atom? (car l))は、リストｌの最初のS式がアトムかどうかをたずねています。(略)
(lat? (cdr l)) の意味は何ですか。
...

この調子で (lat? '(bacon and eggs)) の値を得るまでに4ページ半を使い
21回の質問を繰り返してます
ある意味ここがこの本のクライマックスのひとつと言えるかもしれません

再帰のことがなんとなくわかったようなわからないような、という人がいたら
このレベルで1行1行ていねいに追いかけるというのをやってみると理解度が
上がるんじゃないかと思います

こういうところは得手不得手みたいなのが激しいっぽいので
引っかかる人がどういうところに引っかかるのか想像しづらいところではありますが
(lat? (cdr l))が何をやっているかが腑に落ちるかどうか、かなあ
逆に、本当にわかっている人からすると自分も何かの理解が抜けている気もします

頭の中ではこんな感じですかね

(lat? '(bacon and eggs))を評価する
(null? l)ではなくて(atom? (car l)だから
  (lat? '(and eggs))を評価する
  (null? l)ではなくて(atom? (car l)だから
    (lat? '(eggs))を評価する
    (null? l)ではなくて(atom? (car l)だから
      (lat? '())を評価する
      (null? l)だから値は#t

普通の言語の感覚だと、呼び出しを逆にたどって

      (略)
      (null? l)だから値は#t
      だから(lat? '())の値は#t
    だから(lat? '(eggs))の値は#t    
  だから(lat? '(and eggs))の値は#t
だから(lat? '(bacon and eggs))の値は#t

な風になりそうなものですが、ここは書かれてません
これは末尾再帰だからわざとそうしてるんでしょうか

慣れてきたらこんな感じに

(lat? '(bacon and eggs))
(lat? '(and eggs))
(lat? '(eggs))
(lat? '())
#t

もう一度、こんどは値が#fになる例を同じように追いかけます

(lat? '(bacon (and eggs))')
(lat? '((and eggs))')
#f

ここで

)))は何ですか。
（略）カッコの数を合わせるためのものです。

ちょっと笑いました

次にラットの中にアトムが含まれているかどうかを返すmember?を定義します

(define member?
  (lambda (a lat)
    (cond
      ((null? lat) #f)
      (else (or (eq? (car lat) a)
                (member? a (cdr lat)))))))

本では#fのところがnilとなってますが誤植です
この本、最初はSchemeではなくてCommon Lispで書かれてたそうなので
その時のものが修正されずに残ってしまったんでしょうか
けっこう誤植が多い気がします

(or A B)は↓と同じです
（本では例示したうえでかみくだいて書いてくれてます）

(cond (A #t)
      (else (cond (B #t)
            (else #f))))

member?も例のしつこさで追いかけてくれます

(member? 'meat '(mashed potatoes and meat gravy))
(member? 'meat '(potatoes and meat gravy))
(member? 'meat '(and meat gravy))
(member? 'meat '(meat gravy))
#t

かと思いきや、#tが求まってからも追いかけ続けているようです
ということはこういう解釈？

(member? 'meat '(mashed potatoes and meat gravy))
(or #f (member? 'meat '(potatoes and meat gravy)))
(or #f (or #f (member? 'meat '(and meat gravy))))
(or #f (or #f (or #f (member? 'meat '(meat gravy)))))
(or #f (or #f (or #f #t)))
(or #f (or #f #t))
(or #f #t)
#t

この形でも末尾再帰だと思ったんだけどな・・・
なにか理解が違ってるかな

あと#fになる例

(member? 'liver (bagles and lox))
(or #f (member? 'liver (and lox)))
(or #f (or #f (member? 'liver (lox))))
(or #f (or #f (or #f (member? 'liver ()))))
(or #f (or #f (or #f #f)))
(or #f (or #f #f))
(or #f #f)
#f

まあこれくらい繰り返して1行ずつ追えば初めての人でも再帰の感じがつかめるんじゃないでしょうか
私は初めてじゃなかったので本当のところはわかりませんが

戒律というのが出てきます

第1の戒律
（仮）いかなる関数を表現するときも最初の質問はすべてnull?にすべし。

10個の戒律をマスターすればあなたも再帰の達人に
というわけ

ちなみにlat?は普通こんな風に書くと思います
こちらのほうが1行とインデント1段とを節約できて読みやすくなりますし

(define (lat? l)
  (cond
    ((null? l) #t)
      ((atom? (car l)) (lat? (cdr l)))
      (else #f)))

ただこの書き方は関数を作る部分(lambda)と、モノに名前を付ける部分(define)が
ごっちゃになってますのでちょっとピュアな感じに欠けます
計算機科学の世界だとこっちが普通なんでしょうか
できるだけシンプルにしたいというだけかもしれません
そのあたりけっこう原理主義かもしれませんこの本