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

Затем я бы отобразил каждую из этих функций по всему списку строк в файле, чтобы получить полный список атомов и листов:

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 и, вероятно, не стоит, если потребители не выполняют много работы), изменив это на:

import Data.Iteratee.Parallel

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

Результат этого не совпадает с одним циклом for - он по-прежнему будет выполнять несколько обходов данных. Однако картина обхода изменилась. Это позволит загружать определенное количество данных за один раз (defaultBufSize байт) и проходить через этот фрагмент несколько раз, сохраняя при необходимости частичные результаты. После того, как чанк полностью израсходован, загружается следующий чанк, а старый можно собирать мусором.

Надеюсь, это продемонстрирует разницу:

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.

Прекрасное решение

Если решение с одним обходом действительно имеет смысл, вас могут заинтересовать пост Макса Рабкина Beautiful Folding и сообщение Конала Эллиота продолжение работа ( это тоже ). Основная идея заключается в том, что вы можете создавать структуры данных, представляющие сгибы и почтовые индексы, и их объединение позволяет создать новую комбинированную функцию сгиба / почтового индекса, которая требует только одного обхода. Это может быть немного продвинутым для новичка в Haskell, но, так как вы думаете о проблеме, вы можете найти ее интересной или полезной. Пост Макса, вероятно, лучшая отправная точка.

Answer 2

Я показываю решение для двух типов линий, но оно легко расширяется до пяти типов линий с использованием пяти-кортежа вместо двух-кортежа.

import Data.Monoid

eachLine :: B.ByteString -> ([Atom], [Sheet])
eachLine bs | isAnAtom bs = ([ {- calculate an Atom -} ], [])
            | isASheet bs = ([], [ {- calculate a Sheet -} ])
            | otherwise = error "eachLine"

allLines :: [B.ByteString] -> ([Atom], [Sheet])
allLines bss = mconcat (map eachLine bss)

Волшебство осуществляетсяmconcat из Data.Monoid (входит в состав GHC).

(В отношении стиля: лично я определил бы тип Line, функцию parseLine :: B.ByteString -> Line и запись eachLine bs = case parseLine bs of .... Но это второстепенный вопрос.)

Answer 3

Хорошей идеей будет ввести новый ADT, например, «Резюме» вместо кортежей. Затем, поскольку вы хотите накапливать значения Summary, вы пришли к нему как к Data.Monoid. Затем вы классифицируете каждую из ваших строк с помощью функций классификатора (например, isAtom, isSheet и т. Д.) И объединяете их вместе, используя функцию mconcat Monoid (как предложено @ dave4420).

Вот код (он использует String вместо ByteString, но его довольно легко изменить):

module Classifier where

import Data.List
import Data.Monoid

data Summary = Summary
  { atoms :: [String]
  , sheets :: [String]
  , digits :: [String]
  } deriving (Show)

instance Monoid Summary where
  mempty = Summary [] [] []
  Summary as1 ss1 ds1 `mappend` Summary as2 ss2 ds2 =
    Summary (as1 `mappend` as2)
            (ss1 `mappend` ss2)
            (ds1 `mappend` ds2)

classify :: [String] -> Summary
classify = mconcat  . map classifyLine

classifyLine :: String -> Summary
classifyLine line
  | isAtom line  = Summary [line] [] [] -- or "mempty { atoms = [line] }"
  | isSheet line = Summary [] [line] []
  | isDigit line = Summary [] [] [line]
  | otherwise    = mempty -- or "error" if you need this  

isAtom, isSheet, isDigit :: String -> Bool
isAtom = isPrefixOf "atom"
isSheet = isPrefixOf "sheet"
isDigit = isPrefixOf "digits"

input :: [String]
input = ["atom1", "sheet1", "sheet2", "digits1"]

test :: Summary
test = classify input

Answer 4

Если у вас есть только 2 альтернативы, использование Either может быть хорошей идеей. В этом случае объедините ваши функции, отобразите список и используйте левые и права для получения результатов:

import Data.Either

-- first sample function, returning String
f1 x = show $ x `div` 2

-- second sample function, returning Int
f2 x = 3*x+1

-- combined function returning Either String Int
hotpo x = if even x then Left (f1 x) else Right (f2 x)

xs = map hotpo [1..10] 
-- [Right 4,Left "1",Right 10,Left "2",Right 16,Left "3",Right 22,Left "4",Right 28,Left "5"]

lefts xs 
-- ["1","2","3","4","5"]

rights xs
-- [4,10,16,22,28]