ヒネリたくてもヒネれず、Y combinator で書くなどしました。
今回は、The Seasoned Schemer で出てきた let/cc を用いてやってみました。
(やっぱこれって「再帰じゃない」とは言い張れないような気がしてきました。うまいこと書けてないだけかな。)
取り合えず以下コード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(define (my-reverse ls) | |
(let/cc continue | |
(letrec | |
((r (lambda (acc l) | |
(if (null? l) | |
acc | |
(continue (r (cons (car l) | |
acc) | |
(cdr l))))))) | |
(r '() ls)))) | |
(my-reverse '(1 2 3 4 5)) | |
; -> (5 4 3 2 1) |
ちなみに先日のものはこちら
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
; reverse | |
(define (my-reverse ls) | |
(reverse ls)) | |
(my-reverse '(1 2 3)) | |
; fold | |
(define (my-reverse ls) | |
(fold cons '() ls)) | |
(my-reverse '(1 2 3 4 5)) | |
;-> (5 4 3 2 1) | |
; recur | |
(define (my-reverse ls) | |
(letrec | |
((rev (lambda (ret l) | |
(if (null? l) | |
ret | |
(rev (cons (car l) ret) | |
(cdr l)))))) | |
(rev '() ls))) | |
(my-reverse '(a b c)) | |
; -> (c b a) | |
; y combinator | |
(define (my-reverse ls) | |
(((lambda (f) | |
(f f)) | |
(lambda (f) | |
(lambda (ret l) | |
(if (null? l) | |
ret | |
((f f)(cons (car l) ret)(cdr l)))))) | |
'() ls)) | |
(my-reverse '(a b c)) | |
; -> (c b a) |
追記
いやー読んでもよくわからないっす・・・。力不足ですはい^^;(define (my-reverse ls) (let/cc return (let ((r #f)) (let ((l ls) (acc '())) (let/cc continue (set! r continue)) (and (null? l) (return acc)) (set! acc (cons (car l) acc)) (set! l (cdr l)) (r '()))))) |
追記2
擬似コードも説明もわかりやすかったです。追記で書いたように、だいたい思った通りの動きのようで安心しました。でもやっぱりなんか異物感のようなものがありますねー・・・。@cametan_001さんの仰るように関数型的でないからなのでしょうか。
兎に角もっと書いてみる方が良さそうだなーという印象でした。
山崎です
返信削除prolog で差分リストを使ったリバースです。
述語の再帰だけで(スコーレム)関数は使っていないので、可逆的に利用可能
rev(X,X,Y,Y).
rev([A|X1],X2,Y1,Y2) :- rev(X1,X2,Y1,[A|Y2]).
実行結果
?- rev([1,2,3,4],[],R,[]).
R = [4, 3, 2, 1].
?- rev(R,[],[4,3,2,1],[]).
R = [1, 2, 3, 4] .
山崎先生
返信削除いやー・・・パッと見てもよくわかりませんし、動作もイメージできませんorz
Prologやると、これまた頭の作りが変わりそうですね!