为什么Haskell列表更有效率，如果它是关联的 [英] why Haskell list is more efficient if it's left associate

问题描述

我正在学习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 <= code> 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列表更有效率，如果它是关联的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！