list - Haskell:扫描列表并为每个元素应用不同的函数

Question

我需要扫描文档并为文件中的每个字符串累积不同函数的输出。在文件的任何给定行上运行的函数取决于该行中的内容。

通过对我想要收集的每个列表进行完整的文件传递，我可以非常低效地做到这一点。示例伪代码:

at :: B.ByteString -> Maybe Atom
at line
    | line == ATOM record = do stuff to return Just Atom
    | otherwise = Nothing

ot :: B.ByteString -> Maybe Sheet
ot line
    | line == SHEET record = do other stuff to return Just Sheet
    | otherwise = Nothing

然后，我会将这些函数中的每一个映射到文件中的整个行列表，以获得 Atom 和 Sheets 的完整列表:

mapper :: [B.ByteString] -> IO ()
mapper lines = do
    let atoms = mapMaybe at lines
    let sheets = mapMaybe to lines
    -- Do stuff with my atoms and sheets

但是，这是低效的，因为我正在为我尝试创建的每个列表映射整个字符串列表。相反，我只想在行字符串列表中映射一次，在我通过它时识别每一行，然后应用适当的函数并将这些值存储在不同的列表中。

我的 C 心态想要这样做(伪代码):

mapper' :: [B.ByteString] -> IO ()
mapper' lines = do
    let atoms = []
    let sheets = []
    for line in lines:
        | line == ATOM record = (atoms = atoms ++ at line)
        | line == SHEET record = (sheets = sheets ++ ot line)
    -- Now 'atoms' is a complete list of all the ATOM records
    --  and 'sheets' is a complete list of all the SHEET records

这样做的 Haskell 方法是什么？我根本无法让我的函数式编程思维提出解决方案。

Answer 1

首先，我认为其他人提供的答案至少在 95% 的情况下都有效。使用适当的数据类型(或在某些情况下为元组)为手头的问题编写代码始终是一种好习惯。但是，有时您确实事先并不知道要在列表中查找什么，在这些情况下，尝试列举所有可能性是困难的/耗时的/容易出错的。或者，您正在编写同一类事物的多个变体(手动将多个折叠内联为一个)，并且您想捕获抽象。

幸运的是，有一些技巧可以提供帮助。

框架解决方案

(有点自我宣传)

首先，各种“iteratee/enumerator”包通常提供处理这类问题的函数。我最熟悉iteratee ，这将让您执行以下操作:

import Data.Iteratee as I
import Data.Iteratee.Char
import Data.Maybe

-- first, you'll need some way to process the Atoms/Sheets/etc. you're getting
-- if you want to just return them as a list, you can use the built-in
-- stream2list function

-- next, create stream transformers
-- given at :: B.ByteString -> Maybe Atom
-- create a stream transformer from ByteString lines to Atoms
atIter :: Enumeratee [B.ByteString] [Atom] m a
atIter = I.mapChunks (catMaybes . map at)

otIter :: Enumeratee [B.ByteString] [Sheet] m a
otIter = I.mapChunks (catMaybes . map ot)

-- finally, combine multiple processors into one
-- if you have more than one processor, you can use zip3, zip4, etc.
procFile :: Iteratee [B.ByteString] m ([Atom],[Sheet])
procFile = I.zip (atIter =$ stream2list) (otIter =$ stream2list)

-- and run it on some data
runner :: FilePath -> IO ([Atom],[Sheet])
runner filename = do
  resultIter <- enumFile defaultBufSize filename $= enumLinesBS $ procFile
  run resultIter

这给您带来的一个好处是额外的可组合性。您可以根据需要创建转换器，并将它们与 zip 结合起来。如果你愿意，你甚至可以并行运行消费者(尽管只有当你在 IO monad 中工作，除非消费者做很多工作，否则可能不值得)通过更改为:

import Data.Iteratee.Parallel

parProcFile = I.zip (parI $ atIter =$ stream2list) (parI $ otIter =$ stream2list)

这样做的结果与单个 for 循环不同 - 这仍将执行数据的多次遍历。但是，遍历模式已经改变。这将一次加载一定数量的数据( defaultBufSize 字节)并多次遍历该 block ，并根据需要存储部分结果。在一个 block 被完全消耗后，下一个 block 被加载并且旧的 block 可以被垃圾收集。

希望这将证明差异:

Data.List.zip:
  x1 x2 x3 .. x_n
                   x1 x2 x3 .. x_n

Data.Iteratee.zip:
  x1 x2      x3 x4      x_n-1 x_n
       x1 x2      x3 x4           x_n-1 x_n

如果你做了足够多的工作，并行性是有意义的，这根本不是问题。由于内存局部性，性能比整个输入上的多次遍历要好得多，如 Data.List.zip将使。

美丽的解决方案

如果单遍历解决方案确实最有意义，您可能会对 Max Rabkin 的 Beautiful Folding 感兴趣。帖子和 Conal Elliott 的 followup work ( this too)。基本思想是您可以创建数据结构来表示折叠和 zipper ，将它们组合起来可以创建一个新的、组合的折叠/ zipper 功能，该功能只需要一次遍历。对于 Haskell 初学者来说，这可能有点高级，但是由于您正在考虑这个问题，您可能会发现它很有趣或有用。 Max 的帖子可能是最好的起点。