subfindの実装（Parallel and Concurrent Programming in Haskell Chapter 13の一部)

haskell

parallel and concurrentの13章でとてもわかりづらいところがあったのでメモ

英語の原文はこちらのページで読める
http://chimera.labs.oreilly.com/books/1230000000929/ch13.html#conc-par_00000029


今回調べたのは以下のコード(本から引用)

subfind :: String -> FilePath
        -> ([Async (Maybe FilePath)] -> IO (Maybe FilePath))
        ->  [Async (Maybe FilePath)] -> IO (Maybe FilePath)

subfind s p inner asyncs = do
  isdir <- doesDirectoryExist p
  if not isdir
     then inner asyncs
     else withAsync (find s p) $ \a -> inner (a:asyncs)

find :: String -> FilePath -> IO (Maybe FilePath)
find s d = do
  fs <- getDirectoryContents d
  let fs' = sort $ filter (`notElem` [".",".."]) fs
  if any (== s) fs'
     then return (Just (d </> s))
     else do
       let ps = map (d </>) fs'         
       foldr (subfind s) dowait ps []   -- (*)
 where
   dowait as = loop (reverse as)        

   loop [] = return Nothing
   loop (a:as) = do                     
      r <- wait a
      case r of
        Nothing -> loop as
        Just a  -> return (Just a)

特にわかりづらいのが(*)の部分。

一見すると引数の数が合わないが、関数の結合力が強いことから以下の形で結合して処理される。

foldr (subfind s) dowait ps $ []

foldrの型は以下。

(a -> b -> b) -> b -> [a] -> b

これを踏まえるとa, bの型は以下のようになっていると考えることができる。

  • a => FilaPath
  • b => [Async (Maybe FilePath)] -> IO (Maybe FilePath)

foldrを簡単な式で考えてみる。

foldr (+) 0 [1,2,3]
はこのように置き換えて考えられる
1 : (2 : (3 : []))
=>
1 + (2 + (3 + 0)

なので同様のことを今回の式に当てはめると以下のようになる。
ps = [p1, p2, p3]とすると

p1 : (p2 : (p3 : []))
=>
p1 `subfind s` (p2 `subfind s` (p3 `subfind s` dowait))  -- (**)

つまりfoldrした結果としてdowaitと同じ型でいくつもsubfindを内包した式が出てくる。

subfind p3 dowait :: [Async (Maybe FilePath)] -> IO (Maybe FilePath)

そして(*)の最後の部分で空のリストに適用してIO (Maybe FilePath)が返ってくる。のリストが適用されたときの処理を考えてみる。

foldrによって畳み込まれた結果の関数にが適用される。つまり(**)の式にが適用される。subfindのinnerとしてsubfindが２つ含まれた式が渡される。

p1がディレクトリであれば次のsubfindが実行され, そうでなければwithAsyncでfind s p1を実行して生成されたAsyncをに加えた上で次のsubfindを適用する。Asyncの生成＝スレッドの生成なのでfind s pの処理は別のスレッドで開始されることになる。

同じように処理していくとディレクトリ内のすべてのエントリについてsubfindが実行され、下にあるディレクトリの検索のためにいくつか新しいスレッドでfind s pが実行される。最終的にinnerがdowait、[Async (Maybe FilePath)]がそれまで生成したAsyncをすべて含んだリストとしてsubfindが実行される。

dowaitはloop (reverse ps)であり、loop内でwaitを実行して結果を取り出している。asyncを格納する際はリストの先頭に順に入れていったのだからp3,p2,p1のように並んでいる。よってdowaitは上の例だとp1から順に結果が取り出されることになる。