Scorrimento ricorsivo di una directory in Haskell

Question

Sto provando a fare una discesa ricorsiva di una struttura di directory usando Haskell. Mi piacerebbe solo recuperare le directory e i file secondari, se necessario (pigramente).

ho scritto il seguente codice, ma quando l'eseguo, la traccia mostra che tutte le directory sono visitati prima che il primo file:

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 

Come posso alternare l'elaborazione dei file con la discesa? Il problema è che l'azione files <- getRecursiveContents path viene eseguita prima del seguente forM_ in main?

Answer 1

Questo è esattamente il tipo di problema che le iterazioni/coroutine sono state progettate per risolvere.

È possibile farlo facilmente con pipes. L'unica modifica apportata al tuo getRecursiveContents era di renderlo un Producer di FilePath se a respond con il nome del file invece di restituirlo. Ciò consente a downstream di gestire immediatamente il nome del file anziché attendere il completamento di 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) 

Questo stampa ogni file immediatamente in quanto attraversa l'albero, e non richiede pigro IO. È anche molto facile cambiare le tue azioni con i nomi dei file, poiché tutto ciò che devi fare è cambiare il livello useD con la tua logica di gestione dei file.

Per ulteriori informazioni su pipes, consiglio vivamente di leggere Control.Proxy.Tutorial.

Answer 2

Grazie al commento di Niklas B., ecco la soluzione che ho:

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 

C'è un modo migliore?

Answer 3

L'utilizzo di IO pigro/unsafe... è non un buon modo per andare. Lazy IO provoca many problems, incluse le risorse non chiuse e l'esecuzione di azioni impure all'interno di codice puro. (Vedi anche The problem with lazy I/O su Haskell Wiki.)

Un modo sicuro è utilizzare una libreria iteratee/enumeratore. (Sostituire l'IO pigro problematico era la motivazione per lo sviluppo di questi concetti). Il tuo getRecursiveContents diventerebbe una fonte di dati (enumeratore AKA). E i dati saranno consumati da qualche iteratore. (Vedi anche Enumerator and iteratee su Haskell wiki.)

C'è a tutorial on the enumerator library che dà solo un esempio di traslazione e la directory di filtraggio albero, l'attuazione di un semplice trovare utilità. Implementa il metodo

enumDir :: FilePath -> Enumerator FilePath IO b 

che è fondamentalmente solo quello che ti serve. Credo che lo troverai interessante.

Inoltre c'è un bell'articolo che spiega iteratees in The Monad Reader, Issue 16: Iteratee: Insegnare un vecchio Fold New Tricks da John W. Lato, l'autore della biblioteca iteratee.

Oggi molte persone preferiscono le nuove librerie come pipes. Potresti essere interessato a un confronto: What are the pros and cons of Enumerators vs. Conduits vs. Pipes?.

Answer 4

Recentemente stavo guardando un problema molto simile, dove sto cercando di fare una ricerca un po 'complicata usando la monade IO, fermandomi dopo aver trovato il file che mi interessa. Mentre le soluzioni usano librerie come Enumerator, Conduit, ecc. Sembra essere il meglio che si possa fare nel momento in cui sono state pubblicate le risposte, ho appena appreso che IO è diventato un'istanza di Alternative nella libreria di base di GHC circa un anno fa, che apre nuove possibilità. Ecco il codice che ho scritto di provarlo:

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 

La funzione searchFiles fa una ricerca in profondità di un albero di directory, fermandosi quando trova quello che stai cercando, come determinato dalla funzione passata come primo argomento. La funzione è solo lì per mostrare come costruire una funzione adatta da utilizzare come primo argomento per searchFiles; nella vita reale probabilmente faresti qualcosa di più complicato.

La cosa interessante è che ora è possibile utilizzare empty per fare un IO calcolo "mollare" senza restituire un risultato, e si può calcoli concatenare con asum (che è solo foldr (<|>) empty) di continuare a provare calcoli fino a quando uno dei loro succede.

Trovo un po 'inquietante che la firma del tipo di un'azione IO non rifletta più il fatto che potrebbe deliberatamente non produrre un risultato, ma sicuramente semplifica il codice. In precedenza stavo cercando di usare tipi come IO (Maybe a), ma farlo rendeva molto difficile comporre azioni.

IMHO non c'è più molto motivo per utilizzare un tipo come IO (Maybe a), ma se è necessario interfacciarsi con il codice che utilizza un tipo simile, è facile convertire tra i due tipi. Per convertire IO a-IO (Maybe a), si può semplicemente utilizzare Control.Applicative.optional, e andando nella direzione opposta, si può usare qualcosa di simile:

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