Subscribed unsubscribe Subscribe Subscribe

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

Haskell

Haskell 界隈では、生産者/消費者のモデルとして、Enumerator/Iteratee (EI)が流行っている。しかし、EI を理解するのは難しい。
そこでこの記事では、もっと簡単な生産者/消費者モデルを示す。EI は Enumerator が Iteratee に push する push 型だが、紹介するモデルは pull 型である。

ファーストクラスIOと部品プログラミング - あどけない話

この記事でkazuさんが紹介している、I/Oのリストを使ったディレクトリ走査関数について取り上げます。

アジェンダは次の通りです。

  • (期待している)遅延I/Oはディレクトリを潜る方向の走査でしか起きていない
  • unfoldrMの使い道
  • iteratee I/Oが必要なわけにリソース制御も入れるのがよいのではないか

コードを整理する

まずはコードを少し整理します。先の記事ではContentsという型を使って、ディレクトリ走査のアクションを表現していました。

data Contents = File FilePath | Dir [IO Contents]

ポイントは構成子Dirです。Dirが表現しているのは「あとでこのディレクトリも走査してね」という予約(IOアクション)です。アクションを実行せずに値として持っておく(予約する)ことで、遅延I/Oを実現しようとしています。

しかしよくよく考えると、走査関数がディレクトリを見つけた時にするべき予約は、[IO Contents]よりIO [Contents]の方が正確に表現できます。言い換えると、「このディレクトリ以下の内容のリストを返すアクション」を予約するのです。

data Contents = File FilePath | Dir (IO [Contents])

書き換えたContentsは、まさにディレクトリエントリを表しています。名前もDEntryに書き換えます。

data DEntry = File FilePath | Dir (IO [DEntry])

走査関数の方も型をあわせます。

data DEntry = File FilePath | Dir (IO [DEntry])

getRecursiveContents :: FilePath -> IO [DEntry]
getRecursiveContents dir = map (dir </>) <$> getValidContents dir >>= mapM toDEntry
  where toDEntry :: FilePath -> IO DEntry
        toDEntry path = do
          isDir <- isSearchableDir path
          if isDir
            then return $ Dir $ getRecursiveContents path
            else File <$> pure path

grep :: String -> [DEntry] -> IO ()
grep pattern = mapM_ go
  where go (File f)
          | pattern `isInfixOf` f = putStrLn f
          | otherwise             = return ()
        go (Dir mdentries)        = mdentries >>= grep pattern

find :: FilePath -> String -> IO ()
find dir pattern = getRecursiveContents dir >>= grep pattern

これでコードがすっきりしました。以前お話ししたときはFilePathからDEntryの生成がunfoldrMになるはずという話でしたが、このコード上では出てきません。これについては後で触れます。

getDirectoryContentsは正格

ここで注意すべきポイントは、kazuさんのどの例でも上で再定義したfindでも、(期待している)遅延I/O的な動作は、ディレクトリ階層を潜る方向の走査だけであるということです。同一ディレクトリ内のファイル一覧を生成する部分は依然としてモノリシックなI/Oアクションになっています。何故でしょうか?

それはgetDirectoryContentsが正格なI/Oをするからです。getDirectoryContentsのコードを見てみましょう。

getDirectoryContents :: FilePath -> IO [FilePath]
getDirectoryContents path =
  modifyIOError ((`ioeSetFileName` path) . 
                 (`ioeSetLocation` "getDirectoryContents")) $ do
#ifndef mingw32_HOST_OS
    bracket
      (Posix.openDirStream path)
      Posix.closeDirStream
      loop
 where
  loop dirp = do
     e <- Posix.readDirStream dirp
     if null e then return [] else do
       es <- loop dirp
       return (e:es)

IOモナドのbindは正格であることを思い出してください。補助関数loopの再帰呼び出しでディレクトリストリームから取り出されたディレクトリエントリのリストesは必要になったときに生成されるのではなく、すべて生成されてからreturn (e:es)されます。

