Haskell, монады, память, и все-все-все
Форум — Development
Есть задача - пройтись по текстовому файлу и найти максимальное число одинаковых последовательно идущих строчек. Задача весьма синтетическая, просто надо продемонстрировать, что
- Потоково обрабатывается некий объем данных;
- Есть состояние - надо помнить предыдущую строку в файле при обращении к следующей.
Решение в лоб на IORef-ах (m1.hs):
module Main where
import Data.IORef
import Control.Monad (forM)
main :: IO ()
main = do
input <- getContents
lastLine <- newIORef (Nothing)
counter <- newIORef (0)
result <- newIORef (0)
let incr = modifyIORef counter (\x -> x `seq` x+1)
reset s = do c <- readIORef counter
r <- readIORef result
writeIORef result (max c r)
writeIORef lastLine (Just s)
writeIORef counter 1
forM (lines input) $ \line -> do
ml <- readIORef lastLine
case ml of
(Just s) -> if s == line then incr else reset line
Nothing -> reset line
r <- readIORef result
putStrLn $ "Largest subsequence of equal lines: " ++ show r
Более модное решение с трансформером StateT (m2.hs):
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
module Main where
import Control.Monad (forM)
import Control.Monad.State.Strict
data AppContext = AppContext { ctxLastLine :: Maybe String
, ctxCounter :: Integer
, ctxResult :: Integer
}
initialContext :: AppContext
initialContext = AppContext { ctxLastLine = Nothing
, ctxCounter = 0
, ctxResult = 0
}
newtype App a = App (StateT AppContext IO a)
deriving (Monad, MonadIO, MonadState AppContext)
runApp (App app) = execStateT app
incr :: App ()
incr = do
cnt <- gets ctxCounter
modify $ \s -> s { ctxCounter = cnt+1 }
reset :: String -> App ()
reset l = do
cnt <- gets ctxCounter
res <- gets ctxResult
modify $ \s -> s { ctxLastLine = Just l
, ctxCounter = 1
, ctxResult = max res cnt
}
processLine :: String -> App ()
processLine line = do
ll <- gets ctxLastLine
case ll of
(Just s) -> if line == s then incr else reset line
Nothing -> reset line
main :: IO ()
main = do
input <- getContents
s <- runApp (forM (lines input) processLine) initialContext
putStrLn $ "Largest subsequence of equal lines: " ++ show (ctxResult s)
Интересно, как поведут себя оба варианта на обработке, скажем, «Улисс» Джойса (txt, 1.6 MB):
[dmatveev@localhost memq]$ ghc --make m1.hs -rtsopts -prof
[1 of 1] Compiling Main ( m1.hs, m1.o )
Linking m1 ...
[dmatveev@localhost memq]$ ghc --make m2.hs -rtsopts -prof
[1 of 1] Compiling Main ( m2.hs, m2.o )
Linking m2 ...
[dmatveev@localhost memq]$ du -sh ulysses.txt
1.6M ulysses.txt
[dmatveev@localhost memq]$ wc -l ulysses.txt
33055 ulysses.txt
[dmatveev@localhost memq]$ time cat ulysses.txt | ./m1 +RTS -hd -i0.001
Largest subsequence of equal lines: 5
real 0m1.599s
user 0m1.577s
sys 0m0.021s
[dmatveev@localhost memq]$ time cat ulysses.txt | ./m2 +RTS -hd -i0.001
Largest subsequence of equal lines: 5
real 0m19.360s
user 0m19.123s
sys 0m0.091s
ШОК! Посмотрим, что там с памятью:
[dmatveev@localhost memq]$ hp2ps -e8in -c m1.hp
[dmatveev@localhost memq]$ hp2ps -e8in -c m2.hp
Очевидно, что во втором примере что-то течёт, а я что-то глобально упустил.
Вопросы:
- ЧЯДНТ?
- Как быть?
- Как правильно готовить монадические ивентлупы с изменяемым состоянием?
З.Ы. Да, я знаю, что на awk это решается проще и быстрее, суть-то не в этом, а в вопросе №3. Извините за неровный почерк.
