lispでの再帰まとめ

リストを結合する関数、入れ子リストを平準化する関数の作成を通じてlispでの再帰を復習する


リストを結合する実装 append

appendは、引数に2つのリストをとり、それらを結合したリストを返す再帰的関数とする。

実装例:

(defun append (a b)
   (if (null a)  b
       (cons (car a) (append (cdr a) b))))

説明:

  1. (if (null a) b

    a に nil が来た時点が、再帰の底とする。この時点で初めて b を返し、リストの再構築を始める
  2. (cons (car a) (append (cdr a) b))))

    b を持ったまま、a が分解できないところ"底"まで降りていく.
    最後は a に nil が入った状態でappendを呼び出すため、その際に b が返る.
    "底"で b を返すときappendが最初に"値"を返すタイミングとなり、それ以降、逆順にconsを当てはめていく。最初にappendを呼び戻した時点まで巻き戻り、consの返り値でリストが完成する

実行例:

> (define x '(1 2 3))
> (define y '(4 5 6))
> (append x y)
(1 2 3 4 5 6)
> x
(1 2 3)
> y
(4 5 6)


入れ子リストの平準化をする実装例 flat

flatは、入れ子になった複雑なリストを純リストにする再帰的関数とする。

実行例:

> (flat '(1 2 (3 (4 5)) 6 (((7)))))
(1 2 3 4 5 6 7)

実装例:

(defun flat (x)
   (cond  ((null x) nil)
          ((atom x) x)
          ((atom (car x) ) (cons (car x) (flat (cdr x))))
          (t (append (flat (car x)) (flat (cdr x))))))

説明:

  1. (defun flat (x) .... )

    関数を宣言する。「flat は引数として与えたリストを平たくする」というこの関数の定義を頭の中で覚えておく。
  2. (cond .....)

    再帰が上手く動くということは、0 と 1 と n+1 の3つのケースで動くということだと言える。
    この場合は、引数が nil のケースが 0 、引数がアトムのケースが 1 、それ以外が n+1 となる。以降引数のケースごとに分岐を考えていく。
  3. *1

    残りの場合は引数がリストであるケース。一般に Lisp のリスト処理は、最初の要素とそれ以降の要素にわけて考える。だから (car x) と (cdr x) わける。このうち、2つ目以降の要素である(cdr x) の処理については、flat 自身に任せることにする
  4. *2で帰ってくる純リストに対して、cons で先頭に追加してやれば良いだけである
  5. (t (append (flat (car x)) (flat (cdr x))))

    (car x)がリストである場合(アトム以外の場合)。
    (flat (cdr x))が返す純リストと、(flat (car x))が返す純リストとを連結すれば良い、ということになる。連結には先程作った append を使う

※アトムは、コンスセルを除くすべてのオブジェクト、シンボル、数字、配列、ベクタ、ハッシュ表など。シンボル`nil'はアトムでもありリストでもある.


再帰の実装のコツ

わかんなくなったら、さっさと M-x edebug-defun 等のデバッガでもって、軌跡を見てみること。

*1:null x) nil)
引数が nil の場合、単に戻り値は nil とする

  • ((atom x) x)
    引数がアトムの場合、引数のアトムをそのまま返す。 以上の2つが停止条件、ベースケースになる
  • (flat (cdr x

    *2:atom (car x) ) (cons (car x) (flat (cdr x))))
    (car x)について考える。(car x)は2通りの可能性がある。つまり、アトムである場合と、リストである場合だ。もし、アトムならば、単純に(flat (cdr x