我制作了一种应该模拟“流”的类型。这基本上是一个没有内存的列表。
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
的速度. 最佳答案
就目前而言 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 .
关于performance - 加速流式数据类型,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27683948/