blocks|key|1613523|text|在Scheme中，您可以轻松地使用set!、set-car!和set-cdr!+(以及任何其他以bang+('!')结尾的内容，表示修改)：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1613524|(let+((x+'(1+2+3)))
++(set-car!+x+x)
++;+x+is+now+the+list+(x+2+3),+with+the+first+element+referring+to+itself
++)|code-block|syntax|javascript|1613525|entityMap^0|H|4|M|8|V|8|1I|3|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@$9|N|A|O|B|C]|$9|P|A|Q|B|C]|$9|R|A|S|B|C]|$9|T|A|U|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|V|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|W|8|@]|D|@]|E|$]]]|L|$]]

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

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

blocks|key|1613559|text|Common+Lisp支持使用setf修改数据结构。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1613560|您可以通过tying+the+knot在Haskell中构建循环数据结构。|1613561|entityMap|0|LINK|mutability|MUTABLE|url|http://www.haskell.org/haskellwiki/Tying_the_Knot^0|F|4|0|5|E|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@$9|Q|A|R|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|S|8|@]|D|@$9|T|A|U|1|V]]|E|$]]|$1|H|3|-4|5|6|7|W|8|@]|D|@]|E|$]]]|I|$J|$5|K|L|M|E|$N|O]]]]

Common Lisp supports modification of data structures with <code>setf</code>.

You can build a circular data structure in Haskell by <a href="http://www.haskell.org/haskellwiki/Tying_the_Knot" rel="noreferrer">tying the knot</a>.

blocks|key|1613606|text|是的，它们可以是有用的。我的一位大学教授创建了一种名为Medusa+Numbers的Scheme类型。它们是任意精度的浮点数，可以包含重复的小数。他有一个功能：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1613607|(create-medusa+numerator+denominator)+;+or+some+such|code-block|syntax|javascript|1613608|它创造了代表理性的美杜莎数字。结果是：|1613609|(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|1613610|如前所述，这是通过set-car的明智应用来完成的！和set-cdr！|1613611|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|S|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

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:

<pre><code>(create-medusa numerator denominator) ; or some such
</code></pre>

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

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

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

blocks|key|1613693|text|这不仅是可能的，而且是Common+Lisp对象系统的核心:+standard-class是其自身的一个实例！|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1613694|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Not only is it possible, it's pretty central to the Common Lisp Object System: standard-class is an instance of itself!

blocks|key|1613769|text|我推荐了显而易见的Scheme技术；这个答案只针对Haskell。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1613770|在Haskell中，您可以纯粹使用let来实现这一点，这被认为是一种很好的风格。一个很好的例子是regexp到NFA的转换。您也可以使用IORefs强制执行此操作，这被认为是糟糕的风格，因为它会强制您的所有代码都放入IO+monad中。|offset|length|style|CODE|1613771|一般来说，Haskell的惰性计算适合于循环和无限数据结构的可爱的函数实现。在任何复杂的let绑定中，绑定的所有内容都可以在所有定义中使用。例如，将特定的有限状态机转换为Haskell是轻而易举的，无论它可能有多少个周期。|1613772|entityMap^0|0|H|3|1W|5|0|18|3|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@$D|N|E|O|F|G]|$D|P|E|Q|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|R|8|@$D|S|E|T|F|G]]|9|@]|A|$]]|$1|J|3|-4|5|6|7|U|8|@]|9|@]|A|$]]]|K|$]]

I upvoted the obvious Scheme techniques; this answer addresses only Haskell.

In Haskell you can do this purely functionally using <code>let</code>, which is considered good style. One nice example is regexp-to-NFA conversion. You can also do it imperatively using <code>IORef</code>s, which is considered poor style as it forces all your code into the IO monad.

In general Haskell's lazy evaluation lends itself to lovely functional implementations of both cyclic and infinite data structures. In any complex <code>let</code> binding, all things bound may be used in all definitions. For example translating a particular finite-state machine into Haskell is a snap, no matter how many cycles it may have.

blocks|key|1613819|text|StackOverflow上的Tying+the+Knot+(circular+data+structures+in+Haskell)|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1613820|另请参阅Haskell+Wiki页面：Tying+the+Knot|1613821|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/357956/explanation-of-tying-the-knot|1|https://wiki.haskell.org/Tying_the_Knot^0|F|1G|0|0|J|E|1|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@$A|U|B|V|1|W]]|C|$]]|$1|F|3|-4|5|6|7|X|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]|N|$5|I|J|K|C|$L|O]]]]

<a href="https://stackoverflow.com/questions/357956/explanation-of-tying-the-knot">Tying the Knot (circular data structures in Haskell)</a> on StackOverflow

