Haskell: list 的底层数据结构是什么？
Haskell: What's the underlying data structure for list?
如果是链表，为什么不支持push_back？
如果只是简单的数组，为什么下标访问时需要线性时间？
感谢您的帮助。
编辑：我们可以像这样1:[2,3]，即push_front，在列表前面追加元素；但我们不能这样做：[2,3]:4，即 push_back。
ps。实际上我从 C++ 的 STL
中借用了 push_front/back
Haskell 列表是单链表。它支持附加到列表的末尾，但它必须遍历整个列表才能进行此操作。:
λ> let x = [1,2,3]
λ> x ++ [4]
[1,2,3,4]
如果push_back你的意思是在末尾添加一个元素，当然是"supports"了。要将元素 x 添加到列表 list（并得到一个如此构建的新列表），请使用表达式 list ++ [x].
请注意，这是一个 O(n) 操作，n 是 list.
的长度
那是因为它是一个单链表。它还回答了您关于下标的其他问题。
由于问题询问的是 "underlying implementation":
列表类型（概念上）定义如下：
data [a] = [] | a:[a]
你实际上不能写这个声明，因为列表的语法很奇怪。但是你自己也可以做出完全一样的东西
data List a = Nil | a :* List a
infixr 5 :*
当你写类似 [1,2,3] 的东西时，那只是 1:2:3:[] 的特殊语法。由于 : 关联到右边，这实际上意味着 1:(2:(3:[]))。列表上的函数从根本上说都是基于模式匹配的，一次只处理一个构造函数。您可能需要打开很多 : 构造函数才能到达列表的末尾，然后构建一堆 : 构造函数以在末尾放置一个带有额外元素的新版本。您可能使用的任何功能（如 ++）最终都会在内部经历这种过程。
如果是链表，为什么不支持push_back？
如果只是简单的数组，为什么下标访问时需要线性时间？
感谢您的帮助。
编辑：我们可以像这样1:[2,3]，即push_front，在列表前面追加元素；但我们不能这样做：[2,3]:4，即 push_back。
ps。实际上我从 C++ 的 STL
中借用了 push_front/backHaskell 列表是单链表。它支持附加到列表的末尾，但它必须遍历整个列表才能进行此操作。:
λ> let x = [1,2,3]
λ> x ++ [4]
[1,2,3,4]
如果push_back你的意思是在末尾添加一个元素，当然是"supports"了。要将元素 x 添加到列表 list（并得到一个如此构建的新列表），请使用表达式 list ++ [x].
请注意，这是一个 O(n) 操作，n 是 list.
那是因为它是一个单链表。它还回答了您关于下标的其他问题。
由于问题询问的是 "underlying implementation":
列表类型（概念上）定义如下：
data [a] = [] | a:[a]
你实际上不能写这个声明，因为列表的语法很奇怪。但是你自己也可以做出完全一样的东西
data List a = Nil | a :* List a
infixr 5 :*
当你写类似 [1,2,3] 的东西时，那只是 1:2:3:[] 的特殊语法。由于 : 关联到右边，这实际上意味着 1:(2:(3:[]))。列表上的函数从根本上说都是基于模式匹配的，一次只处理一个构造函数。您可能需要打开很多 : 构造函数才能到达列表的末尾，然后构建一堆 : 构造函数以在末尾放置一个带有额外元素的新版本。您可能使用的任何功能（如 ++）最终都会在内部经历这种过程。