18

有没有办法在lisp或scheme中构建一个自引用数据结构（比如一个带循环的图）？我以前从未想过它，但由于缺乏进行破坏性修改的方法，我找不到直接的方法来制作它。这只是函数式语言的一个本质缺陷吗？如果是这样，那么像 haskell 这样的惰性函数式语言呢？

4

11 回答 11

15

在 Common Lisp 中，您可以修改列表内容、数组内容、CLOS 实例的插槽等。

Common Lisp 还允许读写循环数据结构。利用

? (setf *print-circle* t)
T

; a list of two symbols: (foo bar)

? (defvar *ex1* (list 'foo 'bar))
*EX1*

; now let the first list element point to the list,
; Common Lisp prints the circular list

? (setf (first *ex1*) *ex1*)
#1=(#1# BAR)

; one can also read such a list

? '#1=(#1# BAR)
#1=(#1# BAR)

; What is the first element? The list itself

? (first '#1=(#1# BAR))
#1=(#1# BAR)
?

所谓的纯函数式编程语言不允许副作用。大多数 Lisp 方言并不纯粹。它们允许副作用，并且允许修改数据结构。

有关更多信息，请参阅 Lisp 介绍书籍。

于 2009-03-03T09:33:35.703 回答
9

Common Lisp 支持使用setf.

您可以通过打结在 Haskell 中构建循环数据结构。

于 2009-03-03T04:05:16.023 回答
9

在 Scheme 中，您可以使用set!、set-car!和set-cdr!（以及以 bang ( ) 结尾的任何其他内容'!'，表示修改）轻松完成：

(let ((x '(1 2 3)))
  (set-car! x x)
  ; x is now the list (x 2 3), with the first element referring to itself
  )
于 2009-03-03T03:35:51.723 回答
5

  1. 您不需要“破坏性修改”来构建自引用数据结构；例如，在 Common Lisp 中，'#1=(#1#)是一个包含自身的 cons-cell。

  2. Scheme 和 Lisp 能够进行破坏性修改：您可以像这样构建上面的循环 cons： (let ((x (cons nil nil))) (rplaca x x) x)

你能告诉我们你在学习 Lisp/Scheme 时使用了什么材料吗？我正在为我们的黑色直升机编制一份目标清单；这种关于 Lisp 和 Scheme 的错误信息的传播必须停止。

于 2009-03-03T14:49:58.687 回答
3

是的，它们很有用。我的一位大学教授创建了一个名为 Medusa Numbers 的 Scheme 类型。它们是可以包含重复小数的任意精度浮点数。他有一个功能：

(create-medusa numerator denominator) ; or some such

它创造了代表理性的美杜莎数。因此：

(define one-third (create-medusa 1 3))
one-third => ; scheme hangs - when you look at a medusa number you turn to stone
(add-medusa one-third (add-medusa one-third one-third)) => 1

如前所述，这是通过设置车的明智应用完成的！和设置-cdr！

于 2009-03-03T18:30:51.840 回答
3

这不仅是可能的，而且是 Common Lisp 对象系统的核心：标准类是它自己的一个实例！

于 2009-03-03T23:08:41.937 回答
3

我赞成明显的方案技术；此答案仅针对 Haskell。

在 Haskell 中，您可以使用 纯函数式来执行此操作let，这被认为是很好的风格。一个很好的例子是正则表达式到 NFA 的转换。您也可以使用IORefs 命令式地执行此操作，这被认为是糟糕的样式，因为它强制您的所有代码进入 IO monad。

一般来说，Haskell 的惰性求值适用于循环和无限数据结构的可爱功能实现。在任何复杂let的绑定中，所有绑定的事物都可以在所有定义中使用。例如，将特定的有限状态机翻译成 Haskell 是一件轻而易举的事，无论它可能有多少个周期。

于 2009-03-04T04:10:03.723 回答
1

关闭示例：

（定义类节点（）
  ((child :accessor node-child :initarg :child)))

(defun make-node-cycle ()
  (let* ((node1 (make-instance 'node))
         (node2 (make-instance 'node :child node1)))
     (setf (node-child node1) node2)))
于 2009-03-03T18:14:03.860 回答
1

在 StackOverflow 上打结（Haskell 中的循环数据结构）

另请参阅 Haskell Wiki 页面：打结

于 2009-08-06T13:32:07.047 回答
0

我在搜索“CIRCULAR LISTS LISP SCHEME”时偶然发现了这个问题。

这就是我如何制作一个（在 STk 方案中）：

首先，列一个清单

(define a '(1 2 3))

此时，STk 认为 a 是一个列表。

(list? a)
> #t

接下来，转到最后一个元素（3在本例中为 the）并将cdr当前包含的元素替换nil为指向自身的指针。

(set-cdr! (cdr ( cdr a)) a)

现在，STk 认为 a 不是列表。

(list? a)
> #f

（它是如何解决的？）

现在，如果您打印a，您会发现一个无限长的列表，(1 2 3 1 2 3 1 2 ...您将需要终止该程序。在 Stk 你可以control-z或control-\退出。

但是循环列表有什么用呢？

我可以想到一些与模算术有关的晦涩示例，例如一周中各天的(M T W T F S S M T W ...)循环列表，或由 3 位表示的整数的循环列表(0 1 2 3 4 5 6 7 0 1 2 3 4 5 ..)。

有没有现实世界的例子？

于 2010-03-07T06:03:44.337 回答
0

嗯，没有提到 Lisp/Scheme 和 SICP 流中的自引用数据结构？好吧，总而言之，流 == 惰性评估列表。它可能正是您想要的那种自我参照，但它是一种自我参照。

因此，cons-stream在 SICP 中是一种延迟评估其参数的语法。 (cons-stream a b)将立即返回而不评估 a 或 b，并且仅在您调用car-stream或时评估 a 或 bcdr-stream

来自 SICP，http://mitpress.mit.edu/sicp/full-text/sicp/book/node71.html : >

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))

这个定义说 fibs 是一个以 0 和 1 开头的流，因此流的其余部分可以通过将 fibs 添加到自身移位一个位置来生成：

在这种情况下，“fibs”被分配了一个对象，其值是根据“fibs”延迟定义的

差点忘了提，惰性流存在于常用库 SRFI-40 或 SRFI-41 中。我认为这两个中的一个应该在最流行的方案中可用

于 2009-06-18T06:30:49.117 回答