See also the Haskell Wiki page: <a href="https://wiki.haskell.org/Tying_the_Knot" rel="nofollow noreferrer">Tying the Knot</a>

blocks|key|1613909|text|我在搜索“循环列表LISP方案”时偶然发现了这个问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1613910|这就是我如何制作一个(在STk方案中)：|1613911|首先，列一张清单|1613912|(define+a+'(1+2+3))|code-block|syntax|javascript|1613913|在这一点上，STk认为a是一个列表。|1613914|(list?+a)
>+#t|1613915|接下来，转到最后一个元素(本例中为3+)，并将当前包含nil的cdr替换为指向其自身的指针。|offset|length|style|CODE|1613916|(set-cdr!+(cdr+(+cdr+a))+a)|1613917|现在，STk认为a不是一个列表。|1613918|(list?+a)
>+#f|1613919|(它是如何实现的？)|1613920|现在，如果你打印a，你会发现一个无限长的(1+2+3+1+2+3+1+2+...列表，你需要杀死这个程序。在Stk中，你可以用control-z或control-\退出。|1613921|但是循环列表有什么好处呢？|1613922|我可以想到一些与模运算相关的晦涩难懂的例子，比如一周中各天的循环列表(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+..)表示的整数循环列表。|1613923|有什么真实的例子吗？|1613924|entityMap^0|0|0|0|0|0|0|H|1|R|3|V|3|0|0|0|0|0|8|1|K|K|1R|9|21|9|0|0|Y|P|1T|W|0|0^^$0|@$1|2|3|4|5|6|7|1C|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1D|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|1E|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|1F|8|@]|9|@]|A|$I|J]]|$1|K|3|L|5|6|7|1G|8|@]|9|@]|A|$]]|$1|M|3|N|5|H|7|1H|8|@]|9|@]|A|$I|J]]|$1|O|3|P|5|6|7|1I|8|@$Q|1J|R|1K|S|T]|$Q|1L|R|1M|S|T]|$Q|1N|R|1O|S|T]]|9|@]|A|$]]|$1|U|3|V|5|H|7|1P|8|@]|9|@]|A|$I|J]]|$1|W|3|X|5|6|7|1Q|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|H|7|1R|8|@]|9|@]|A|$I|J]]|$1|10|3|11|5|6|7|1S|8|@]|9|@]|A|$]]|$1|12|3|13|5|6|7|1T|8|@$Q|1U|R|1V|S|T]|$Q|1W|R|1X|S|T]|$Q|1Y|R|1Z|S|T]|$Q|20|R|21|S|T]]|9|@]|A|$]]|$1|14|3|15|5|6|7|22|8|@]|9|@]|A|$]]|$1|16|3|17|5|6|7|23|8|@$Q|24|R|25|S|T]|$Q|26|R|27|S|T]]|9|@]|A|$]]|$1|18|3|19|5|6|7|28|8|@]|9|@]|A|$]]|$1|1A|3|-4|5|6|7|29|8|@]|9|@]|A|$]]]|1B|$]]

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

<pre><code>(define a '(1 2 3))
</code></pre>

At this point, STk thinks a is a list.

<pre><code>(list? a)
&gt; #t
</code></pre>

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

<pre><code>(set-cdr! (cdr ( cdr a)) a)
</code></pre>

Now, STk thinks a is not a list.

<pre><code>(list? a)
&gt; #f
</code></pre>

(How does it work this out?)

Now if you print <code>a</code> you will find an infinitely long list of <code>(1 2 3 1 2 3 1 2 ...</code> and you will need to kill the program. In Stk you can <code>control-z</code> or <code>control-\</code> 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 <code>(M T W T F S S M T W ...)</code>, or a circular list of integers represented by 3 bits <code>(0 1 2 3 4 5 6 7 0 1 2 3 4 5 ..)</code>.

Are there any real-world examples?

Is there a way to construct a self-referential data structure (say a graph with cycles) in lisp or scheme? I'd never thought about it before, but playing around I can find no straightforward way to make one due to the lack of a way to make destructive modification. Is this just an essential flaw of functional languages, and if so, what about lazy functional languages like haskell?

Self-referential data structures in Lisp/Scheme

数据结构

有没有一种方法可以在lisp或scheme中构建自引用数据结构(比如带圈的图)？我以前从来没有想过它，但由于缺乏进行破坏性修改的方法，我找不到简单的方法来制作一个。这只是函数式语言的一个本质缺陷吗?如果是这样，那么像haskell这样的懒惰函数式语言又如何呢？

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

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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