Como posso fazer uma lista preguiçoso em uma linguagem Ansioso?

Question

Eu queria fazer uma lista preguiçoso no esquema. Isto é o que eu tenho até agora.

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

O problema com a lista-preguiçoso é que avalia o Esquema (-lista preguiçoso (+ a partir de 1)) expressão interna primeira fazendo com que o procedimento para entrar em uma recursividade infinita.

Existe uma maneira de fazer a con-stream tomar essa expressão interior sem qualquer avaliação?

Answer 1

A solução é usar uma macro. Não sou especialista esquema (especialmente não sobre macros), mas talvez esse trecho pode servir como inspiração:

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

É usado da seguinte forma:

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

Então, talvez você quer algo como

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

Mas eu não tenho certeza. Ter um olhar para define-syntax.

Answer 2

Se você não quiser ir a rota macro, você sempre pode simplesmente abandonar cons-stream e reescrever lazy-list da seguinte forma:

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

Esta é provavelmente a solução mais fácil, mais pragmática, mas é apenas bom para fazer listas preguiçosos de números de incremento. Você pode generalizar isso passando em uma função que irá gerar elementos sucessivos da lista quando chamado:

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

Isso funciona muito bem:

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

Mas há um bug no código:

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

Este erro ocorre porque a chamada para cdr-stream chama generator novamente. Podemos resolver isso pelo cache o valor de retorno do lambda:

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

Agora, ele funciona como deveria:

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

Uma lista preguiçoso no esquema é conhecido como um fluxo . Aqui está a introdução padrão.

Answer 4

Você deve realmente olhar para SRFI-41

Em particular, os fluxos, preguiçoso criados por funções recursivas vai vazar memória mal numa língua ansiosa, menos você especificamente evitá-lo. Para fazer isso, você precisa fazer funções recursivas preguiçoso também, não ansioso. Isto significa que suas necessidades de implementação preguiça de ser SRFI-45 , que exporta atraso, força, e preguiçoso. Funções que construir córregos recursiva deve envolver seus corpos em preguiçoso.