Comment puis-je faire une liste Lazy dans une langue Impatient?

Question

Je voulais faire une liste paresseuse dans le schéma. Voilà ce que j'ai jusqu'à présent.

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

Le problème avec la liste paresseux est que le schéma évalue l'expression interne (-list paresseux (+ de 1)) provoque d'abord la procédure d'aller dans une récursion infinie.

Y at-il un moyen de faire le con-stream prendre cette expression intérieure sans évaluation?

Answer 1

La solution est d'utiliser une macro. Je ne suis pas expert en système (surtout pas sur les macros), mais peut-être cet extrait peut servir d'inspiration:

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

Il est utilisé comme suit:

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

Donc, vous voulez peut-être quelque chose comme

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

Mais je ne suis pas sûr. Jetez un oeil à define-syntax.

Answer 2

Si vous ne voulez pas aller la route macro, vous pouvez toujours simplement abandonner cons-stream et réécrire lazy-list comme suit:

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

Ceci est probablement le plus facile, la solution la plus pragmatique, mais il est seulement bon pour faire des listes de numéros paresseux incrémenter. Vous pouvez généraliser cela en passant dans une fonction qui va générer des éléments successifs de la liste lorsque appelé:

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

Cela fonctionne assez bien:

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

Mais il y a un bogue dans le code:

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

Cette erreur se produit parce que l'appel à cdr-stream appels generator à nouveau. Nous pouvons résoudre ce problème en mettant en cache la valeur de retour du 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))))

Maintenant, cela fonctionne comme il se doit:

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

Une liste paresseuse dans le schéma est connu comme un flux . Voici l'introduction standard.

Answer 4

Vous devriez vraiment regarder SRFI-41

Dans les cours particuliers, paresseux créés par des fonctions récursives fuira mémoire mal dans une langue avide, à moins que vous éviter spécifiquement. Pour ce faire, vous devez faire des fonctions récursives paresseux aussi, pas envie. Cela signifie que votre mise en œuvre de la paresse doit être SRFI-45 , qui exporte retard, la force, et paresseux. Les fonctions qui construisent les flux doivent récursive envelopper leur corps paresseux.