哈斯克尔：我能完成超过同一懒列表数倍没有保留在内存中的列表？(Haskell: Can I perf

我的背景是生物信息学，特别是新一代测序，但问题是通用的; 所以我会用一个日志文件为例。

该文件非常大（吉大，压缩的，所以它不适合在内存中），但很容易解析（每行一个条目），所以我们可以很容易地编写如下：

parse :: Lazy.ByteString -> [LogEntry]

现在，我有很多，我想从日志文件来计算的统计数据。这是最简单的编写不同的功能，如：

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

所有这些都是形式foldl' kz . map f foldl' kz . 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:

这是一个关于sdcvvc的参考本评论评论“美丽的折叠”征文美丽，正如他所说的- -我忍不住将它真是太爽了Functor和Applicative实例和现代化建设的几个其他位。的，也就是说，同时的折叠x y和z是一个简单的产品： (,,) <$> x <*> y <*> z 。我做了小的随机整数半GB的文件，并花了10秒，以便给 - 诚然微不足道的 - 计算长度之和最大的在我的笔记本电脑生锈。它似乎并没有进一步注解来帮助，但是编译器可以看到Int一切都是我感兴趣的; 显而易见的map read . lines 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的文件可以存放在内存衍生未装箱向量做的，这是所有快两倍，而且有些更好的表现，如果它被赋予的数据明显relettering。 Vector.Uboxed http://hpaste.org/69270当然，这是不相关的，其中一个具有类型，如LogEntry不过要注意的是， Fold式和折叠“乘法”概括了连续类型未经修改，因此如褶皱与操作相关上Char S或Word8 s时，可以同时直接折叠在字节串。必须首先定义一个foldB ，通过relettering fold使用foldl' S IN不同的字节串的模块。但Fold S和产品Fold可相同的人，你会折的列表或矢量Char S或Word8小号