Racket中take与take-while函数返回结果顺序差异原因咨询

问题重现 #

你实现了斐波那契生成器：

(require racket/generator)
(define fib (generator ()
            (define (f a b) 
               (yield a)
               (f b (+ a b)))
            (f 1 1)
        ))

同时实现了将生成器转换为流的take函数：

(define (take n gen)
    (define (f a acc) 
    (if (= a n) acc 
        (f (+ a 1) (stream-cons (gen) acc))))
    (f 0 (stream))
)

以及逻辑类似的take-while函数：

(define (take-while p gen)
    (define (f acc) 
    (let ([x (gen)])
        (if (not (p x)) acc (f (stream-cons x acc)) )))
    (f (stream))
)

运行结果如下：

(sequence->list (take-while (lambda (x) (< x 100)) fib))
'(89 55 34 21 13 8 5 3 2 1 1)

(sequence->list (take 5 fib))
'(233 377 610 987 1597)

你认为take-while的顺序正确，但疑惑take的结果顺序为何相反。

核心问题分析 #

首先纠正一个误解：take-while的结果顺序是错误的，正常斐波那契数列小于100的序列应为'(1 1 2 3 5 8 13 21 34 55 89)，你的输出是倒序的。两个函数的顺序问题根源一致：

1. 顺序颠倒的本质原因 #

你在构建流时，每次都将新生成的元素通过stream-cons x acc放到了当前累加流的头部。生成器是按顺序输出1,1,2,3,...,89,144,...的，第一个生成的元素会被压到流的最底层，最后一个满足条件的元素则在流的最前端，最终sequence->list转换后自然是倒序。

2. take结果看似“正序”的假象 #

你看到的take结果是正序，实际是两个因素导致：

• 生成器是有状态的：先运行take-while时，它已经消耗了生成器直到144（144不满足<100，停止但生成器已前进到下一个元素233）。
• 若从头开始调用take 5 fib，结果应为倒序的'(5 3 2 1 1)，你当前的正序结果要么是测试时重新初始化了生成器，要么是误写了代码逻辑。

修复方案 #

要得到正序结果，需要让新元素按生成顺序添加到流的正确位置，有两种常见方式：

方式一：递归回溯构建正序流 #

利用非尾递归，先递归到终止条件，再回溯时将元素添加到流的头部，保证顺序正确：

; 修复后的take函数
(define (take n gen)
  (if (= n 0)
      (stream)
      (stream-cons (gen) (take (- n 1) gen))))

; 修复后的take-while函数
(define (take-while p gen)
  (let ([x (gen)])
    (if (p x)
        (stream-cons x (take-while p gen))
        (stream))))

方式二：累加后反转（尾递归友好） #

先将元素收集到列表中，最后反转列表再转为流，适合处理较大的n值：

; 修复后的take函数
(define (take n gen)
  (define (f a acc)
    (if (= a n)
        (reverse acc)
        (f (+ a 1) (cons (gen) acc))))
  (list->stream (f 0 '())))

; 修复后的take-while函数
(define (take-while p gen)
  (define (f acc)
    (let ([x (gen)])
      (if (p x)
          (f (cons x acc))
          (reverse acc))))
  (list->stream (f '())))

额外提示：生成器的状态复用问题 #

生成器是一次性状态的，若想多次从头测试，建议将其封装为返回新生成器的函数：

(define (make-fib-generator)
  (generator ()
    (define (f a b)
      (yield a)
      (f b (+ a b)))
    (f 1 1)))

; 使用时每次创建新生成器
(sequence->list (take-while (lambda (x) (< x 100)) (make-fib-generator)))
; 输出：'(1 1 2 3 5 8 13 21 34 55 89)

内容的提问来源于stack exchange，提问作者gefei