在Racket中为延迟列表构建累加器

Question

我定义了一个从零开始的所有整数的简单惰性列表：

(define integers-from
  (lambda (n) 
    (cons n
          (lambda () (integers-from (+ 1 n))))))

(define lz (integers-from 0))

我还编码了一个将惰性列表作为参数的累加器

(define lz-lst-accumulate
  (lambda (op initial lz)
    (if (null? lz)
        initial
        (cons (op (head lz) initial)  
              (lambda () (lz-lst-accumulate op (op initial (head lz)) (tail lz))))))) 

这个累加器会回答惰性列表的格式吗？这是对累加器的简单测试：

(define acc (lz-lst-accumulate * 1 lz))
(take acc 4)
=> '(1 2 6 24)

take是一个帮助函数，它从n懒惰列表的前几个元素创建一个列表：

(define head car)

(define tail
  (lambda (lz-lst)
     ((cdr lz-lst)) ))

(define take
  (lambda (lz-lst n)
    (if (= n 0)
        (list)
        (cons (car lz-lst)
              (take (tail lz-lst) (sub1 n)))) ))

Answer 1

在你的lz-lst-accumulate你计算一次(op (head lz) initial)，然后也(op initial (head lz))。这是不一致的；两者应该相同，并且实际上仅计算一次，因为它的值相同：

(define lz-lst-accumulate
  (lambda (op initial lz)
    (if (lz-lst-empty? lz)
        initial
        (let ((val (op (head lz) initial)))
           (cons val
              (lambda () (lz-lst-accumulate op val (tail lz))))))))

它仅在您使用数字对称运算的情况下在您的示例中起作用，因为您使用类型对称运算*。用cons它是行不通的。

除此之外，还可以。lz-lst-accumulate通常称为左折（scanl实际上在Haskell中，因为您产生“累积”值的级数foldl f z xs = last (scanl f z xs)）。

回复：您的的版本take，它迫使流中的元素过多。更好地做到

(define take
  (lambda (lz n)
    (if (or (<= n 0) (lz-lst-empty? lz))
      (list)
      (if (= n 1)
        (list (car lz))      ; already forced
        (cons (car lz)
              (take (tail lz) (sub1 n)))))))

因此，它只会强制生成所需数量的元素，而不会强制生成更多元素（例如，可能发散，如(/ 1 0)无缘无故使整个计算无效）。

这样，SRFI 41（of(take 4 (stream-map 1/ (ints-from-by 4 -1)))）中的反例就可以正常工作（它(1/4 1/3 1/2 1/1)无需强制即可进行计算，而 com1/0的常规版本（take如您所使用的版本）可以做到）。