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

list?の実装について考える

scheme

本日の取り組み。

list?とは(例題の)

プログラミングGaucheの46P記載より
list?手続き

(define (list? obj)
  (or (null? obj)
    (and (pair? obj) (list? (cdr obj)))))

正式なリストの定義(list?の実装内容)

  • 空リストは正式なリストである。
  • オブジェクトが対であり、そのcdrが正式なリストであれば、そのオブジェクトも正式なリストである。

この手続き「list?」は引数のオブジェクトが正式なリストかどうか確かめるというものです。
5つの手続き*1の利用例なので、循環リストには対応していないという条件つきです。
実際にGaucheで実装されているlist?手続きとは異なります。

この例を分解しながら考えてみたいと思います。
理解したい!!

考察

まずは

(define (list? obj) 処理 )

手続きの定義を行っていると。

次の注目は最初の手続き「or」です。

(define (list? obj)
  (or (null? obj)
    (次のS式)))

[null?]はobjが空リストだったら#tを返すだったので、空リストは正式なリストということで、#tを返す。
こんな感じでしょうか?


次は手続き「and」の箇所です。

(手続き定義部分
  (or (1つめの精査のS式)
    (and (pair? obj) (list? (cdr obj))))

andは両方とも全て真の場合のみ#tを返し、一つでも偽があれば、#fを返すということらしいです。
最初のS式では(pair? obj)の手続きがあるのですが、既にorの手続きで空リストの精査は行っているので、あとは空ではないリストである事を精査すれば良いということですよね??


これで、正式なリストが証明されるかというとまだ足りなくて、リストは入れ子になっているという可能性があるということ。奥深くまで精査する為に、そこで再帰的にcdr部のポインタをlist?へ引き渡すという形なんですね。引き渡されたobjは最終的にcdr部が「空リスト」であるか、そうでないかを判断するまで継続する事になる。

ということでよいのかな?

ここでのポイントは、and条件のpair?が継続条件であることと偽を返す条件を兼ねている事。
この手続きは最終的には空リストであることが真の条件になるのだから・・・

最小限の正式なリストのcdr手続きの結果が空リストという所が答えに近いのでしょうか。

(cdr '(1))
;result ()

考察結果

これが、例題のlist?手続きに対する実装の解析の回答です。

  • 「二つのポインタが示す結果を辿っていけば最終的に正式なリストかどうかわかるよ」
  • 「car部・cdr部どちらかひとつだけでは駄目。ふたつあるからこんな実装方法ができるのだよ」

なんか面白いぞ、これは。まだリストの基本をしているだけのに・・・
あぁぁ〜〜赤ペン先生して欲しい。

唯一の身近にいた関数型言語をやっているEmacs使いの人が客先に行ってしまったので、今度会う時にこの考えのレビューのお願いをしてみようっと。

間違っている点とか理解できていない点があれば、早めにただしたいな〜。

*1:car,cdr,cona,null?,pair?