Потоковое рекурсивное снижение директории в 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

Как я могу чередовать обработку файла со спуском? Проблема в том, что files <- getRecursiveContents path действие выполняется до следующего forM_ в main?

Answer 1

Это именно та проблема, для решения которой были разработаны итерации / сопрограммы.

Вы можете легко сделать это с pipes, Единственное изменение, которое я сделал в вашем getRecursiveContents должен был сделать это Producer из FilePathс и к 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

Используя ленивый IO / unsafe... это не хороший путь. Ленивый ввод-вывод вызывает много проблем, включая незакрытые ресурсы и выполнение нечистых действий в чистом коде. (См. Также "Проблема с ленивым вводом / выводом" на Haskell Wiki.)

Безопасным способом является использование некоторой библиотеки iteratee / enumerator. (Замена проблемных ленивых IO была мотивом для разработки этих концепций.) Ваш getRecursiveContents станет источником данных (перечислитель АКА). И данные будут использованы каким-то итератором. (См. Также Enumerator и iteratee на вики Haskell.)

В библиотеке перечислителя есть учебное пособие, в котором приведен пример обхода и фильтрации дерева каталогов с помощью простой утилиты поиска. Реализует метод

enumDir :: FilePath -> Enumerator FilePath IO b

что в основном то, что вам нужно. Я верю, что вы найдете это интересным.

Также есть хорошая статья, объясняющая итерируемых в The Monad Reader, выпуск 16: Итерируемый: обучение старому складыванию новых трюков, автор Джон У. Лато, автор библиотеки iteratee.

Сегодня многие люди предпочитают новые библиотеки, такие как трубы. Возможно, вас заинтересует сравнение: каковы плюсы и минусы счетчиков против трубопроводов и труб?,

Answer 3

Благодаря комментарию Никласа Б. вот решение, которое у меня есть:

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 4

Недавно я смотрел на очень похожую проблему, где я пытаюсь сделать несколько сложный поиск, используя IO монада, остановка после того, как я нахожу интересующий меня файл. Хотя решения, использующие библиотеки, такие как Enumerator, Conduit и т. д., кажутся лучшими, что вы могли бы сделать на момент публикации этих ответов, я только что узнал IO стал примером Alternative около года назад в базовой библиотеке GHC, что открывает новые возможности. Вот код, который я написал, чтобы попробовать это:

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