Как мне создать ленивый список на языке Eager?
-
13-09-2019 - |
Вопрос
Я хотел сделать ленивый список в Scheme.Это то, что у меня есть до сих пор.
;; 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))
Проблема с ленивым списком заключается в том, что Scheme сначала оценивает внутреннее выражение (ленивый список (+ от 1)) и процедура переходит в бесконечную рекурсию.
Есть ли способ заставить con-stream принимать это внутреннее выражение без какой-либо оценки?
Решение
Решение — использовать макрос.Я не эксперт по схемам (особенно по макросам), но, возможно, этот фрагмент может послужить вдохновением:
(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
.
Другие советы
Если вы не хотите идти по макромаршруту, вы всегда можете просто отказаться 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
Ленивый список в Scheme известен как транслировать. Вот стандартное введение.
Вам действительно стоит посмотреть СРФИ-41
В частности, ленивые потоки, созданные рекурсивными функциями, приводят к серьезной утечке памяти в активном языке. пока не ты специально избегаешь этого.Для этого вам также нужно сделать рекурсивные функции ленивыми, а не нетерпеливыми.Это означает, что ваша реализация лени должна быть СРФИ-45, который экспортирует задержку, силу, и ленивый.Функции, которые рекурсивно создают потоки, должны лениво обертывать свои тела.