Scheme中的Fibonacci程序（使用define-datatype）

Question

我一直在嘗試使用定義數據類型方法在方案中編寫斐波納契程序，但無法這樣做。請告訴我它是如何完成的。

我已經寫了下面的表示獨立性代碼：

(define (top-k k) 
    k) 

(define (applyk k n) 
    (k n)) 

(define (fibind n k) 
    (cond 
    [(= n 0) (k 1)] 
    [(= n 1) (k 1)] 
    [else (fibind (- n 1) (fib1 n k))])) 

(define fib1 
    (lambda (n k) 
    (lambda (v) 
     (fibind (- n 2) (lambda (w) (k (+ v w))))))) 

編輯：我基本上要一個代碼（類似於下面的一個）發現斐波那契數

;;;;k:: []-> continuation? 
(define-datatype k k? 
[topk] 
[fact1-k (n number?) (saved-k k?)]) 

;;;appylk:: nat? continuation? -> nat? 
(define apply-k 
    (lambda (v c) 
    (cases k c 
    [topk() v] 
    [fact1-k (n saved-k) 
     (apply-k (* n v) saved-k)]))) 

;;;fact :: nat? continuation? -> nat? 
(define (fact n k) 
    (if (< n 2) 
     (apply-k n k) 
     (fact (- n 1) (fact1-k n k)))) 

Answer 1

下面是斐波那契CPS表示獨立性的代碼，

#lang racket 

(define top-k 
    (lambda(v) 
    v)) 

(define fib 
    (lambda (n) 
    (fib/k n top-k))) 

(define fib/k 
    (lambda (n k) 
    (cond 
     [ (= 1 n) 
       (apply-k k 0) ] 
     [ (= 2 n) 
       (apply-k k 1) ] 

     (else 
      (fib/k (sub1 n) (fib1-k n k)) 
    ) 
    ) 
) 
) 

(define fib1-k 
    (lambda (n k) 
    (lambda(v) 
     (fib/k (- n 2) (fib2-k v k)) 
    ))) 


(define fib2-k 
    (lambda(v k) 
    (lambda (w) 
     (apply-k k (+ w v)) 
    ))) 



(define apply-k 
    (lambda(k v) 
    (k v))) 

詳見本書的198頁Essentials of Programming Languages

我不知道你打電話來表達獨立是否真的如此。

Answer 2

您的代碼它看起來像你試圖通過延續傳球的方式來做到這一點。首先，讓我們來看看實現n個Fibonacci數的天真直接的方式：

(define (fib n) 
    ;; This is a naïve implementation, and will get 
    ;; *very* slow, *very* quickly. It's much more 
    ;; common to implement this as an iterative process 
    (cond 
    ((= n 0) 1) 
    ((= n 1) 1) 
    (else (+ (fib (- n 1)) 
      (fib (- n 2)))))) 

現在，翻譯成延續傳遞風格，我們只是打破某些地方的事情發生。對於n爲0或1的情況，我們只需撥打1即可。然而，在遞歸情況下，我們需要計算(- n 1)（稱爲f1）的斐波那契數，然後調用它的一些延續。儘管如此，延續並不是k，因爲仍有工作要做;我們仍然需要(- n 2)的號碼！延續以f1作爲參數，併爲我們計算斐波納契數(- n 2)（稱爲f2），並且必須調用一些延續。不過，這個延續並不是k。新的延續將有機會獲得f1和f2雖然，他們的總和就是k需求：

(define (fib% n k) 
    (cond 
    ((= n 0) (k 1)) 
    ((= n 1) (k 1)) 
    (else (fib% (- n 1) 
       (lambda (f1) 
        (fib% (- n 2) 
         (lambda (f2) 
          (k (+ f1 f2))))))))) 

> (fib% 1 display) 
1 
> (fib% 5 display) 
8 
> (fib% 8 display) 
34 

有更有效的方法來計算數字在Fibonacci序列中，雖然。典型的以1和1開始，然後計算下一個值（2），將其添加到先前的值（1）以得到3，將先前的值（2）添加到5，將其添加到先前的值（ 3）獲得8，依此類推。這看起來像：

(define (fib-it n) 
    ;; This is much more efficient, since it moves 
    ;; computes the numbers in the sequence sequentially. 
    (let fib ((a 1) (b 1) (n n)) 
    (if (zero? n) 
     a 
     (fib b (+ a b) (sub1 n))))) 

這已經是一個延續傳遞風格差不多，不同的是名爲let功能，fib返回a而不是調用k它。這可以這樣完成：

(define (fib-it% n k) 
    (let fib ((a 1) (b 1) (n n)) 
    (if (zero? n) 
     (k a) 
     (fib b (+ a b) (sub1 n))))) 

這感覺並不像它完成儘可能多的，因爲它是一個傳遞函數，它沒有做任何自我遞歸調用無論如何風格延續版本;與名爲let的迭代照顧了這一點。我們不妨寫了下面的，但它是不是很有趣：

(define (fib-it% n k) 
    (k (let fib ((a 1) (b 1) (n n)) 
     (if (zero? n) 
      a 
      (fib b (+ a b) (sub1 n))))))