フムフムヌクヌクアプアア練習

LISP脳になるのはまだまだ先のようです( ´△｀)。

フムフムヌクヌクアプアア本の練習問題やってみました。

リストから要素を一つだけ削除する以下の手続き、

(define (delete-1 elt lis . options)
  (let-optionals* options ((cmp-fn equal?))
    (define (loop lis)
      (cond ((null? lis) '())
	    ((cmp-fn elt (car lis)) (cdr lis))
	    (else (cons (car lis) (loop (cdr lis))))))
    (loop lis)))

は、削除対象がなくてもリストをコピーしてしまうので、削除対象が無ければリストをコピーしないようにしなさい。

P.112 の練習問題の要約

ああでもないこうでもないと悩むこと1時間ほど。「cdrしたものとcdrをloop処理したものが同じ物であれば、この先に削除対象の要素はないと言うことが保証されるので、コピーせずに自分を返しても差し支えない」、と言うことに気がつきました。そうじゃない場合は、この先でリストが変更されてるからコピーが必要と。

できたソースは以下です。

(define (delete-1 elt lis . options)
  (let-optionals* options ((cmp-fn equal?))
    (define (loop lis)
      (cond [(null? lis) '()]
	    [(cmp-fn elt (car lis)) (cdr lis)]
	    [(eq? (cdr lis) (loop (cdr lis))) lis]
	    [else (cons (car lis) (loop (cdr lis)))]
	    ))
    (loop lis)))

まあ、テストはパスしました。ですが、loopの再帰呼び出しが2カ所あるため、(cdr lis)に残り要素がある場合に２回再帰しなきゃいけないので、効率悪過ぎです。うーむ。

そんなわけで納得行かず、解答探してみました(ぉ。サポートページで公開されている模範解答は以下です。

(define (delete-1 elt lis . options)
  (let-optionals* options ((cmp-fn equal?))
    (define (loop lis)
      (cond [(null? lis) '()]
            [(cmp-fn elt (car lis)) (cdr lis)]
            [else (let ((tail (loop (cdr lis))))
                    (if (eq? tail (cdr lis))
                      lis
                      (cons (car lis) tail)))]))
    (loop lis)))

ダウンロードページ

あ、なるほど。結果をletしとけばいいだけなんですね。当たり前っちゃあ当たり前でした。。。

もう一つ、ググって見つけた解答がこちら。こっちの方が好きです。

(define (delete-1 elt lis . options)
  (let-optionals* options ((cmp-fn equal?))
    (define (loop lis)
      (cond ([null? lis] '())
            ([cmp-fn elt (car lis)] (cdr lis))
            ([loop (cdr lis)] =>
             (lambda (tail)
               (if (eq? (cdr lis) tail)
                   lis
                   (cons (car lis) tail))))))
    (loop lis)))

[本][Scheme] プログラミングGauche p.112 の練習問題

つまり、letは本質的にはlambda式と一緒ってことですね。