@kyanny's blog

My thoughts, my life. Views/opinions are my own.

サルでもわかる L-99 の P09

L-99 の P09 を二週間以上かけてなんとか自力で解いたが、正答を見たら違うやり方で、何やってるかさっぱり理解できなかったので地道に全部展開してみてようやく意味がわかった。

同じように悩む人のために――未来の自分以外にいないかもしれないが――ここに解説する。

（ネタバレ防止のため空白をはさんでいます）

正答

正答を再掲する。pega と tira という補助関数を使っていることはわかるが、それぞれ何をしているのかよくわからないし、(cons (pega lista) (pack (tira lista))) のところで pack を再帰してるあたりで頭がこんがらがってついていけなくなる。これを紐解くには、補助関数もそれぞれ実行して結果を見るのがよい。

(defun pack (lista)
    (if (eql lista nil) 
        nil
        (cons (pega lista) (pack (tira lista)))
    )
)

(defun pega (lista)
    (cond ((eql lista nil) nil)
      ((eql (cdr lista) nil) lista)
          ((equal (car lista) (cadr lista))
              (cons (car lista) (pega (cdr lista))))
          (t (list (car lista)))
    )
)

(defun tira (lista)
    (cond ((eql lista nil) nil)
      ((eql (cdr lista) nil) nil)
          ((equal (car lista) (cadr lista))
              (tira (cdr lista)))
          (t (cdr lista))
    )
)

正答の実行結果の解説（概要）

実行結果はこのようになる。

