Lisp/Scheme 中的自引用数据结构

发布于 2024-07-14 08:46:29 字数 143 浏览 5 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

看透却不说透 2024-07-21 08:46:29

在 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 入门书籍。

In Common Lisp you can modify list contents, array contents, slots of CLOS instances, etc.

Common Lisp also allows to read and write circular data structures. Use

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

So-called pure Functional Programming Languages don't allow side-effects. Most Lisp dialects are not pure. They allow side-effects and they allow to modify data-structures.

See Lisp introduction books for more on that.

回复收藏 0 原文

草莓酥 2024-07-21 08:46:29

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

In Scheme, you can do it easily with set!, set-car!, and set-cdr! (and anything else ending in a bang ('!'), which indicates modification):

(let ((x '(1 2 3)))
  (set-car! x x)
  ; x is now the list (x 2 3), with the first element referring to itself
  )

回复收藏 0 原文

撩人痒 2024-07-21 08:46:29

Common Lisp 支持使用 setf 修改数据结构。

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

回复收藏 0 原文

和我恋爱吧 2024-07-21 08:46:29

您不需要“破坏性修改”来构造自引用数据结构；例如，在 Common Lisp 中，'#1=(#1#) 是一个包含自身的 cons-cell。
Scheme 和 Lisp 能够进行破坏性修改：您可以像这样构造上面的循环缺点：
<代码>
(让((x(cons nil nil)))
(rplaca xx) x)

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

回复收藏 0 原文

套路撩心 2024-07-21 08:46:29

是的，它们很有用。我的一位大学教授创建了一种方案类型，他称之为“美杜莎数字”。它们是任意精度的浮点数，可能包含重复小数。他有一个函数：

(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

如前所述，这是通过明智地应用 set-car 来完成的！并设置-CDR！

Yes, and they can be useful. One of my college professors created a Scheme type he called Medusa Numbers. They were arbitrary precision floating point numbers that could include repeating decimals. He had a function:

(create-medusa numerator denominator) ; or some such

which created the Medusa Number that represented the rational. As a result:

(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

as said before, this is done with judicious application of set-car! and set-cdr!

回复收藏 0 原文

蛮可爱 2024-07-21 08:46:29

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

回复收藏 0 原文

空城仅有旧梦在 2024-07-21 08:46:29

我赞成明显的计划技术；这个答案仅针对 Haskell。

在 Haskell 中，您可以使用 let 纯功能性地完成此操作，这被认为是很好的风格。一个很好的例子是 regexp 到 NFA 的转换。您还可以使用 IORef 强制执行此操作，这被认为是较差的风格，因为它会强制将所有代码放入 IO monad 中。

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

回复收藏 0 原文

一袭水袖舞倾城 2024-07-21 08:46:29

关闭示例：

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

CLOS example:

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

回复收藏 0 原文

太阳哥哥 2024-07-21 08:46:29

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

另请参阅 Haskell Wiki 页面: 喜结连理

回复收藏 0 原文

兮子 2024-07-21 08:46:29

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

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

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

（定义小纤维 
    （缺点流 0 
                 （缺点流 1 
                              （添加流（流-cdr fibs） 
                                           谎言）））） 
  
这个定义表明 fibs 是
以 0 和 1 开头的流，例如
流的其余部分可以是
通过向自身添加 fib 来生成
移动一位：

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

几乎忘记提及，延迟流存在于常用库 SRFI-40 或 SRFI-41 中。我认为这两个之一应该在最流行的方案中可用

Hmm, self referential data structures in Lisp/Scheme, and SICP streams are not mentioned? Well, to summarize, streams == lazily evaluated list. It might be exactly the kind of self reference you've intended, but it's a kind of self reference.

So, cons-stream in SICP is a syntax that delays evaluating its arguments. (cons-stream a b) will return immediately without evaluating a or b, and only evaluates a or b when you invoke car-stream or cdr-stream

From 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))))
This definition says that fibs is a
stream beginning with 0 and 1, such
that the rest of the stream can be
generated by adding fibs to itself
shifted by one place:

In this case, 'fibs' is assigned an object whose value is defined lazily in terms of 'fibs'

Almost forgot to mention, lazy streams live on in the commonly available libraries SRFI-40 or SRFI-41. One of these two should be available in most popular Schemes, I think

回复收藏 0 原文

昨迟人 2024-07-21 08:46:29

我在搜索“循环列表 LISP 方案”时偶然发现了这个问题。

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

首先，制作一个列表

(define a '(1 2 3))

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

(list? a)
> #t

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

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

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

(list? a)
> #f

（它是如何解决的？）

现在，如果你打印 a 你会发现一个无限长的 (1 2 3 1 2 3 1 2 ... 列表，并且你在 Stk 中，您可以使用 control-z 或 control-\ 来退出，

循环列表有什么用呢？

但是与模算术相关，例如一周中各天的循环列表 (MTWTFSSMTW ...)，或由 3 位表示的整数循环列表 (0 1 2 3 4 5 6 7 0 1 2 3 4 5 ..)

有现实世界的例子吗？

I stumbled upon this question while searching for "CIRCULAR LISTS LISP SCHEME".

This is how I can make one (in STk Scheme):

First, make a list

(define a '(1 2 3))

At this point, STk thinks a is a list.

(list? a)
> #t

Next, go to the last element (the 3 in this case) and replace the cdr which currently contains nil with a pointer to itself.

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

Now, STk thinks a is not a list.

(list? a)
> #f

(How does it work this out?)

Now if you print a you will find an infinitely long list of (1 2 3 1 2 3 1 2 ... and you will need to kill the program. In Stk you can control-z or control-\ to quit.

But what are circular-lists good for?

I can think of obscure examples to do with modulo arithmetic such as a circular list of the days of the week (M T W T F S S M T W ...), or a circular list of integers represented by 3 bits (0 1 2 3 4 5 6 7 0 1 2 3 4 5 ..).

Are there any real-world examples?

回复收藏 0 原文

~没有更多了~