计划流和循环列表 [英] Scheme streams and circular lists

问题描述

在Scheme / Lisp中，我试图创建一个将列表转换为循环列表的函数。因此，我相信我需要构造一个无限流，其中列表的尾部指向列表的头部。

到目前为止， （b）

$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ b（cons（car l1）（delay l1copy）））
（cons（car l1）（delay（rotate-list（force（cdr l1））l1copy）））

所有的帮助都非常感谢。

解决方案

不，你不需要流创建一个循环列表。

创建循环列表有两种方法，标准Scheme方法和Racket方法因为Racket的conses是不可变的）。我将使用 SRFI 1 的 circular-list 函数。这里是参考实现：

$ $ p $ （define（circular-list val1。vals）
（let（（ans（cons val1 vals）））
（set-cdr！（last-pair ans）ans）
ans））


所做的是在给定值列表中找到最后一对，并且 set-cdr！ s回到那个开头名单。很简单，对吗？

在Racket中，conses是不可变的，所以 set-cdr！不存在。所以，Racket可以这样做：

 （define（circular-list val1。vals）
（let [ph（make-placeholder #f）]）
（placeholder-set！ph 
（cons val1（let loop（[vals vals]）
（if（null？vals）
 $ ph 
（cons（car vals）（loop（cdr vals）））））））
（make-reader-graph ph）））
  

这使用Racket的 make-reader-graph 功能处理周期。非常漂亮。 ： - ）

In Scheme/Lisp I am trying to make a function that converts a list into a circular list. Therefore, I believe I need to construct an infinite stream in which the tail of the list points to the head of the list.

Here is my code so far:

(define (rotate-list l1 l1copy)
  (if (null? (force (cdr l1)))
      (cons (car l1) (delay l1copy)))
      (cons (car l1) (delay (rotate-list (force (cdr l1)) l1copy))))

All help is greatly appreciated.

解决方案

No, you don't need streams to make a circular list.

There are two approaches to creating circular lists, the standard Scheme approach, and the Racket approach (since Racket's conses are immutable). I will look at examples using SRFI 1's circular-list function. Here's the reference implementation:

(define (circular-list val1 . vals)
  (let ((ans (cons val1 vals)))
    (set-cdr! (last-pair ans) ans)
    ans))

What that does is to find the last pair in the list of given values, and set-cdr!s it back to the beginning of that list. Pretty straightforward, right?

In Racket, conses are immutable, so set-cdr! does not exist. So instead, Racket does it this way:

(define (circular-list val1 . vals)
  (let ([ph (make-placeholder #f)])
    (placeholder-set! ph
      (cons val1 (let loop ([vals vals])
                   (if (null? vals)
                     ph
                     (cons (car vals) (loop (cdr vals)))))))
    (make-reader-graph ph)))

This uses Racket's make-reader-graph function to handle the cycles. Very nifty. :-)

这篇关于计划流和循环列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！