(++)与懒惰评估的表现

Question

我一直在想这个问题,但我找不到令人满意的答案.

为什么(++)"贵"？在惰性评估下,我们不会评估像这样的表达式

xs ++ ys

在必要之前,即便如此,我们只会在需要时评估我们需要的部分.

有人可以解释我错过的东西吗？

Answer 1

如果访问整个结果列表,延迟评估将不会保存任何计算.它只会延迟它,直到你需要每个特定的元素,但最后,你必须计算相同的东西.

如果遍历连接列表xs ++ ys,访问第一个part(xs)的每个元素会增加一些不变的开销,检查是否xs花费了.

因此,如果您关联++到左侧或右侧,它会产生很大的不同.

• 如果您关联n长的名单k到左像(..(xs1 ++ xs2) ... ) ++ xsn,然后访问每个第一k要素需要O(n)时间,访问每个接下来的k那些将O(n-1)等于是遍历整个列表将采取O(k n^2).你可以检查一下

  sum $ foldl (++) [] (replicate 100000 [1])
  

  需要很长时间.

• 如果您关联n长的名单k到右像xs1 ++ ( ..(xsn_1 ++ xsn) .. ),那么你会得到每个元素的唯一不变的开销,所以遍历整个列表将是唯一的O(k n).你可以检查一下

  sum $ foldr (++) [] (replicate 100000 [1])
  

  很合理.

编辑:这只是隐藏在背后的魔力ShowS.如果你将每个字符串转换xs为 showString xs :: String -> String(showString只是别名(++))并组成这些函数,那么无论你如何关联它们的组成,最后它们将从右到左应用 - 正是我们需要获得线性时间复杂度.(这仅仅是因为(f . g) x是f (g x).)

你可以检查两者

length $ (foldl (.) id (replicate 1000000 (showString "x"))) ""

和

length $ (foldr (.) id (replicate 1000000 (showString "x"))) ""

在合理的时间内运行(foldr速度稍快,因为从右侧编写函数时它的开销较小,但两者在元素数量上都是线性的).

Answer 2

这不是对自己太昂贵了，问题就出现了，当你开始合并一大堆的++从左至右：这种连锁被评为像

  ( ([1,2] ++ [3,4]) ++ [5,6] ) ++ [7,8]
? let a = ([1,2] ++ [3,4]) ++ [5,6]
        ? let b = [1,2] ++ [3,4]
                ? let c = [1,2]
                  in  head c : tail c ++ [3,4]
                    ? 1 : [2] ++ [3,4]
                    ? 1 : 2 : [] ++ [3,4]
                    ? 1 : 2 : [3,4]
                    ? [1,2,3,4]
          in  head b : tail b ++ [5,6]
            ? 1 : [2,3,4] ++ [5,6]
            ? 1:2 : [3,4] ++ [5,6]
            ? 1:2:3 : [4] ++ [5,6]
            ? 1:2:3:4 : [] ++ [5,6]
            ? 1:2:3:4:[5,6]
            ? [1,2,3,4,5,6]
  in head a : tail a ++ [7,8]
   ? 1 : [2,3,4,5,6] ++ [7,8]
   ? 1:2 : [3,4,5,6] ++ [7,8]
   ? 1:2:3 : [4,5,6] ++ [7,8]
   ? 1:2:3:4 : [5,6] ++ [7,8]
   ? 1:2:3:4:5 : [6] ++ [7,8]
   ? 1:2:3:4:5:6 : [] ++ [7,8]
   ? 1:2:3:4:5:6 : [7,8]
   ? [1,2,3,4,5,6,7,8]

在那里您可以清楚地看到二次复杂性。即使您只想评估第n个元素，您仍然必须在所有这些lets 中挖掘自己的方式。这就是为什么++is infixr, for[1,2] ++ ( [3,4] ++ ([5,6] ++ [7,8]) )实际上效率更高。但是如果你在设计一个简单的序列化器时不小心，你可能很容易得到一个像上面那样的链。这是初学者被警告的主要原因++。

除此之外，Prelude.++与 egBytestring操作相比速度较慢，原因很简单，因为它是通过遍历链表来工作的，而链表的缓存使用情况总是不理想等，但这并没有那么大的问题；这会阻止您实现类似 C 的性能，但仅使用普通列表正确编写程序，++并且仍然可以轻松地与用 Python 编写的类似程序相媲美。