首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >函数式语言中的列表设计

问函数式语言中的列表设计
EN

Stack Overflow用户
提问于 2011-04-07 04:59:24
回答 5查看 420关注 0票数 5

我注意到,在Haskell和OCaml等函数式语言中,您可以使用列表执行两个操作。首先,你可以做x:xs,其中x是一个元素,xs是一个列表,结果是我们得到了一个新的列表,其中x在固定时间内附加到xs的开头。第二个是x++y,其中x和y都是列表,结果是我们得到了一个新的列表,其中y按照x中元素的数量以线性时间附加到x的末尾。现在我不是语言设计和编译器构建方面的专家,但在我看来,这很像是一个简单的链表实现,只有一个指针指向第一项。如果我要用像C++这样的语言实现这个数据结构,我会发现添加一个指向最后一个元素的指针通常很简单。在这种情况下,如果这些语言是以这种方式实现的(假设它们确实使用了所述的链表),则向最后一项添加“指针”将使将项添加到列表末尾变得更加有效,并允许与最后一个元素进行模式匹配。

我的问题是,这些数据结构真的是作为链表实现的吗?如果是,为什么它们不添加对最后一个元素的引用?

EN

回答 5

Stack Overflow用户

回答已采纳

发布于 2011-04-07 11:43:20

是的,它们确实是链表。但它们是不可变的。不变性的优点是,您不必担心还有谁拥有指向相同列表的指针。您可以选择编写x++y,但程序中的其他部分可能依赖于x保持不变。

从事这类语言编译器工作的人(我就是其中之一)不会担心这个成本,因为有很多其他的数据结构可以提供有效的访问:

  • 表示为两个列表的函数队列为两端提供了恒定时间的访问,并为put和get操作提供了摊销的恒定时间。
  • 一个更复杂的数据结构,如指状树,可以以非常低的成本提供多种列表访问。
  • 如果您只是想要恒定时间追加,John Hughes开发了一种出色的、简单的列表表示为函数,它就提供了这一点。(在Haskell库中,它们被称为DList.)

如果你对这类问题感兴趣,你可以从Chris Okasaki的书《纯函数式数据结构》和Ralf Hinze的一些不那么吓人的论文中获得有用的信息。

票数 11
EN

Stack Overflow用户

发布于 2011-04-07 05:09:11

你说过:

第二个是x++y,其中x和y都是列表,结果是y被附加到x的末尾,相对于x中元素的数量是线性的。

这在像Haskell这样的函数式语言中并非如此;y被附加到x的副本上,因为任何保持x的东西都依赖于它不变。

如果你打算复制所有的x,那么保留它的最后一个节点并不能给你带来任何好处。

票数 4
EN

Stack Overflow用户

发布于 2011-04-07 05:12:32

是的,它们是链表。在像Haskell和OCaml这样的语言中,你不会将项目添加到列表的末尾,句号。列表是不可变的。有一个创建新列表的操作- cons,您前面提到的:操作符。它接受一个元素和一个列表,并创建一个新的列表,其中元素作为头部,列表作为尾部。x++y占用线性时间的原因是,它必须将x的最后一个元素与y相联,然后将x的倒数第二个元素与该列表相联,以此类推,与x的每个元素相联。x中的任何cons单元格都不能重用,因为这会导致原始列表也发生变化。指向x的最后一个元素的指针在这里不是很有用-我们仍然需要遍历整个列表。

票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/5572876

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档