performance - 加速流式数据类型

Question

我制作了一种应该模拟“流”的类型。这基本上是一个没有内存的列表。

data Stream a = forall s. Stream (s -> Maybe (a, s)) s

基本上一个流有两个元素。一个州 s ，以及一个获取状态并返回类型为 a 的元素的函数和新的状态。

我希望能够对流执行操作，所以我导入了 Data.Foldable并在其上定义流:

import Data.Foldable

instance Foldable Stream where
  foldr k z (Stream sf s) = go (sf s)
    where
      go Nothing = z
      go (Just (e, ns)) = e `k` go (sf ns)

为了测试我的流的速度，我定义了以下函数:

mysum = foldl' (+) 0

现在我们可以比较普通列表的速度和我的流类型:

x1 = [1..n]
x2 = Stream (\s -> if (s == n + 1) then Nothing else Just (s, s + 1)) 1

--main = print $ mysum x1
--main = print $ mysum x2

我的流大约是列表速度的一半(完整代码 here)。

此外，这是一个最好的情况，没有列表或流:

bestcase :: Int
bestcase = go 1 0 where
  go i c = if i == n then c + i else go (i+1) (c+i)

这比列表和流版本快得多。

所以我有两个问题:

如何让我的流版本至少与列表一样快。

如何让我的流版本接近 bestcase 的速度.

Answer 1

就目前而言 foldl'您来自 Foldable是根据您给它的文件夹定义的。默认实现非常出色且出奇地好

foldl' :: (b -> a -> b) -> b -> t a -> b
foldl' f z0 xs = foldr f' id xs z0
  where f' x k z = k $! f z x

但是 foldl' 是您的专长；幸运的是 Foldable类包括 foldl'作为一种方法，因此您可以将其添加到您的实例中。

 foldl' op acc0 (Stream sf s0) = loop s0 acc0
   where 
    loop !s !acc = case sf s  of 
      Nothing -> acc
      Just (a,s') -> loop s' (op acc a)

对我来说，这似乎与 bestcase 的时间差不多。
请注意，这是一个标准情况，我们需要在累加器上添加严格性注释。您可以查看 vector包对类似类型的处理 https://hackage.haskell.org/package/vector-0.10.12.2/docs/src/Data-Vector-Fusion-Stream.html对于一些想法；或在文本库的隐藏“融合”模块中 https://github.com/bos/text/blob/master/Data/Text/Internal/Fusion .