Как мне составить Lazy List на нетерпеливом языке?

Question

Я хотел сделать ленивый список в Схеме. Это то, что я до сих пор.

;; Constructor for Pairs
(define (cons-stream a b)
  (cons a (λ() b)))

;; Selectors
(define (car-stream a-stream)
  (car a-stream))

(define (cdr-stream a-stream)
  ((cdr a-stream)))

;; Lazy List using the pairs
(define (lazy-list from)
  (cons-stream from (lazy-list (+ from 1))))

;; Take function
(define (take a-lazy-list number)
  (define (take-helper i )
    (if(= i number)
       empty
       (cons (car a-lazy-list) (take-helper (+ i 1)))))
  (take-helper 0))

Проблема с lazy-list заключается в том, что Scheme сначала оценивает внутреннее выражение (lazy-list (+ from 1)), в результате чего процедура переходит в бесконечную рекурсию.

Есть ли способ заставить con-stream принимать это внутреннее выражение без какой-либо оценки?

Answer 1

Решение состоит в том, чтобы использовать макрос. Я не специалист по схемам (особенно по макросам), но, возможно, этот фрагмент может послужить источником вдохновения:

(define-syntax pointer-to
   (syntax-rules ()
    ((pointer-to var)
     (make-pointer
      (lambda () var) ; the "pointer dereference" operation
      (lambda (value) (set! var value)))))) ; "pointer write"

Используется следующим образом:

(define x 1)
(define px (pointer-to x))
(pointer-set! px 2) ; this (in some sense) becomes `(set! x 2)'

Так что, может быть, вы хотите что-то вроде

(define-syntax lazy-cons
 (syntax-rules ()
  ((lazy-cons head lazytail)
   (cons head (lambda () lazytail)))))

Но я не уверен. Посмотри на define-syntax,

Answer 2

Если вы не хотите идти по макро-маршруту, вы всегда можете просто отказаться cons-stream и переписать lazy-list следующее:

(define (lazy-list from)
  (cons from (λ() (lazy-list (+ from 1)))))

Это, вероятно, самое простое, наиболее прагматичное решение, но оно подходит только для составления ленивых списков увеличивающихся чисел. Вы можете обобщить это, передав функцию, которая будет вызывать последовательные элементы списка при вызове:

(define (lazy-list-gen generator)
  (cons (generator)
        (λ() (lazy-list-gen generator))))

(define (lazy-list from)
  (lazy-list-gen
   (λ()
     (let ((ret from))
       (set! from (+ from 1))
       ret))))

Это работает довольно хорошо:

> (define x (lazy-list 1))
> (car-stream x)
1
> (car-stream (cdr-stream x))
2

Но в коде есть ошибка:

... continuing from above ...
> (car-stream (cdr-stream x))
3

Эта ошибка происходит потому, что вызов cdr-stream звонки generator снова. Мы можем решить эту проблему, кэшируя возвращаемое значение лямбды:

(define (lazy-list-gen generator)
  (cons (generator)
        (let ((gen-cache #f))
          (λ()
            (cond ((not gen-cache)
                   (set! gen-cache (lazy-list-gen generator))))
            gen-cache))))

Теперь все работает как надо:

> (define x (lazy-list 1))
> (car-stream x)
1
> (car-stream (cdr-stream x))
2
> (car-stream (cdr-stream x))
2
> (car-stream (cdr-stream (cdr-stream x)))
3
> (car-stream (cdr-stream x))
2

Answer 3

Ленивый список в Схеме называется потоком. Вот стандартное введение.

Answer 4

Вы действительно должны смотреть на SRFI-41

В частности, ленивые потоки, создаваемые рекурсивными функциями, будут сильно пропускать память на нетерпеливом языке, если вы специально не избегаете этого. Для этого рекурсивные функции нужно делать ленивыми, а не нетерпеливыми. Это означает, что ваша реализация для лени должна быть SRFI-45, которая экспортирует задержку, форсирование и ленивость. Функции, которые рекурсивно создают потоки, должны обернуть их тела в ленивый