2010/03/12

"再帰も"ループも使わずに配列を逆順にする:継続呼び出し編

先日は、「再帰は厳密にはループじゃないよね?」というノリで書きました。
ヒネリたくてもヒネれず、Y combinator で書くなどしました。
今回は、The Seasoned Schemer で出てきた let/cc を用いてやってみました。

(やっぱこれって「再帰じゃない」とは言い張れないような気がしてきました。うまいこと書けてないだけかな。)

取り合えず以下コード


ちなみに先日のものはこちら


追記

いやー読んでもよくわからないっす・・・。力不足ですはい^^;
(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 '())))))
よく読んだらなんとなくわかりました。継続呼び出しでジャンプ(というか無限ループ的なもの)、andは継続呼び出しによる終了(脱出)のための条件分岐、副作用で蓄積と減算ですか。うーん難しいぃー^^;

追記2

擬似コードも説明もわかりやすかったです。
追記で書いたように、だいたい思った通りの動きのようで安心しました。でもやっぱりなんか異物感のようなものがありますねー・・・。@cametan_001さんの仰るように関数型的でないからなのでしょうか。

兎に角もっと書いてみる方が良さそうだなーという印象でした。

The Seasoned Schemer

2 件のコメント:

  1. 山崎です
    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] .

    返信削除
  2. 山崎先生

    いやー・・・パッと見てもよくわかりませんし、動作もイメージできませんorz

    Prologやると、これまた頭の作りが変わりそうですね!

    返信削除