この走査を遅延I/OさせるにはunsafeInterleaveIOの出番です。

getDirectoryContentsとunfoldrM

実はこのgetDirectoryContentsこそがunfoldrMの使いどころです。unfoldrMとunsafeInterleaveIOでべたっと書くのも微妙なので、ここではより一般化したunsafeUnfoldrIOを定義して、それを使ってunsafeGetDirectoryContentsを定義します。

-- monadicなunfoldr。ここでは使ってない。
unfoldrM :: Monad m => (b -> m (Maybe (a, b))) -> b -> m [a]
unfoldrM f z = f z >>= step
  where step (Just (a, b')) = liftM (a:) $ unfoldrM f b'
        step Nothing        = return []

-- IOの場合はbindが正格なので、遅延I/OするにはunsafeInterleaveIOが必要
unsafeUnfoldrIO :: (b -> IO (Maybe (a, b))) -> b -> IO [a]
unsafeUnfoldrIO f z = f z >>= step
  where step (Just (a, b')) = liftM (a:) $ unsafeInterleaveIO $ unsafeUnfoldrIO f b'
        step Nothing        = return []

unsafeGetDirectoryContents :: FilePath -> IO [FilePath]
unsafeGetDirectoryContents path = openDirStream path >>= unsafeUnfoldrIO phi
  where phi dirp = do
          e <- readDirStream dirp
          if null e
            then return Nothing
            else return $ Just (e, dirp)

この例のように何か種となる値(たとえばHandleとか)からリストを生成するのはunfold(anamorphism)の役割です。明示的な再帰はconsidered harmfulHaskell界で、たいていのI/Oループがべったり書かれているのは残念なので、こういうよく使いそうな高階関数Haskell Platformに入るといいなあと思います。

注目すべきポイントはgetDirectoryContentsではbracketを使ってDirStreamを閉じる処理をしていましたが、今回はしていないところです。これが何故かはbracketを書いて実行してみるとわかります。

unsafeGetDirectoryContents' :: FilePath -> IO [FilePath]
unsafeGetDirectoryContents' path =
  bracket (openDirStream path) closeDirStream (unsafeUnfoldrIO phi)
  where phi dirp = do
          e <- readDirStream dirp
          if null e
            then return Nothing
            else return $ Just (e, dirp)

実行するとBad file descriptorで例外が上がります。

Prelude> unsafeGetDirectoryContents' "."
["."*** Exception: readDirStream: invalid argument (Bad file descriptor)

これは当然でbracket自体は通常のIOモナドで書かれているので、openDirStreamして遅延読み込みし始めたところですぐにcloseDirStreamされてしまうためです。unsafeInterleaveIOで遅延I/Oしている場合は、適切なタイミングでリソースを解放できるように慎重に検討しなければなりません。

Iteratee I/Oが必要なわけ

というわけで、kazuさんが挙げた例から

  • grepがモノリシックでいけてない
  • 遅延I/Oはリソース制御が難しい

という問題点を挙げて、iterateeを導入するという流れがいいかなあと思いました。

おまけ: sheのバナナ括弧を使おう

Applicativeの元論文を書いたCornor McBrideさんがthe Strathclyde Haskell Enhancement (she)http://hackage.haskell.org/package/she)というプリプロセッサを公開していて、これを使うと論文中のバナナ括弧が使えるとのことなので使ってみました。

使い方は簡単で、(| liftしたい表現 |)とバナナ括弧で括るだけです。上で書いたunsafeUnfoldrIOはこうなります。

unsafeUnfoldrIO :: (b -> IO (Maybe (a, b))) -> b -> IO [a]
unsafeUnfoldrIO f z = f z >>= step
  where step (Just (a, b')) = (| pure a : unsafeInterleaveIO (unsafeUnfoldrIO f b') |)
        step Nothing        = (| [] |)

いいね!