Building accumulator for lazy lists in Racket

lazy-evaluation, racket, scheme

Solution

In your `lz-lst-accumulate` you calculate once `(op (head lz) initial)` and then also `(op initial (head lz))`. This is inconsistent; both should be the same and actually calculated only once, since it's the same value:

(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))))))))

It works in your example with numbers only because you use the type-symmetrical operation `*`. With `cons` it wouldn't work.

Other than that it's OK. `lz-lst-accumulate` is usually known as left fold (`scanl` in Haskell, actually, since you produce the progression of "accumulated" values, `foldl f z xs = last (scanl f z xs)`).

re: your version of `take`, it is forcing one too many elements of a stream. Better make it

(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)))))))

so that it only forces as many elements as it has to produce, and not one more (which might be e.g. divergent, like `(/ 1 0)`, invalidating the whole calculation for no reason).

That way, the counter-example in SRFI 41 (of `(take 4 (stream-map 1/ (ints-from-by 4 -1)))`) will just work (it calculates `(1/4 1/3 1/2 1/1)` without forcing `1/0`, which the usual version of `take`, like the one you're using, would do).

Problem

I defined a simple lazy list of all integers from zero: ``` (define integers-from (lambda (n) (cons n (lambda () (integers-from (+ 1 n)))))) (define lz (integers-from 0)) ``` I also coded an accumaltor that gets a lazy list as a parameter ``` (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))))))) ``` Does this accumaltor answer the format of lazy lists? Here is a simple test of the accumulator: ``` (define acc (lz-lst-accumulate * 1 lz)) (take acc 4) => '(1 2 6 24) ``` `take` is a helper function that creates a list from the first `n` elements of a lazy list: ``` (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)))) )) ```

Original source