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

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

4 голосов
/ 13 июня 2009

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

;; 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 принимать это внутреннее выражение без какой-либо оценки?

Ответы [ 4 ]

3 голосов
/ 14 июня 2009

Если вы не хотите идти по макро-маршруту, вы всегда можете просто отказаться от 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
3 голосов
/ 13 июня 2009

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

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

2 голосов
/ 13 июня 2009

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

1 голос
/ 13 июля 2012

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

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

...