Haskell中目錄的流式遞歸下降

Question

我想用Haskell做一個目錄結構的遞歸下降。我只想根據需要檢索子目錄和文件（懶洋洋地）。

我寫了下面的代碼，但是當我運行它，跟蹤顯示所有目錄的第一個文件之前訪問：

module Main where 

import Control.Monad (forM, forM_, liftM) 
import Debug.Trace (trace) 
import System.Directory (doesDirectoryExist, getDirectoryContents) 
import System.Environment (getArgs) 
import System.FilePath ((</>)) 

-- From Real World Haskell, p. 214 
getRecursiveContents :: FilePath -> IO [FilePath] 
getRecursiveContents topPath = do 
    names <- getDirectoryContents topPath 
    let 
    properNames = 
     filter (`notElem` [".", ".."]) $ 
     trace ("Processing " ++ topPath) names 
    paths <- forM properNames $ \name -> do 
    let path = topPath </> name 
    isDirectory <- doesDirectoryExist path 
    if isDirectory 
     then getRecursiveContents path 
     else return [path] 
    return (concat paths) 

main :: IO() 
main = do 
    [path] <- getArgs 
    files <- getRecursiveContents path 
    forM_ files $ \file -> putStrLn $ "Found file " ++ file 

我怎樣才能交錯文件處理與血統？動作在main的以下forM_之前執行的問題？

Answer 1

這正是iteratees/coroutines設計要解決的問題。

你可以用pipes輕鬆做到這一點。我對你的getRecursiveContents所作的唯一更改是使其Producer的FilePath s和respond與文件名而不是返回它。這讓下游立即處理文件名，而不是等待getRecursiveContents完成。

module Main where 

import Control.Monad (forM_, liftM) 
import Control.Proxy 
import System.Directory (doesDirectoryExist, getDirectoryContents) 
import System.Environment (getArgs) 
import System.FilePath ((</>)) 

getRecursiveContents :: (Proxy p) => FilePath ->() -> Producer p FilePath IO() 
getRecursiveContents topPath() = runIdentityP $ do 
    names <- lift $ getDirectoryContents topPath 
    let properNames = filter (`notElem` [".", ".."]) names 
    forM_ properNames $ \name -> do 
    let path = topPath </> name 
    isDirectory <- lift $ doesDirectoryExist path 
    if isDirectory 
     then getRecursiveContents path() 
     else respond path 

main :: IO() 
main = do 
    [path] <- getArgs 
    runProxy $ 
      getRecursiveContents path 
     >-> useD (\file -> putStrLn $ "Found file " ++ file) 

這立即打印出每個文件在其穿過樹，它不需要懶惰IO。使用文件名更改你的操作也很容易，因爲你所要做的就是用你的實際文件處理邏輯來切換useD階段。

要了解有關pipes的更多信息，我強烈建議您閱讀Control.Proxy.Tutorial。

Answer 2

多虧了由Niklas B.註釋，這裏是我的解決方案：

module Main where 

import Control.Monad (forM, forM_, liftM) 
import Debug.Trace (trace) 
import System.Directory (doesDirectoryExist, getDirectoryContents) 
import System.Environment (getArgs) 
import System.FilePath ((</>)) 
import System.IO.Unsafe (unsafeInterleaveIO) 

-- From Real World Haskell, p. 214 
getRecursiveContents :: FilePath -> IO [FilePath] 
getRecursiveContents topPath = do 
    names <- unsafeInterleaveIO $ getDirectoryContents topPath 
    let 
    properNames = 
     filter (`notElem` [".", ".."]) $ 
     trace ("Processing " ++ topPath) names 
    paths <- forM properNames $ \name -> do 
    let path = topPath </> name 
    isDirectory <- doesDirectoryExist path 
    if isDirectory 
     then unsafeInterleaveIO $ getRecursiveContents path 
     else return [path] 
    return (concat paths) 

main :: IO() 
main = do 
    [path] <- getArgs 
    files <- unsafeInterleaveIO $ getRecursiveContents path 
    forM_ files $ \file -> putStrLn $ "Found file " ++ file 

有沒有更好的辦法？

Answer 3

使用懶惰IO/unsafe...是不是一個很好的方法去。惰性IO會導致many problems，包括未關閉的資源並在純代碼中執行不純操作。 （另請參見Haskell Wiki上的The problem with lazy I/O）。

安全的方法是使用一些iteratee/enumerator庫。 （替換有問題的惰性IO是開發這些概念的動機。）您的getRecursiveContents將成爲數據源（AKA枚舉器）。數據將被某個迭代器使用。 （另見哈斯克爾維基Enumerator and iteratee。）

有a tutorial on the enumerator library只是給遍歷和過濾目錄樹的例子，實現簡單的找到效用。它實現方法

enumDir :: FilePath -> Enumerator FilePath IO b 

這基本上就是你所需要的。我相信你會覺得很有趣。

也有一個很好的文章，解釋在The Monad Reader, Issue 16 iteratees：Iteratee：由約翰·W·拉託的iteratee庫的作者教老折新的把戲。

今天很多人喜歡較新的庫，如pipes。您可能對比較感興趣：What are the pros and cons of Enumerators vs. Conduits vs. Pipes?。

Answer 4

我最近在尋找一個非常類似的問題，我試圖用IO monad做一個有點複雜的搜索，在找到我感興趣的文件後停下來。雖然使用像Enumerator這樣的庫的解決方案，在這些答案發布的時候，管道等似乎是你可以做的最好的，我剛剛在大約一年前瞭解到IO成爲GHC基礎庫中的Alternative的一個實例，這開闢了一些新的可能性。下面是我寫嘗試一下代碼：

import Control.Applicative (empty) 
import Data.Foldable (asum) 
import Data.List (isSuffixOf) 
import System.Directory (doesDirectoryExist, listDirectory) 
import System.FilePath ((</>)) 

searchFiles :: (FilePath -> IO a) -> FilePath -> IO a 
searchFiles f fp = do 
    isDir <- doesDirectoryExist fp 
    if isDir 
     then do 
      entries <- listDirectory fp 
      asum $ map (searchFiles f . (fp </>)) entries 
     else f fp 

matchFile :: String -> FilePath -> IO() 
matchFile name fp 
    | name `isSuffixOf` fp = putStrLn $ "Found " ++ fp 
    | otherwise = empty 

的searchFiles功能做了深度優先搜索的目錄樹，停止當它發現你正在尋找什麼，由作爲傳遞函數確定第一個論點。 matchFile函數就是爲了展示如何構造一個合適的函數作爲searchFiles的第一個參數;在現實生活中，你可能會做更復雜的事情。

這裏有趣的是，現在你可以使用empty作出IO計算「放棄」不返回的結果，你可以鏈的計算與asum在一起（這只是foldr (<|>) empty）繼續嘗試計算，直到一個他們成功了。

我發現IO動作的類型簽名不再反映它可能故意不產生結果的事實，但它確實簡化了代碼，這有點令人不安。我之前嘗試使用像IO (Maybe a)這樣的類型，但這樣做使得編寫操作非常困難。恕我直言，沒有太多的理由使用像IO (Maybe a)這樣的類型，但是如果你需要與使用這種類型的代碼進行交互，很容易在兩種類型之間進行轉換。要轉換IO a到IO (Maybe a)，你可以使用Control.Applicative.optional，和走另一條路，你可以使用這樣的事情：

maybeEmpty :: IO (Maybe a) -> IO a 
maybeEmpty m = m >>= maybe empty pure