haskell - 通过 fromList 创建(非列表)数据结构实际上会创建列表吗？

Question

基本上我很好奇代码是否像:

let myCollection = Data.SomeCollection.fromList [1, 2, foo]

实际上是在执行它在运行时的样子，并创建一个链表作为创建 SomeCollection 的中间步骤。 ——或者如果这只是为了语法方便，编译器避免在编译后的代码中列出列表？

抱歉，如果这是一个愚蠢的问题，但自从学习了一些 Haskell 后，我就一直想找出答案。

Answer 1

简短回答:也许，在某种程度上，但不是真的……

更长的答案:

当您说链表时，您是在以命令式的方式思考。 Haskell 既懒惰又实用，这使得这个问题很难回答。
[a,b,c]是 a:(b:(c:[])) 的简写.如果我们对此进行全面评估(例如尝试将其打印出来)，那么最终在内存中的内容看起来和行为很像 C 中的链表，但有更多的大脑。但这通常不会发生在功能设置中的列表上。大多数基于列表的函数的操作方式是对列表的头部做一些事情，然后将列表的尾部发送到其他地方(可能是同一个地方)。这意味着列表看起来确实像 x:xs在哪里 xs只是一些将创建列表其余部分的函数。 (GHC 术语中的一个 thunk)

整个列表不会像在命令式语言中那样创建，然后进行处理。它通过 fromList 流式传输一次运行一件。

至少这是大多数 fromList 的方式功能起作用。一个通用的 fromList集合可能如下所示:

fromList    :: [a] -> Collection a
fromList    =  Data.List.foldl' insert empty

一些集合可以利用一次添加多个元素。这些集合(我不知道，但我知道它们存在)将建立一个更广泛的内存列表。

然而，在编译器优化之外，通常情况下

fromList [1, 2, foo]

在计算上等效(在一个很小的常数因子内):

empty `insert` 1 `insert` 2 `insert` foo

免责声明:我不太了解任何 Haskell 实现的内部结构，无法绝对肯定地说它们如何评估代码中的列表常量，但这与现实相差不远。我等待来自 GHC 的启示如果我离基地很远的话，大师们。