通过fromList创建(非列表)数据结构是否实际创建了列表？

Question

基本上我很好奇,如果代码如下:

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

实际上是在运行时看起来是什么样的,并创建链接列表作为创建SomeCollection-or 的中间步骤,如果这只是语法上的便利,并且编译器避免在编译的代码中创建列表？

如果这是一个愚蠢的问题,请道歉,但自从学习一些Haskell以来,我一直想知道.

Answer 1

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

更长的答案:

当你说链表时,你正在考虑强制性的术语.Haskell是懒惰和功能性的,这使得这个问题难以回答.

[a,b,c]是短手的a:(b:(c:[])).如果我们对此进行全面评估(例如尝试将其打印出来),内存中的内容看起来和行为很像C中的链表,但是有更多的大脑.但通常情况下,功能设置中的列表不会发生这种情况.大多数基于列表的函数的操作方式是通过对列表的头部执行某些操作并将列表的尾部发送到其他位置(可能是在同一位置).这意味着列表看起来真的像x:xs这里xs只是一些功能,将创建列表的其余部分.(一个形实转换在GHC术语)

不会创建整个列表,然后像在命令式语言中那样进行处理.它一次通过一个功能流式传输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如果我离开基地,我等待大师们的启示.