Haskell 无意义的性能 - 有效地将多个函数映射到相同的数据

Question

我经常需要将多个函数映射到相同的数据。我已经实现了 dpMap 来为我做到这一点

dpMap fns = (`map` fns) . flip ($)

dpMap 是一个函数，这是否意味着我只读取一次数据 dt(就像使用相同输入的电路一样。毫无意义的系统会让人想起电路；只是管道没有数据)？

作为示例，考虑计算列表 dt 的最小值和最大值。

minimax dt = (dpMap [minimum, maximum]) dt

(我可以摆脱 dt 但必须使用 -XNoMonomorphismRestriction)

与以这样的全点形式实现相同的功能相比，是否有性能优势？:

minimax2 dt = [minimum dt, maximum dt]

编辑:是否有 dpMap 的通用实现可以与常量内存一起使用？

我发现了另一篇不错的博文:http://www.haskellforall.com/2013/08/composable-streaming-folds.html ;希望这有帮助。

<罢工>编辑2:在更多上下文之后，这里是一个解决方案，即使我没有 dpMap 的精确实现，该模式也足够简单，不需要单独的函数:

minimax = (,) <$> minimum <*> maximum

用法:

> minimax [1..100]
(1,100)

如果您还想计算总和和长度

func = (,,,) <$> minimum <*> maximum <*> sum <*> length

用法:

> func [1..100]
(1,100,5050,100)

<罢工>

Answer 1

TL;DR:语言本身的性能无法保证。没有任何。这是一个编译器的事情。

根据经验，命名实体将驻留在内存中。如果仅由一个使用者延迟访问，则可以合理地期望对其进行优化，以便编译后的程序将在恒定内存中运行。

内存单元的创建和消耗将交错进行，每个单元在处理后都会被GC回收。

<小时/>

在 minimax2 dt = [minimum dt, maximum dt] ，表达式[minimum dt, maximum dt]位于命名实体 dt 的范围内被定义为。最有可能(即几乎肯定)GHC 会将其分配为内存实体，即一次，并且两者 dt表达式内部将引用相同的实体(指向它，就像指针一样)。

但正如 Cat Plus Plus 在评论中指出的那样，当然如何访问实体是另一回事。并且两个子表达式将分别访问它，即它将完整保留在内存中。这可不好。

我们可以做得更好，通过仅访问一次、折叠并收集两条数据来找到答案。在这种情况下，几乎可以肯定的是，GHC 将执行优化，使该列表不会作为一个整体保留在内存中。

这就是通常所说的延迟使用列表。此时，其创建将与该一次访问交错进行，产生的每个内存单元将立即被 GC(垃圾收集)消耗并释放，从而实现恒定的内存操作。

但这取决于我们仅扫描列表一次的能力:

{-# OPTIONS_GHC -O2 -XBangPatterns #-}

import Data.List (foldl')

minmax :: (Ord b) => [b] -> (b, b)
minmax (x:xs) = foldl' (\(!a,!b) x -> (min a x,max b x)) (x,x) xs

Bang 模式可防止 thunk 累积，从而使对参数的评估更加急切。测试:

Prelude> minmax [1..6]
(1,6)
Prelude> minmax []
*** Exception: <interactive>:1:4-65: Non-exhaustive patterns in function minmax

空列表当然没有定义最小值或最大值。

为了启动优化，-O2使用 GHC 编译时必须使用标志。