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

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

我可以写一个这样做的大函数,但它是不可组合的代码.

或者,这就是我一直在做的,我分别运行每个传递,但每次重新加载和解压缩文件.

Answer 1

要处理懒惰数据多次,在恒定空间中,您可以做三件事:

• 从头开始重新构建懒惰列表n次
• 熔丝n进入单个顺序折叠,在锁定步骤中执行每个步骤.
• 用于par同时进行n次并行遍历

这些是你的选择.最后一个是最酷的:)

Answer 2

这是对sdcvvc的评论的评论,指的是这篇"美丽的折叠"文章 它是如此酷 - 美丽,正如他所说 - 我无法抗拒添加Functor和Applicative实例和其他一些现代化.的,同时折叠说,x y而且z是一个简单的产品:(,,) <$> x <*> y <*> z.我制作了一个半千兆字节的小型随机整数文件,花了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文件派生的未装箱的矢量可以适合内存,如果给出明显的数据重新传输,这都是两倍的速度和更好的表现. Vector.Uboxed http://hpaste.org/69270 当然LogEntry ,如果Fold类型和Fold'乘法'在没有修正的情况下对顺序类型进行推广,那么这与类似Note的类型无关.因此,例如与Chars 上的运算相关联的折叠或者Word8s可以直接在ByteString上折叠.首先必须foldB通过重新定义来定义a ,以在各种ByteString模块中fold使用foldl's.但Folds和s的产品Fold与你折叠Chars或Word8s 的列表或向量的相同