list - 有效地合并两个列表

Question

我目前正在学习 Haskell，并使用 List。

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

list1 ++ list2 

然而，根据this回答，在大列表上使用++ 效率低下。

通过研究，我发现了 this SO page ，但该问题需要对 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

According to the HaskellWiki, if I wanted to merge two lists together, I would write:

list1 ++ list2 

However, according to this answer, using ++ on a large list would be inefficient.

我认为您需要在此答案中考虑上下文。如果我们附加两个列表 a和 b与 (++)然后它在 O(m) 中附加两个列表(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. 它将以二次方时间运行，因为对于输入列表中的每个元素，追加该元素将花费越来越多的时间。

一个更有效的实现 map 的方法是:

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