Haskell 界隈では、生産者/消費者のモデルとして、Enumerator/Iteratee (EI)が流行っている。しかし、EI を理解するのは難しい。
そこでこの記事では、もっと簡単な生産者/消費者モデルを示す。EI は Enumerator が Iteratee に push する push 型だが、紹介するモデルは pull 型である。
僕が書いたEI のチュートリアル「A tutorial on the enumerator library」から例を取る。すなわち、UNIX の find コマンドを実装する。
命令型 find
命令型プログラミング言語から Haskell にやってきた初心者プログラマーなら、こんなコードを書くだろう。
import Control.Monad import Control.Applicative import Data.List import System.Directory import System.FilePath getValidContents :: FilePath -> IO [String] getValidContents path = filter (`notElem` [".", "..", ".git", ".svn"]) <$> getDirectoryContents path isSearchableDir :: FilePath -> IO Bool isSearchableDir dir = (&&) <$> doesDirectoryExist dir <*> (searchable <$> getPermissions dir) findImperative :: FilePath -> String -> IO () findImperative dir pattern = do cnts <- map (dir </>) <$> getValidContents dir forM_ cnts $ \path -> do when (pattern `isInfixOf` path) $ putStrLn path isDirectory <- isSearchableDir path when isDirectory $ findImperative path pattern
このコードもの問題は、findImperative が仕事をし過ぎていることである。関数プログラマーなら、この一枚岩な関数を分割し、合成することで find を実装したい。
期待外れの関数型find
初心者関数プログラマーなら、以下のように生産者(getRecursiveContetns)と消費者(grep)をそれぞれ別に実装し、>>= で合成するだろう。
getRecursiveContents :: FilePath -> IO [FilePath] getRecursiveContents dir = do cnts <- map (dir </>) <$> getValidContents dir cnts' <- forM cnts $ \path -> do isDirectory <- isSearchableDir path if isDirectory then getRecursiveContents path else return [path] return . concat $ cnts' grep :: String -> [FilePath] -> [FilePath] grep pattern = filter (pattern `isInfixOf`) findFunctional :: FilePath -> String -> IO () findFunctional dir pattern = grep pattern <$> getRecursiveContents dir >>= mapM_ putStrLn
残念ながら、このコードは期待通りには動かない。IO [a] という型は、(getContetents とその仲間たちを除いて)正格に動く。リストは遅延しない。つまり、一度に [a] の全体が帰ってくると考えてよい。
よって、findFunctional を走らせると利用者をしばらく待たせ、すべての結果を得られた時点で、一度に表示する。我々が欲しいのは、ファイルを見つけた時点で表示してくれるプログラムである。
ファーストクラスIOを利用した関数型find
上記の問題を解決するために、IO がファーストクラスであることを利用する。IO a は、命令ではなく、命令書であることを思い出そう。命令書は、値、つまりファーストクラスである。
以下のコードのポイントは、Contents というデータである。定義を見れば、IO を値として扱っていることが分かるだろう。
data Contents = File FilePath | Dir [IO Contents] getRecursiveContents :: FilePath -> IO [IO Contents] getRecursiveContents dir = do cnts <- map (dir </>) <$> getValidContents dir return $ map toDir cnts where toDir :: FilePath -> IO Contents toDir path = do isDirectory <- isSearchableDir path if isDirectory then Dir <$> getRecursiveContents path else return $ File path grep :: String -> [IO Contents] -> IO () grep _ [] = return () grep pattern (act:acts) = do cnt <- act case cnt of File file | pattern `isInfixOf` file -> putStrLn file | otherwise -> return () Dir dir -> grep pattern dir grep pattern acts
このプログラムは期待通りに動く。どう動いているのか分からない人のために、図示してみる。ディレクトリの構造が、
.
file01
dir02
file11
dir12
file31
file03
dir04
file21
file22
であるとすると、以下のように動いている。
getR "." >>= grep file01 getR "diir02" >>= grep file11 getR "dir12" >>= grep file31 file03 getR "dir04" >>= grep file21 file22
高階関数にしてみる
N 個表示したら、終了するようにするために、消費者側を以下のように変更してみる。
type Action = FilePath -> IO Bool takeM :: Int -> Action -> [IO Contents] -> IO () takeM lim act as = takeM' 0 lim act as >> return () takeM' :: Int -> Int -> Action -> [IO Contents] -> IO Int takeM' n _ _ [] = return n takeM' n lim act (order:orders) = do cnt <- order m <- case cnt of File file -> do took <- act file if took then return (n + 1) else return n Dir dir -> takeM' n lim act dir if m == lim then return m else takeM' m lim act orders grep :: String -> Action grep patt file | patt `isInfixOf` file = putStrLn file >> return True | otherwise = return False find :: FilePath -> String -> Int -> IO () find dir pattern n = getRecursiveContents dir >>= takeM n (grep pattern)
まとめと今後の課題
EI は柔軟であるが、理解は容易ではない。
一方、このモデルは、理解が簡単であるが、消費者はやはり一枚岩として動くので、柔軟性に欠ける。間にもう一人の登場人物を挟んだりはできない。今後の課題は、このモデルを unfold/fold のようにもっと抽象化できるか考えることである。