[Haskell] 为什么列表操作++很昂贵？

时间：2022-02-10 23:59:51

博主是haskell新手。学习haskll的时候遇到了一些问题，在寻求答案的过程中产生了一些思考，可能理解存在偏差，希望各位不吝赐教。

提出问题

《Learn you a haskell for great good》里第六章关于函数foldl(左fold)的部分提到，++操作符比:要昂贵很多，所以我们一般用foldr来构造一个list

第一次看这段话的时候我并没有深究(实际上我认为这句话根本就有毛病，因为foldr也得用++，原文作者根本没把核心问题指出来)，因为haskell用都没用过几次，自然理解不了内在机制。最近刚好遇上了一个用(++)的机会，我想把一个Char数组转成String数组，实现如下(不重要，大致就是用foldl将剩余数组的内容塞进累加器数组里，用++来连接，不想看的直接跳过代码吧):

chars2String :: [Char] -> [String]
chars2Str chars = foldl (\strs c -> strs ++ [[c]]) [] chars

-- 当时没想到的更简便实现
chars2String :: [Char] -> [String]
chars2Str chars = map (\c -> [c]) chars

突然想到这不正是使用++的最坏情况吗？所以我花了不少时间去SOF等地方看别人的回答，为什么++会显得更加昂贵。

探索过程

++的源码实现是递归式的，并且底层使用了:，大部分的答案都有提到这一点，去看了源码确实是这样没错。（大致的做法就是将 ++ 左边的部分拆成 x1:x2:x3 ... 这样，右边不需要递归遍历）

可是仔细想一想这种递归的开销是O(n)。懂一些数据结构知识就知道，往数组(非链式)底部插入一个(或x个)值，相当于把已经存在的n个值全部抬高一个(或x个)数组位，开销必然是O(n)。也就是说不论你是什么语言，想要用非链式数组数据结构实现这样的功能开销都应该是一样的。

证明开销昂贵

先不论别的语言如何，现在博主来证明++开销的巨大，假如有这样的情况：

-- 从SOF的这个回答里受到很大启发:  https://*.com/questions/12296694/the-performance-of-with-lazy-evaluation
let a = (   (   (  [1,2]  ) ++ [3]   )   ++   [4]  )

计算步骤(伪代码)：

  1. [1,2] ++ [3] => 1 : 2 : [3] => [1,2,3]，这里通过递归遍历将[1,2]拆开，大致消耗O(2)
  2. [1,2,3] ++ [4] => 1 : 2 : 3 : [4] => [1,2,3,4]，又通过递归遍历将[1,2,3]拆开，大致消耗O(3)
  3. ...

很明显在步骤2，重复了递归遍历拆开[1,2]这个操作，也就是说继续这样循环下去，时间复杂度大致为O(1+2+3+4+...+n)，似乎可以化简为O(k * n^2) (k代表++左边数组的长度，n代表重复++的次数)

再观察刚才的代码，可以看到这和函数foldl所做的事情差不多，这就是为什么++开销在foldl会很昂贵的原因

也可以很廉价

但是，++也可以很廉价，想象这样的情况：

let a = (   [1]  ++  (   [2]   ++  [3,4]  )  )

相当于1 : 2 : [3,4]，时间复杂度是O(n)，n是++的次数，这和:操作是一样的。

上面的代码刚好是foldr所做的事情。这就是《Learn you a haskell for great good》作者写下那段话的原因。

对比其他语言

现在回头反观其他语言。假设对一个非链式数组进行如下操作：

noLinkedArray = []
noLinkedArray.prepend(1).prepend(2).prepend(3)

排除该语言对数组操作优化的可能，难道时间复杂度不也是O(0+1+2+3+...+n)吗？

我由此思考得出结论，这是一个普遍存在的问题，和haskell的底层机制没多大关系。

可是一码归一码，现在数组的首选应该都是LinkedArray吧，链式数组无论往头部还是尾部插入元素，单次时间复杂度都是O(1)，多次操作时间复杂度则是O(n)，不会出现O(k * n^2)这种天文运算

相关文章