问题描述
我正在学习Haskell的基础知识，并且遇到很多教程，指出如果使用++从左到右构造列表比从右向左更有效。但我似乎无法理解为什么。
例如，为什么这个
a ++（b ++（c ++（d ++（e ++ f））））
比
（（（（a ++ b）++ c）++ d）++ e）++ f
直至列表和 ++ 被实现。你可以想象列表正在被实现，就像
数据List a = Empty |缺点a（列表a）
只要将 [] 与空和：与缺点。这是Haskell中单链表的一个非常简单的定义。单连接列表的连接时间为 O（n），其中 n 是第一个列表的长度。为了理解为什么，回想一下，对于链表，你持有对头或第一个元素的引用，为了执行任何操作，你必须沿着列表走下去，检查每个值是否有后继。
因此，对于每个列表级联，编译器必须遍历第一个列表的整个长度。如果你有清单 a ， b ， c ，和 d ，长度 n1 ， n2 ， n3 和 n4 ，那么对于表达式
<$ p $ （$ a
$ >它先走下 a 构造 a ++ b ，然后将结果存储为 x ，自 a 具有 n1 n1 code>元素。您剩下的
（x ++ c）++ d
现在编译器向下遍历 x 来构造 x ++ c ，然后在 n1 + n2 步骤中存储这个结果为 y a 和 b 这次）。你留下了
y ++ d
现在 y 被执行，以 n1 + n2 + n3 步骤，共计 n1 +（n1 + n2）+（n1 + n2 + n3）= 3n1 + 2n2 + n3 步骤。
对于表达式
a ++（b ++（c ++ d ））
编译器从内部圆括号开始，构造 c ++ d - > x in n3 步骤，导致
a ++（b ++ x）
然后 b ++ x - > y 在 n2 步骤中，导致
a ++ y
终于在 n1 步骤，总步数为 n3 + n2 + n1 ，这肯定少于 3n1 + 2n2 + n3 。
I'm learning the basics of Haskell, and come across many tutorials saying that if a list is constructed from left to right using ++ is more efficient than from right to left. But I can't seem to understand why.
For example, why this
a ++ (b ++ (c ++ (d ++ (e ++ f))))
is more efficient than
((((a ++ b) ++ c) ++ d) ++ e) ++ f
It comes down to how lists and ++ is implemented. You can think of lists being implemented like
data List a = Empty | Cons a (List a)
Just replace [] with Empty and : with Cons. This is a very simple definition of a singly linked list in Haskell. Singly linked lists have a concatenation time of O(n), with n being the length of the first list. To understand why, recall that for linked lists you hold a reference to the head or first element, and in order to perform any operation you have to walk down the list, checking each value to see if it has a successor.
So for every list concatenation, the compiler has to walk down the entire length of the first list. If you have the lists a, b, c, and d with the lengths n1, n2, n3, and n4 respectively, then for the expression
((a ++ b) ++ c) ++ d
It first walks down a to construct a ++ b, then stores this result as x, taking n1 steps since a has n1 elements. You're left with
(x ++ c) ++ d
Now the compiler walks down x to construct x ++ c, then stores this result as y in n1 + n2 steps (it has to walk down elements of a and b this time). you're left with
y ++ d
Now y is walked down to perform the concatenation, taking n1 + n2 + n3 steps, for a total of n1 + (n1 + n2) + (n1 + n2 + n3) = 3n1 + 2n2 + n3 steps.
For the expression
a ++ (b ++ (c ++ d))
The compiler starts at the inner parentheses, construction c ++ d -> x in n3 steps, resulting in
a ++ (b ++ x)
Then b ++ x -> y in n2 steps, resulting in
a ++ y
Which is finally collapsed in n1 steps, with a total number of steps as n3 + n2 + n1, which is definitely fewer than 3n1 + 2n2 + n3.
这篇关于为什么Haskell列表更有效率，如果它是关联的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！