是否可以在没有突变的情况下在 Scheme 中创建循环数据结构？

Question

我可以像这样在 Scheme 中创建一个循环数据结构：

(define my-pair (cons 1 1))
(set-car! my-pair my-pair)

是否可以在不使用变异的情况下在 Scheme 中创建循环数据结构？（我正在准备关于引用计数限制的讲座。）

Answer 1

通过关注 link 相关问题 (Why don't purely functional languages use reference counting?)，我看到了对 letrec 的引用。这让我意识到我确实可以在 Scheme 中创建一个循环 "data structure":

(letrec ((add (lambda (x y) (if (>= x y) (+ x y) (add2 y x))))
         (add2 (lambda (x y) (if (>= x y) (+ x y) (add y x)))))
  (add 1 5))

Answer 2

你可以用闭包创建惰性列表：

; The infinite list (1 1 1 ...
(define ones
  (letrec ((x (cons 1 (lambda () x))))
    x))

> ones
'(1 . #<procedure>)
> ((cdr ones))
'(1 . #<procedure>)

验证循环的身份检查：

> (eq? ones ((cdr ones)))
#t

Answer 3

添加到@molbdnilo 回答大多数方案实施定义 delay 和 force，允许创建所谓的流（定义在 SICP).

; The infinite list (1 1 1 ...
(define ones (cons 1 (delay ones)))

> ones
(1 . #<promise>)

> (force (cdr ones))
(1 . #<promise>)

(eq? ones (force (cdr ones)))
#t

delay 和 force 可以实现为只是 lambda 表达式的宏。您甚至可以编写处理流的过程，例如过滤器或映射。

编辑：

同样由 R7RS 定义，您可以创建带有基准标签的真实循环列表。

(define x '#0=(a b c . #0#))
x
;; ==> #0=(a b c . #0#)
(eq? x (cdddr x))
#t

如果 Scheme 完全支持 R7RS 规范，它应该允许以相同的方式定义和显示循环列表。注意在Kawa Scheme中会循环打印显示你需要使用的循环列表(write x).

是否可以在没有突变的情况下在 Scheme 中创建循环数据结构？

Is it possible to create a circular data structure in Scheme without mutation?

scheme

functional-programming

reference-counting