直観に反する？

継続渡し形式が腑に落ちたので復習。

まず、直観的なのが、下の例のように k に渡される場合。“The Little Schemer”や“The Seasoned Schemer”ではコレクターとか〜&co とかで憶えています。

(define (dup-k xs)
  (define (recur xs k)
    (if (null? xs)
      (k '())
      (recur (cdr xs) (lambda (r) (k (cons (car xs) r))))))

  (recur xs values))

(dup-k '(a b c))
;;=> (a b c)

一方、 k に渡さない…というか、 k が末尾呼び出しではない場合、途端になんだこれ？となる。コレクター、〜&co にはあんまり無かったパターンです。(もしかしたらあったのかも。ローカルに写経したコードからは見つからなかったという)

(define (rev-k xs)
  (define (recur xs k)
    (if (null? xs)
      (k '())
      (recur (cdr xs) (lambda (r) (cons (car xs) (k r))))))

  (recur xs values))

(rev-k '(a b c))
;;=> (c b a)

上の方はさんざん動きを一歩ずつトレースしたから見慣れただけのかもしれない。というわけで、下の方を一歩一歩トレースします。

;; (rev-k '())
(rev-k '())
(recur '() values)
(recur '() (lambda (r) ;; そろえるために
             (values r)))
((lambda (r)
   (values r))
 '())
;;=> ()

;; (rev-k '(a))
(rev-k '(a))
(recur '(a) values)
(recur '(a) (lambda (r)
              (values r)))
(recur '()
       (lambda (r)
         (cons 'a
               ((lambda (r)
                  (values r))
                r))))
((lambda (r)
   (cons 'a
         ((lambda (r)
            (values r))
          r)))
 '())
;;=> (a)

;; (rev-k '(a b))
(rev-k '(a b))
(recur '(a b) values)
(recur '(a b) (lambda (r)
                (values r)))
(recur '(b)
       (lambda (r)
         (cons 'a
               ((lambda (r)
                  (values r))
                r))))
(recur '()
       (lambda (r)
         (cons 'b
               ((lambda (r)
                  (cons 'a
                        ((lambda (r)
                           (values r))
                         r)))
                r))))
((lambda (r)
   (cons 'b
         ((lambda (r)
            (cons 'a
                  ((lambda (r)
                     (values r))
                   r)))
          r)))
 '())
;;=> (b a)

;; (rev-k '(a b c))
(rev-k '(a b c))
(recur '(a b c) values)
(recur '(a b c) (lambda (r)
                  (values r)))
(recur '(b c)
       (lambda (r)
         (cons 'a
               ((lambda (r)
                  (values r))
                r))))
(recur '(c)
       (lambda (r)
         (cons 'b
               ((lambda (r)
                  (cons 'a
                        ((lambda (r)
                           (values r))
                         r)))
                r))))
(recur '()
       (lambda (r)
         (cons 'c
               ((lambda (r)
                 (cons 'b
                       ((lambda (r)
                          (cons 'a
                                ((lambda (r)
                                   (values r))
                                 r)))
                        r)))
                r))))
((lambda (r)
   (cons 'c
         ((lambda (r)
            (cons 'b
                  ((lambda (r)
                     (cons 'a
                           ((lambda (r)
                              (values r))
                            r)))
                   r)))
          r)))
 '())
;;=> (c b a)

このパターン、というか形状というかは、よくよく観察すると見覚えがある、 fold-right/fold-left です。

(use srfi-1 :only (xcons)) ;; xcons

(define dup (pa$ fold-right cons '())) ;; fold-right$ あるけれどそろえる
(define rev (pa$ fold-left xcons '()))

(let1 xs '(a b c)
  (values
   #0=(dup xs)
   (equal? (dup-k xs) #0#)
   #1=(rev xs)
   (equal? (rev-k xs) #1#)))
;;=> (a b c), #t, (c b a), #t

foldr

foldl

http://foldl.com/ は見られなくなっちゃっているようなので、とりあえずどちらも書いておきます。

どちらも直観的で納得できるようになったと思いたい。