performance - Haskell:我可以在同一个惰性列表上执行多次折叠而不将列表保存在内存中吗？

Question

我的背景是生物信息学，尤其是下一代测序，但问题是通用的；所以我将以一个日志文件为例。

该文件非常大(千兆字节大，已压缩，因此无法放入内存)，但易于解析(每一行都是一个条目)，因此我们可以轻松编写如下内容:

parse :: Lazy.ByteString -> [LogEntry]

现在，我想从日志文件中计算出很多统计数据。编写单独的函数是最简单的，例如:

totalEntries = length
nrBots = sum . map fromEnum . map isBotEntry
averageTimeOfDay = histogram . map extractHour

所有这些都是 foldl' k z . map f 的形式.

问题是，如果我尝试以最自然的方式使用它们，比如

main = do
    input <- Lazy.readFile "input.txt"
    let logEntries = parse input
        totalEntries' = totalEntries logEntries
        nrBots' = nrBots logEntries
        avgTOD = averageTimeOfDay logEntries
    print totalEntries'
    print nrBots'
    print avgTOD

这将在内存中分配整个列表，这不是我想要的。我希望折叠同步完成，以便可以对 cons 单元进行垃圾收集。如果我只计算一个统计数据，就会发生这种情况。

我可以编写一个大函数来执行此操作，但它是不可组合的代码。

或者，这就是我一直在做的，我分别运行每个 channel ，但这每次都会重新加载和解压缩文件。

Answer 1

这是对 sdcvvc 的评论的评论，指的是这个 'beautiful folding' essay太酷了——正如他所说，很漂亮——我忍不住加了Functor和 Applicative实例和其他一些现代化。同时折叠，例如，x y和 z是一个简单的产品:(,,) <$> x <*> y <*> z .我制作了一个 0.5GB 的小随机整数文件，在我生锈的笔记本电脑上计算长度、总和和最大值花了 10 秒。进一步的注释似乎没有帮助，但编译器可以看到 Int是我唯一感兴趣的；明显的map read . lines作为解析器导致了无望的空间和时间灾难，所以我粗略地使用了ByteString.readInt。 ;否则它基本上是 Data.List过程。

{-# LANGUAGE GADTs, BangPatterns #-}

import Data.List (foldl', unfoldr)
import Control.Applicative 
import qualified Data.ByteString.Lazy.Char8 as B

main = fmap readInts (B.readFile "int.txt") >>= print . fold allThree
  where allThree = (,,) <$> length_ <*> sum_ <*> maximum_

data Fold b c where  F ::  (a -> b -> a) -> a -> (a -> c) -> Fold b c
data Pair a b = P !a !b

instance Functor (Fold b) where  fmap f (F op x g) = F op x (f . g)

instance Applicative (Fold b) where
  pure c = F const () (const c)
  (F f x c) <*> (F g y c') = F (comb f g) (P x y) (c *** c')
    where comb f g (P a a') b = P (f a b) (g a' b)
          (***) f g (P x y) = f x ( g y)

fold :: Fold b c -> [b] -> c
fold (F f x c) bs = c $ (foldl' f x bs)

sum_, product_ :: Num a => Fold a a
length_ :: Fold a Int
sum_     = F (+) 0 id
product_ = F (*) 1 id
length_  = F (const . (+1)) 0 id
maximum_ = F max 0 id
readInts  = unfoldr $ \bs -> case B.readInt bs of
  Nothing      -> Nothing
  Just (n,bs2) -> if not (B.null bs2) then Just (n,B.tail bs2) 
                                      else Just (n,B.empty)

编辑:毫不奇怪，因为我们必须处理上面的未装箱类型，以及派生自例如的未装箱向量。一个 2G 文件可以放入内存中，如果对 Data.Vector.Uboxed http://hpaste.org/69270 进行明显的重新字母处理，速度会提高一倍，并且表现得更好一些。当然，这与具有 LogEntry 之类的类型无关。请注意， Fold type 和 Fold '乘法'概括了没有修改的顺序类型，因此例如与 Char 上的操作相关的折叠s 或 Word8 s 可以同时直接折叠在 ByteString 上。必须首先定义一个 foldB , 通过转写 fold使用 foldl' s 在各种 ByteString 模块中。但是 Fold Fold 的产品和产品s 与折叠 Char 的列表或向量的相同。 s 或 Word8 s