4

我试图找到一个实现，它使用我编写的过程来interleave扁平化惰性列表的惰性列表。lz-lst-accumulate这是到目前为止的代码：

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

(define interleave
  (lambda (lz1 lz2)
    (if (empty? lz1)
      (lz2)
      (cons (head lz1)
        (interleave (lz2) (lambda() (tail lz1)))))))

(define all-div-from-flattened
     (lambda (lower)
       (lz-lst-accumulate interleave '() (all-div-from lower))))

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

(define head
  (lambda (lz)
    (car lz)))

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

(define lz-lst-map
  (lambda (f lz)
    (if (empty? lz)
      lz
      (cons (f (head lz))
        (lambda () (lz-lst-map f (tail lz)))))))

; Signature: all-div-from (low)
; Type: [Number -> Lazy-list]
; Purpose: return a lazy-list of lazy-lists. The nested lazy-lists 
;          correspond to the integers greater than lower in an 
;          increasing order. Each nested lazy-list is the list of 
;          all integers divisible by i for some i>=lower.
; Pre-conditions: low is an integer
; Tests: > (define lz3 (all-div-from 7))
;        > (take lz3 3)
;        '((7 . #<procedure>) (8 . #<procedure>) (9 . #<procedure>))
;        > (take (head lz3) 3)
;        '(7 14 21)
;        > (take (head (tail lz3)) 3)
;        '(8 16 24)

(define all-div-from
    (lambda(lower)
      (cons (lz-lst-map (lambda(x) (* x lower)) (div-from 1 1))
            (lambda() (all-div-from (add1 lower))))))


; Signature: div-from (low int)
; Type: [[Number*Number]-> Lazy-list]
; Purpose: return the lazy-list of all integers that 
;          are larger than low and divisible by int
; Pre-conditions: int > low
; Tests: > (define lz1 (div-from 5 12))
;        > (take lz1 3)
;        '(12 24 36)
;        > (define lz2 (div-from 7 10))
;        > (take lz2 4)
;        '(10 20 30 40)
(define div-from
  (lambda (lower int)
    (lz-lst-filter (lambda(x) (> x (- lower 1))) 
      (lz-lst-map (lambda(x) (* x int)) (integers-from 1)))))

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

(define lz-lst-filter
  (lambda (p lz)
    (cond ((empty? lz) lz)
          ((p (head lz)) 
             (cons (head lz) 
               (lambda () (lz-lst-filter p (tail lz)))))
          (else (lz-lst-filter p (tail lz))))))

该过程all-div-from接收下限low并返回惰性列表的惰性列表。其中的每个惰性列表都是由div-from它接收一个下限low和一个整数int > low，并返回所有大于low且可被 整除的整数的惰性列表int。

输入和正确输出的示例：

 > (take (all-div-from-flattened 7) 10)
        '(7 8 14 9 21 16 28 10 35 24)

但是当我在解释器中尝试这一行时：

> (take (all-div-from-flattened 3) 3)

它进入一个无限循环。

我的执行必须使用lz-lst-accumulate,interleave和all-div-from-flattend程序。

有关如何使其工作的任何建议？

4

1 回答 1

5

您interleave不会生成惰性列表；它生成一个普通列表：它使用cons两个参数，第二个参数不包含在 a 中lambda。所以cons强制第二个参数通过，导致失控评估：

(define interleave
  (lambda (lz1 dlz2)    ; "delayed" lz2
    (if (empty? lz1)
      (dlz2)
      (cons (head lz1)
            ; here:
            (interleave (dlz2) (lambda () (tail lz1)))))))

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

(all-div-from lower)产生正确的输出，( (lower . <proc1>) . <proc2> )但调用(lz-lst-accumulate interleave '() (all-div-from lower))减少为

(interleave [lower . <proc1>]
            (lambda () (lz-lst-accumulate interleave '() (<proc2>))))

并且减少为

(cons lower 
      (interleave (lz-lst-accumulate interleave '() (<proc2>))
                  (lambda () (<proc1>))))

虽然它必须减少为

(cons lower 
      (lambda () (interleave ....)))

产生一个惰性列表。

显而易见的（现在）解决方案是添加缺少的lambda：

(define interleave
  (lambda (lz1 lz2)
    (if (empty? lz1)
      (lz2)
      (cons (head lz1)
            (lambda () (interleave (lz2) (lambda() (tail lz1))))))))

现在它运行正常：

（取（所有 div-from-flattened 7）10）
；值 12：（7 8 14 9 21 16 28 10 35 24）

您可以通过引入来大大简化您的代码

(define integers-from-by
  (lambda (n d) (cons n
    (lambda () (integers-from (+ n d) d)))))

然后，

;(define div-from
;  (lambda (lower int)
;    (lz-lst-filter (lambda(x) (> x (- lower 1))) 
;      (lz-lst-map (lambda(x) (* x int)) (integers-from 1)))))

(define mults-from-of    ; n in [int, 2*int ..], n >= lower
  (lambda (lower int)
    (let ((x (* (quotient (+ lower (- int 1)) int) int)))
      (integers-from-by x int))))

你也可以有

(define mults-above-of   ; n in [int, 2*int ..], n > lower
  (lambda (lower int)
    (let ((x (* (+ (quotient lower int) 1) int)))
      (integers-from-by x int))))

下一个，

; (define all-div-from
;    (lambda(lower)
;      (cons (lz-lst-map (lambda(x) (* x lower)) (div-from 1 1))
;            (lambda() (all-div-from (add1 lower))))))

(define all-mults-from
  (lambda (lower)
    (lz-lst-map (lambda (n) (mults-from-of n n))
                            ; or just (integers-from-by n n)
                (integers-from-by lower 1))))

如果您更改为按顺序组合流，并在定义中interleave切换到，则将按顺序定义所有合数的惰性列表，方法是像在 Eratosthenes 的筛子中那样向上计数。mults-above-ofall-mults-from(lz-lst-accumulate interleave-ordered '() (all-mults-from-above 2))

从这里开始，这只是让自己拥有自己的 Eratosthenes 惰性无限增量筛的又一步 （在该页面上搜索“SiCp”）。

另一个评论：take应该调整以不强制流的额外元素。更多在这里。

于 2014-05-02T11:56:37.603 回答