كيف أقوم بإجراء قائمة كسول في لغة حريصة؟

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

المشكلة في القائمة الكسولة هي أن المخطط يقوم بتقييم التعبير الداخلي (القائمة الكسولة (+ من 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 تكرارا. يمكننا حل هذا عن طريق التخزين المؤقت قيمة العودة ل 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))))

الآن يعمل كما ينبغي:

> (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., ، والتي تصدر التأخير، القوة، و كسول. الوظائف التي تبني تدفقات متكررة يجب أن تلتف على أجسادهم في كسول.