Scheme手習い 第５章 *すごい* 星がいっぱいだ（その１）

この章では要素が一列に並んだリストではなくリストがリストを含む木構造の処理を習います。リストでは再帰の際にcdrを対象としていましたが、ここからはcarも再帰の対象となります。

ノート：

rember*

定義を言葉に書き下すと：

1. アトムaとリストlに対して適用し、「lと同じ要素を同じ順序で含むがaは含まないリスト」を意味する。
2. そのリストは：
3. lが空であれば、空リスト
4. lの先頭要素がアトムの場合、
   1. lの先頭要素がaと等しい場合、lの残りに対してrember*を適用したリスト
   2. lの先頭要素がaと等しくない場合、lの先頭要素とlの残りに対してrember*を適用したリストを連結したリスト
5. lの先頭要素がリストの場合、lの先頭要素に対してrember*を適用したリストと、lの残りに対してrember*を適用したリストを連結したリスト

> (let ((a 'cup)
        (l '((cofee) cup ((tea) cup)
                     (and (hick)) cup)))
    (rember* a l))
((cofee) ((tea)) (and (hick)))
> (let ((a 'sauce)
        (l '(((tomato sauce))
             ((bean) sauce)
             (and ((flying)) sauce))))
    (rember* a l))
(((tomato)) ((bean)) (and ((flying))))
> 

(car l)がアトムの時は簡単だが、(car l)がリストの場合リストのcarも再帰させる所が新しい。

latかどうかのチェックも確認する。

> (lat? '((coffee) cup ((tea) cup) (and (hick)) cup))
#f
> (let ((l '(((tomato sauce)) ((bean) sauce) (and ((flying)) sauce))))
    (atom? (car l)))
#f
> 

insertR*

正確にはoldの右にnewを挿入した新しいリストを作る。

> (let ((new 'roast)
        (old 'chuck)
        (l '((how much (wood)) could ((a (wood) chuck)) (((chuck))) (if (a) ((wood chuck))) could chuck wood)))
    (insertR* new old l))
((how much (wood)) could ((a (wood) chuck roast)) (((chuck roast))) (if (a) ((wood chuck roast))) could chuck roast wood)
> 

occur

1. アトムaとリストlに適用し、「lに含まれるaの数」を意味する。
2. その数は：
3. lが空リストであれば、0
4. lの先頭要素がアトムの場合
   1. lの先頭要素がaと同じ場合は、lの残りのリストに含まれるaの数に１を加えた数
   2. lの先頭要素がaと同じでない場合は、lの残りのリストに含まれるaの数
5. lの先頭要素がリストの場合、lの先頭要素（リスト）に含まれるaの数とlの残りのリストに含まれるaの数を足した数

> (let ((a 'banana)
        (l '((banana) (split ((((banana ice))) (cream (banana)) sherbt)) (banana) (bread) (banana brandy))))
    (occur* a l))
5
> 

subst*

insertR*と殆ど同じ。

> (let ((new 'orange)
        (old 'banana)
        (l '((banana) (split ((((banana ice))) (cream (banana)) sherbet)) (banana) (bread) (banana brandy))))
    (subst* new old l))   
((orange) (split ((((orange ice))) (cream (orange)) sherbet)) (orange) (bread) (orange brandy))
> 

insertL*

insertR*と殆ど同じ。

> (let ((new 'pecker)
        (old 'chuck)
        (l '((how much (wood)) could ((a (wood) chuck)) (((chuck))) (if (a) ((wood chuck))) could chuck wood)))
    (insertL* new old l))
((how much (wood)) could ((a (wood) pecker chuck)) (((pecker chuck))) (if (a) ((wood pecker chuck))) could pecker chuck wood)
> 

member*

形はほぼこれまでの再帰と同じだが、#tか#fを返してconsによってリストを組み立てない事、従ってcarでの再帰の結果とcdrの再帰の結果をまとめる際にはorを使う所が変わる。

1. 「アトムaがリストlに含まれる」と言う述語
2. lが空リストの場合、（aが含まれる筈は無いので）偽
3. lの先頭要素がアトムの場合
   1. lの先頭要素がaと等しければ真
   2. そうでなければ、lの残りリストにaが含まれているかに依存
4. lの先頭要素がリストの場合、
   1. lの先頭要素（リスト）にaが含まれていれば真
   2. そうでなければ、lの残りリストにaが含まれているかに依存

本の定義ではlが空リストのときnilを返しているが、nilは偽ではないので#fを返すのが正しい。よって定義は以下の通り。

(define member*
  (lambda (a l)
    (cond ((null? l) #f)
          ((atom? (car l)) (cond ((eq? a (car l)) #t)
                                 (else (member* a (cdr l)))))
          (else (or (member* a (car l)) (member* a (cdr l)))))))

例を評価する。

> (let ((a 'chips)
        (l '((potato) (chips ((with) fish) (chips)))))
    (member* a l))
#t
> 

leftmost

『空リストを含まないS式』が対象との事だが、空リストを含む場合には実際にはエラーとなる。

1. リストlに適用し、「リスト中の最も左に位置するアトム」を意味する。
2. lの先頭要素がアトムであれば、lの先頭要素。
3. lの先頭要素がアトムでなければ、lの先頭要素中の最左アトム

> (let ((l '((potato) (chips ((with) fish (chips))))))
    (leftmost l))
potato
> (let ((l '(((hot) (tuna (and))) cheese)))
    (leftmost l))
hot
> (let ((l '(((() for)) 17 (seventeen))))
    (leftmost l))
. . mcar: expects argument of type <mutable-pair>; given ()
> (leftmost (quote ()))
. . mcar: expects argument of type <mutable-pair>; given ()
>