4

我试图以纯功能的方式解决这个问题，而不使用set!.

我已经编写了一个函数，它永远为斐波那契数列中的每个数字调用一个给定的 lambda。

(define (each-fib fn)
  (letrec
    ((next (lambda (a b)
             (fn a)
             (next b (+ a b)))))
    (next 0 1)))

我认为这是尽可能简洁，但如果我可以缩短它，请赐教:)

使用上面的定义，是否可以编写另一个函数，n从斐波那契数列中获取第一个数字并给我一个列表，但不使用变量突变来跟踪状态（我理解这不是真正的功能）。

函数签名不需要与以下相同......任何each-fib不使用而使用set!的方法都可以。

(take-n-fibs 7) ; (0 1 1 2 3 5 8)

我猜我可以使用某种 continuations + currying 技巧，但我一直想使用set!，这是我试图避免的（纯粹是为了学习目的/将我的思维转变为纯粹的功能）。

4

4 回答 4

3

试试这个，通过延迟评估使用惰性代码实现：

(define (each-fib fn)
  (letrec
      ((next (lambda (a b)
               (fn a)
               (delay (next b (+ a b))))))
    (next 0 1)))

(define (take-n-fibs n fn)
  (let loop ((i n)
             (promise (each-fib fn)))
    (when (positive? i)
      (loop (sub1 i) (force promise)))))

如前所述，each-fib可以通过使用命名let进一步简化：

(define (each-fib fn)
  (let next ((a 0) (b 1))
    (fn a)
    (delay (next b (+ a b)))))

无论哪种方式，都需要each-fib对使用delay原语进行一些修改，这会产生一个承诺：

Promise封装了一个表达式，通过force. 在一个承诺被forced 之后，承诺的每一个后续力量都会产生相同的结果。

我想不出一种方法来阻止原始（未修改）过程无限期地迭代。但是随着上述更改的到位，take-n-fibs可以根据需要继续强制懒惰评估尽可能多的值，仅此而已。

此外，take-n-fibs现在接收一个用于依次打印或处理每个值的函数，像这样使用它：

(take-n-fibs 10 (lambda (n) (printf "~a " n)))
> 0 1 1 2 3 5 8 13 21 34 55
于 2012-06-24T16:44:25.847 回答
1

您在斐波那契元素上提供迭代函数。如果您不想迭代每个元素来累积结果，则应该使用不同的原语，它是 a fold(or reduce) 而不是 a iter。
（可以使用延续将 aiter转换为 a ，但与使用 a或突变fold的直接解决方案相比，它的可读性和效率可能更低。）fold

但是请注意，使用通过突变更新的累加器也很好，只要您了解自己在做什么：为了方便起见，您在本地使用可变状态，但是take-n-fibs从外部看，该函数是纯观察的，所以您不要“用副作用污染整个程序。

的快速原型fold-fib，改编自您自己的代码。我对“何时停止折叠”做出了任意选择：如果函数返回null，我们返回当前累加器而不是继续折叠。

(define (fold-fib init fn) (letrec ([next (lambda (acc a b)
      (let ([acc2 (fn acc a)])
        (if (null? acc2) acc
            (next acc2 b (+ a b)))))])
      (next init 0 1)))

(reverse (fold-fib '() (lambda (acc n) (if (> n 10) null (cons n acc)))))

最好有一个更强大的约定来结束折叠。

于 2012-06-24T14:51:01.827 回答
1

我写了几个变种。首先你问如果

(define (each-fib fn)
  (letrec
    ((next (lambda (a b)
             (fn a)
             (next b (+ a b)))))
    (next 0 1)))

可以写得更短。该模式的使用如此频繁，以至于named let引入了特殊的语法称为。您的函数使用命名的 let 如下所示：

(define (each-fib fn)
  (let next ([a 0] [b 1])
    (fn a)
    (next b (+ a b))))

为了使控制从一个函数流向另一个函数，可以在支持 TCO 的语言中使用延续传递样式。每个函数都有一个额外的参数，通常称为 k（用于延续）。函数 k 表示下一步做什么。

使用这种风格，您可以编写如下程序：

(define (generate-fibs k)
  (let next ([a 0] [b 1] [k k])
    (k a (lambda (k1) 
           (next b (+ a b) k1)))))

(define (count-down n k)
  (let loop ([n n] [fibs '()] [next generate-fibs])
    (if (zero? n)
        (k fibs)
        (next (λ (a next)
                (loop (- n 1) (cons a fibs) next))))))

(count-down 5 values)

现在手动写样式有点烦人，所以引入协程可能会很方便。打破你不使用的规则set!我选择使用一个共享变量fibs，在该变量中generate-fibs重复使用新的斐波那契数。当count-down倒计时结束时，例程仅读取值。

(define (make-coroutine co-body)
  (letrec ([state (lambda () (co-body resume))]
           [resume (lambda (other)
                     (call/cc (lambda (here)
                                (set! state here)
                                (other))))])
    (lambda ()
      (state))))

(define fibs '())

(define generate-fib
  (make-coroutine 
   (lambda (resume)
     (let next ([a 0] [b 1])
       (set! fibs (cons a fibs))
       (resume count-down)
       (next b (+ a b))))))

(define count-down
  (make-coroutine   
   (lambda (resume)
     (let loop ([n 10])
       (if (zero? n)
           fibs
           (begin
             (resume generate-fib)
             (loop (- n 1))))))))

(count-down)

还有一个好处，你会得到一个带有通信线程的版本：

#lang racket
(letrec ([result #f]
         [count-down 
          (thread 
           (λ ()
             (let loop ([n 10] [fibs '()])
               (if (zero? n)
                   (set! result fibs)
                   (loop (- n 1) (cons (thread-receive) fibs))))))] 

         [produce-fibs
          (thread
           (λ ()
             (let next ([a 0] [b 1])
               (when (thread-running? count-down)
                 (thread-send count-down a)
                 (next b (+ a b))))))])
  (thread-wait count-down)
  result)

线程版本是特定于 Racket 的，其他版本应该可以在任何地方运行。

于 2012-06-24T16:20:57.660 回答
0

建立一个列表会很困难。但是仍然可以显示结果（以非常糟糕的方式）

#lang racket

(define (each-fib fn)
  (letrec
    ((next (lambda (a b)
             (fn a)
             (next b (+ a b)))))
    (next 0 1)))



(define (take-n-fibs n fn)
  (let/cc k
        (begin
          (each-fib (lambda (x) 
                      (if (= x (fib (+ n 1)))
                          (k (void))
                          (begin
                            (display (fn x))
                            (newline))))))))


(define fib
  (lambda (n)
    (letrec ((f
              (lambda (i a b)
                (if (<= n i)
                    a
                    (f (+ i 1) b (+ a b))))))
      (f 1 0 1))))

请注意，我正在使用常规斐波那契函数作为转义（就像我说的那样，以一种非常糟糕的方式）。我想没有人会推荐这样的编程。

反正

(take-n-fibs 7 (lambda (x) (* x x))) 
0
1
1
4
9
25
64
于 2012-06-24T18:40:28.497 回答