有效地合并两个列表

Question

我正在学习Haskell,并与之合作List.

根据HaskellWiki,如果我想将两个列表合并在一起,我会写:

list1 ++ list2 

但是,根据这个答案,在大型列表中使用++将是低效的.

从研究开始,我遇到了这个SO页面,但是这个问题需要对输出的具体要求List.

我尝试了什么:

假设我有两个数字列表(对于这个例子,假设两个列表足够大,使用++效率低,如SO答案中所述):

 oldNumbers = [1,5,14,22,37]
 newNumbers = [3,10,17,27,34,69]
 allNumbers = oldNumbers:newNumbers

正如你所看到的那样,我试图添加oldNumbers到头部,newNumbers意图在之后allNumbers将其反转(忽略现在没有顺序,这是另一天的练习).

正如您可能猜到的那样,它产生了一个错误

error:
    * Non type-variable argument in the constraint: Num [a]
      (Use FlexibleContexts to permit this)
    * When checking the inferred type
        allNumbers :: forall a. (Num a, Num [a]) => [[a]]

因此,正如标题中所述,我将如何有效地合并两个列表？

Answer 1

根据HaskellWiki,如果我想将两个列表合并在一起,我会写:

list1 ++ list2 

但是,根据这个答案,++在大型列表上使用效率很低.

我认为你需要在这个答案中考虑上下文.如果我们追加两个列表a,并b与(++)再其追加两个列表中的O(M) (与米列表的长度).因此,就时间复杂度而言,这是有效的.人们不能比这更有效地构建这样的单链表.

@melpomene实际上指出了Haskell新手所犯的一个流行错误:他们在列表末尾添加了一个元素.再次,如果您只想将单个元素附加到列表中,那不是问题.如果要将n个元素追加到列表中,这是一个问题,因此,如果每次将单个元素追加到列表中,并且这样做n次,则算法将为O(n ²).

所以简而言之,从时间复杂的角度来看,(++)当你将两个列表附加在一起时并不慢,当你向它添加一个单例列表时也不会很慢.然而,就渐近行为而言,通常比将一个元素的列表重复附加到列表更好的方式,因为那时第一个操作数通常会变大,每次迭代只需要O(n)时间来附加一个元素到列表.通常,在这种情况下,可以对列表的尾部元素使用递归,或者例如反向构建列表.

(++) 因此,通过以不设计的方式使用它,你可以获得低效的行为,因此不是"本质上"低效的.

一个++非常慢的例子是执行"映射"的以下函数:

badmap :: (a -> b) -> [a] -> [b]
badmap f = go []
    where go temp [] = temp
          go temp (x:xs) = go (temp ++ [f x]) xs

这里有两个问题:

1. 它不是懒惰的,它需要在发出第一个元素之前评估整个列表; 和
2. 它将以二次方运行,因为对于输入列表中的每个元素,附加此元素将花费越来越多的时间.

实现地图的更有效方法是:

goodmap :: (a -> b) -> [a] -> [b]
goodmap f = go
    where go (x:xs) = f x : go xs
          go [] = []