最近体調が悪かったりして、夜勉強できていませんでしたが今日は時間が取れました。
プログラムも少し書かないと忘れてしまっている部分があって困ります。
リストから要素を1つ削除するdelete-1を普通に実装すると以下のようになります。
```lisp
`gutter:true;
(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)))
(use gauche.test)
(let ((data 1 2 3 4 5)))
(test* *non-copy delete-1* data (delete-1 6 data) eq?))
gauche> test non-copy delete-1, expects (1 2 3 4 5) ==> ERROR: GOT (1 2 3 4 5)
```
要素を何も削除しない場合でも、consで要素のコピーを作成してしまうので、無駄があります。
何も削除しない場合に、無駄の無いようにするにはどうすれば良いでしょうか。
...
全然わかりません。
ググると以下の回答が...[出展](http://ema-log.herokuapp.com/?date=20081025)
```lisp
`gutter:true;
(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 ((memo (loop (cdr lis))))
(if (eq? (cdr lis) memo) lis (cons (car lis) memo)))]))
(loop lis)))
(use gauche.test)
(let ((data (list 1 2 3 4 5)))
(test* "non-copy delete-1" data (delete-1 6 data) eq?))
```
なるほど、再帰的にやるとはこう言うことか...
elseの場合にcdrに対して再帰的にcallしておいて、結果をeq?で確認して同じなら元のlisを返すのか
全然わかりませんでした。
lisp脳への道は険しい。
0 件のコメント :
コメントを投稿