(pack '(a a a a b c c a a d e e e e))
;;=> ((a a a a) (b) (c c) (a a) (d) (e e e e))

(pega '(a a a a b c c a a d e e e e))
;;=> (a a a a)

(tira '(a a a a b c c a a d e e e e))
;;=> (b c c a a d e e e e)

実行結果を見ると、pega は「リストの先頭から要素を調べて、連続する同じ要素を一つのリストに入れて返す。同じ要素の連続が途切れたら、残りの要素はすべて捨てる」という動作をする。tira は「リストjの先頭から要素を調べて、連続する同じ要素を捨てる。同じ要素の連続が途切れたら、残りのリストを丸ごと返す」という動作をする。tira は pega が捨てる「残りの要素をすべて含むリスト」を返す、ともいえる。

pega と tira は「同じ要素の連続が途切れる位置」で二分割したリストの前半と後半をそれぞれ返すようにできているので、抜け漏れや重複が起こらない。

pega の解説

さて、これだけでもまだピンとこないので、pega を一ステップずつ展開していく。pega の cond 節のうち、どの部分で展開（置換）されたか分かりやすくするために、cond 節の本体それぞれに Case X というラベルをつける（↓のコメント参照）。

(defun pega (lista)
  (cond ((eql lista nil) nil) ; Case A
        ((eql (cdr lista) nil) lista) ; Case B
        ((equal (car lista) (cadr lista))
         (cons (car lista) (pega (cdr lista)))) ; Case C
        (t (list (car lista))) ; Case D
        )
  )
1. pega 一回目の呼び出し
(pega '(a a a a b c c a a d e e e e))
2. pega 一回目の呼び出しを展開する

pega に与えたリストの第一引数 a と第二引数 a は同じなので Case C に該当する。よって pega の一回目の呼び出しを Case C の本体で置換する。

Case C は cons セルを作りつつ再帰する。cons の第一引数には元のリストの car を渡す。cons の第二引数は再帰部分である。ここで「再帰だからえーっと」と考え始めると頭がこんがらがるので、考えるのはやめて、単純に Case C の本体で置換する。すると↓のように pega の呼び出しが再び現れる。この pega に与えるリストは先頭の要素が一つ減っている。以後、同様に pega を置換していく。

(cons 'a
      (pega '(a a a b c c a a d e e e e)))
3. pega 二回目の呼び出しを展開する

↑で pega に与えたリストの第一引数 a と第二引数 a は同じなので Case C に該当する。よって pega の二回目の呼び出しを Case C の本体で置換する。

(cons 'a
      (cons 'a
            (pega '(a a b c c a a d e e e e))))
4. pega 三回目の呼び出しを展開する

↑で pega に与えたリストの第一引数 a と第二引数 a は同じなので Case C に該当する。よって pega の三回目の呼び出しを Case C の本体で置換する。

(cons 'a
      (cons 'a
            (cons 'a
                  (pega '(a b c c a a d e e e e)))))
5. pega 四回目の呼び出しを展開する

↑で pega に与えたリストの第一引数 a と第二引数 b は異なるので Case D に該当する。よって pega の四回目の呼び出しを Case D の本体で置換する。

Case D は再帰しないので、ここが pega の再帰の終端になる。

(cons 'a
      (cons 'a
            (cons 'a
                  (list 'a))))
6. (list 'a) を展開する
(cons 'a
      (cons 'a
            (cons 'a
                  '(a))))
7. S 式を評価する

↑の S 式は cons の羅列なので、結果は一つのリストになる。

(cons 'a
      (cons 'a
            (cons 'a
                  '(a))))
;;=> (a a a a)
リストの要素が 0 個または 1 個の場合

Case A と Case B が登場しなかったが、これらは pega に与えるリストが短い場合に対応する cond 節である。

Case A は pega に空リストを与えたときに対応する。

(pega nil)
;;=> nil

Case B は pega に要素が一つのリストを与えたときに対応する。

(pega '(a))
;;=> (a)
pega まとめ
  • pega は、与えたリストの第一引数と第二引数が同じ要素であれば、(cons (car lista) (pega (cdr lista))) という形で再帰する（Case C）。同じ要素が連続する限り、cons が数珠つなぎになる。cons の数珠つなぎなので戻り値はリストになる。
  • pega は、与えたリストの第一引数と第二引数が異なれば、与えたリストの第一引数だけを含むリストを返す（Case D）。リストの長さが 2 以上の場合は、ここが再帰の終端になる。↑の cons の数珠つなぎの末端に要素が一つのリストが繋がるので、戻り値は結局リストになる。
  • pega は、空リストを与えた場合は空リストを返す（Case A）。
  • pega は、要素が一つのリストを与えた場合はそのリストを返す（Case B）。

tira の解説

同様に tira も一ステップずつ展開していく。tira の cond 節のうち、どの部分で展開（置換）されたか分かりやすくするために、cond 節の本体それぞれに Case X というラベルをつける（↓のコメント参照）。

(defun tira (lista)
  (cond ((eql lista nil) nil) ; Case E
        ((eql (cdr lista) nil) nil) ; Case F
        ((equal (car lista) (cadr lista))
         (tira (cdr lista))) ; Case G
        (t (cdr lista)) ; Case H
        )
  )
1. tira 一回目の呼び出し
(tira '(a a a a b c c a a d e e e e))
2. tira 一回目の呼び出しを展開する

tira に与えたリストの第一引数 a と第二引数 a は同じなので Case G に該当する。よって tira の一回目の呼び出しを Case G の本体で置換する。

Case G は (tira (cdr lista)) なので、与えたリストの要素を一つ減らして（先頭の要素を捨てて）再帰している。

(tira '(a a a b c c a a d e e e e))
3. tira 二回目の呼び出しを展開する

↑で tira に与えたリストの第一引数 a と第二引数 a は同じなので Case G に該当する。よって tira の一回目の呼び出しを Case G の本体で置換する。

(tira '(a a b c c a a d e e e e))
4. tira 三回目の呼び出しを展開する

↑で tira に与えたリストの第一引数 a と第二引数 a は同じなので Case G に該当する。よって tira の一回目の呼び出しを Case G の本体で置換する。

(tira '(a b c c a a d e e e e))
5. tira 四回目の呼び出しを展開する

↑で tira に与えたリストの第一引数 a と第二引数 b は異なるので Case H に該当する。よって tira の四回目の呼び出しを Case H の本体で置換する。

Case H は再帰しないので、ここが tira の再帰の終端になる。

(cdr '(a b c c a a d e e e e))
6. S 式を評価する

↑の S 式は単なる cdr なので、結果はリストになる。

(cdr '(a b c c a a d e e e e))
;;=> (b c c a a d e e e e)
リストの要素が 0 個または 1 個の場合

Case E と Case F が登場しなかったが、これらは tira に与えるリストが短い場合に対応する cond 節である。

Case E は tira に空リストを与えたときに対応する。

(tira nil)
;;=> nil

Case F は tira に要素が一つのリストを与えたときに対応する。

(tira '(a))
;;=> nil
tira まとめ
  • tira は、与えたリストの第一引数と第二引数が同じ要素であれば、(tira (cdr lista)) という形で再帰する（Case G）。単純に、リストの要素を一つずつ減らしながら（先頭の要素を捨てながら） tira を再帰的に呼び出していく。この再帰は最終的に↓の Case H 節で停止する。Case H はリストを返すので、戻り値はリストになる。
  • tira は、与えたリストの第一引数と第二引数が異なれば、与えたリストの cdr を返す（Case H）。リストの長さが 2 以上の場合は、ここが再帰の終端になる。リストの cdr は常にリストなので、戻り値は結局リストになる。
  • tira は、空リストを与えた場合は空リストを返す（Case E）。
  • tira は、要素が一つのリストを与えた場合は空リストを返す（Case F）。

pack の解説

残るは肝心の pack だ。pack は (cons (pega lista) (pack (tira lista))) という形で再帰する。複雑だが、これまでと同様に一ステップずつ pega、 tira そして pack を展開（置換）していけばよい。

なお、pack は pega や tira ほど条件分岐の枝が多くない。本体部分は実質一通りしかないので、Case X というラベルはつけずに置換していく。

(defun pack (lista)
    (if (eql lista nil)
      nil
        (cons (pega lista) (pack (tira lista)))
    )
  )
1. pack 一回目の呼び出し
(pack '(a a a a b c c a a d e e e e))
2. pack 一回目の呼び出しを展開する
(cons (pega '(a a a a b c c a a d e e e e))
      (pack (tira '(a a a a b c c a a d e e e e))))
3. pega と tira を展開する

pega と tira をそれぞれ一ステップずつ展開すると非常に長くなってしまうため、以後は pega と tira の実行結果で置換する。

(cons '(a a a a)
      (pack '(b c c a a d e e e e)))
4. pack 二回目の呼び出しを展開する
(cons '(a a a a)
      (cons (pega '(b c c a a d e e e e))
            (pack (tira '(b c c a a d e e e e)))))
5. pega と tira を展開する
(cons '(a a a a)
      (cons '(b)
            (pack '(c c a a d e e e e))))
6. pack 三回目の呼び出しを展開する
(cons '(a a a a)
      (cons '(b)
            (cons (pega '(c c a a d e e e e))
                  (pack (tira '(c c a a d e e e e))))))
7. pega と tira を展開する
(cons '(a a a a)
      (cons '(b)
            (cons '(c c)
                  (pack '(a a d e e e e)))))
8. pack 四回目の呼び出しを展開する
(cons '(a a a a)
      (cons '(b)
            (cons '(c c)
                  (cons (pega '(a a d e e e e))
                        (pack (tira '(a a d e e e e)))))))
9. pega と tira を展開する
(cons '(a a a a)
      (cons '(b)
            (cons '(c c)
                  (cons '(a a)
                        (pack '(d e e e e))))))
10. pack 五回目の呼び出しを展開する
(cons '(a a a a)
      (cons '(b)
            (cons '(c c)
                  (cons '(a a)
                        (cons (pega '(d e e e e))
                              (pack (tira '(d e e e e))))))))
11. pega と tira を展開する
(cons '(a a a a)
      (cons '(b)
            (cons '(c c)
                  (cons '(a a)
                        (cons '(d)
                              (pack '(e e e e)))))))
12. pack 六回目の呼び出しを展開する
(cons '(a a a a)
      (cons '(b)
            (cons '(c c)
                  (cons '(a a)
                        (cons '(d)
                              (cons (pega '(e e e e))
                                    (pack (tira '(e e e e)))))))))
13. pega と tira を展開する
(cons '(a a a a)
      (cons '(b)
            (cons '(c c)
                  (cons '(a a)
                        (cons '(d)
                              (cons '(e e e e)
                                    (pack nil)))))))
14. pack 七回目の呼び出しを展開する

ようやく終わりが見えてきた。

ここで初めて pack の if 節のもう片方（再帰の終了条件）にマッチする。pack は空リストを与えると空リスト（nil）を返す。最終的な S 式はこのようになる。

(cons '(a a a a)
      (cons '(b)
            (cons '(c c)
                  (cons '(a a)
                        (cons '(d)
                              (cons '(e e e e)
                                    nil))))))

cons の数珠つなぎなので戻り値はリストになる。cons の数珠つなぎの末尾は空リストである。そして戻り値のリストの各要素は、 pega によって「連続した同じ要素」がまとめられたリストである。

15. S 式を評価する
(cons '(a a a a)
      (cons '(b)
            (cons '(c c)
                  (cons '(a a)
                        (cons '(d)
                              (cons '(e e e e)
                                    nil))))))
;;=> ((a a a a) (b) (c c) (a a) (d) (e e e e))

求めたい結果が得られた。

pack まとめ

pack は言葉で説明するのが難しいが（だから長ったらしく全部展開してみたわけだ）、cons しつつ再帰しているので最終的な S 式は cons の数珠つなぎになる。再起するからには pack の再起呼び出しに与えるリストはどこかで cdr して要素を減らしているはずで、それを念頭に置いて tira の実装と tira 単体の実行結果を丹念に見比べるのが理解の突破口になる。一見とっつきにくくて何をやってるのかわかりづらいが、tira が再帰の鍵である。

感想

pega と tira のような仕事をする補助関数を作る、というアイデアを自力で思いつける気がしない。

サンプルコード

動作検証に使ったサンプルコードは Gist に置きました。

L-99-p09.el · GitHub