ACL 4章

Scheme

ANSI Common Lisp読み。


練習問題が変態過ぎ。

長年にわたる議論の末、ある政府委員会が次のように決定した。リストは第一要素を示すために、cdrを使い、その残りを示すためにcarを用いなければならない。この方針にしたがって、以下の関数を定義せよ。

cons,list,length,member

どんな政府委員会だよ。


回答例を見ながら答え合わせしてみると、破壊的にやっちゃった方が効率の良いものが多い。


P.Graham 著 ANSI Common LISP 練習問題解答


例えば、mapを使って、要素に位置を示す数を加える問題。

(pos+ '(7 5 1 4)) ; (7 6 3 7)

length取って、iotaして2個のリストでmapとか書いてたけど、全然効率が悪い。

set!を使ってインデックスを加えたほうがいい。なるほど。


まだ「最長」経路問題が残ってるので、ちまちま考えてみる。


出来た。

  • 検索が完了した経路をどんどん除いていく。
  • 循環チェックは(A B C)とあって、同じのがあったら循環してることがわかる。
  • 最後まで残る経路が最長なので、経路が無くなったら、最後の経路を返す。
(define (longest-path start net)
  (letrec
    ((bfs (lambda (queue acc)
            (if (null? queue)
                (reverse (car acc))
                (let* ((path (car queue))
                       (node (car path))
                       (new (new-paths path node)))
                      (cond ((null? new)
                             (bfs (cdr queue) (cons path acc))) ; 新たな経路がない
                            ((member node (cdr path))
                             (bfs (cdr queue) (cons (cdr path) acc))) ; 循環してた
                            (else
                              (bfs (append (cdr queue) new) acc))))))) ; まだまだ
     (new-paths (lambda (path node)
                  (let ((finds (assoc node net)))
                       (if finds
                           (map (lambda (n)
                                  (cons n path))
                                (cdr finds))
                           '())))))
    (bfs (list (list start)) '())))

(longest-path 'A '((A B) (B C D) (C A D) (D E))) ; (A B C D E)

新たな経路が無いことを確認するのに手間取った。


まとめ。

  • ノードの終了は、新たな経路が見つからないか、循環してるかを調べればわかる。
  • 最長を求めるなんて無理じゃねと思ってたけど、循環を除けば最長もわかる。

勉強になった。