ファーストクラスIOと部品プログラミング

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 のようにもっと抽象化できるか考えることである。

あどけない話

Internet technologies