Распечатка всего содержимого каталога по порядку в ширину приводит к низкой эффективности

Question

Я написал модуль Haskell, чтобы вывести все содержимое каталога в порядке убывания. Ниже приведен исходный код.

module DirElements (dirElem) where

import System.Directory (getDirectoryContents, doesDirectoryExist)
import System.FilePath ((</>))

dirElem :: FilePath -> IO [[FilePath]]
dirElem dirPath = iterateM (not.null) (concatMapM getDirectoryContents') [dirPath] >>= return.tail

getDirectoryContents' :: FilePath -> IO [FilePath]
getDirectoryContents' dirPath = do
  isDir <- do doesDirectoryExist dirPath
  if isDir then dirContent else return [] where
    dirContent = do
      contents <- getDirectoryContents dirPath
      return.(map (dirPath</>)).tail.tail $ contents

iterateM :: (Monad m) => (a -> Bool) -> (a -> m a) -> a -> m [a]
iterateM fb f x = do --Notice: Due to the the implementation of >>=, iterateM can't be writen like iterate which gives a infinite list and have type of iterateM :: (Monad m) => (a -> Bool) -> (a -> m a) -> a -> m [a]
  if fb x
    then do
      tail <- do {fx <- f x; iterateM fb f fx}
      return (x:tail)
    else return []

concatMapM :: Monad m => (a -> m[b]) -> [a] -> m[b]
concatMapM f list = mapM f list >>= return.concat

Он работает правильно, но при работе с большим каталогом он на некоторое время "приостанавливается" и выдает все результаты.

После исследования я обнаружил, что это тот же вопрос, sequence $ map return [1..]::[[Int]] посмотрите, почему функция последовательности Haskell не может быть ленивой или почему рекурсивные монадические функции не могут быть ленивыми

Answer 1

Я изменил старый ответ, с которым Даворак связался, чтобы использовать новый pipes библиотека.

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

import Control.Monad
import Control.Proxy
import Control.Proxy.Trans.Maybe
import Control.Proxy.Trans.State as S
import Data.Sequence hiding (filter)
import System.FilePath.Posix
import System.Directory

getUsefulContents :: FilePath -> IO [FilePath]
getUsefulContents path
  = fmap (filter (`notElem` [".", ".."])) $ getDirectoryContents path

traverseTree
    :: (Proxy p)
    => FilePath
    -> () -> Producer (MaybeP (StateP (Seq FilePath) p)) FilePath IO r
traverseTree path () = do
    liftP $ S.modify (|> path)
    forever $ do
        x <- liftP $ S.gets viewl
        case x of
            EmptyL    -> mzero
            file :< s -> do
                liftP $ S.put s
                respond file
                p <- lift $ doesDirectoryExist file
                when p $ do
                    names <- lift $ getUsefulContents file
                    let namesfull = map (file </>) names
                    liftP $ forM_ namesfull $ \name ->
                        S.modify (|> name)

Это определяет ленивого производителя файлов в ширину. Если вы подключите его к стадии печати, он будет распечатывать файлы по мере прохождения дерева:

main = runProxy $ evalStateK empty $ runMaybeK $
    traverseTree "/tmp" >-> putStrLnD

Лень означает, что если вам требуется только 3 файла, он будет проходить по дереву столько, сколько необходимо для генерации трех файлов, тогда он остановится:

    main = runProxy $ evalStateK empty $ runMaybeK $
        traverseTree "/tmp" >-> takeB_ 3 >-> putStrLnD

Если вы хотите узнать больше о pipes библиотека, тогда я рекомендую вам прочитать учебник.

Answer 2

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

• Потоковое рекурсивное снижение директории в Haskell
• Устаревшее решение для конвейеров устарело и не повторяется, как и решение, сначала обход дерева каталогов в ширину не ленив

Я уже видел решения Conduit и несколько элегантных монадических решений, но сейчас я их не нахожу.

Answer 3

Прежде всего, это не связано со строгостью. Как и многие монады, IO на самом деле не строг в своих монадических операциях. Это связано с ленивым или нетерпеливым вводом / выводом.

Проблема в том, что вы сначала выполняете обход каталога, а затем обрабатываете результат. Вы можете улучшить это, используя сопрограммы для их чередования. Один простой способ - заставить обход каталога принимать обратный вызов в качестве аргумента:

getDirectoryContents' :: (MonadIO m) => (FilePath -> m a) -> FilePath -> m ()
getDirectoryContents' k fp = {- ... -}

Это самое простое и наименее гибкое решение. Более гибким решением является реализация сопрограмм. Вы можете либо свернуть свою собственную монаду сопрограмм, используя свободную, монад-сопрограмму или операционную, либо вы можете использовать одну из многих потоковых абстракций, таких как канал, перечислитель или каналы, причем последняя является моей личной рекомендацией для простых случаев, подобных этой.

Answer 4

Каждый говорит вам использовать итерации, каналы или тому подобное, которые в настоящее время популярны. Но есть еще один классический способ сделать это! Просто используйте unsafeInterleaveIO от System.IO.Unsafe, Вся эта функция типа IO a -> IO a действительно, изменяет действие ввода-вывода так, чтобы оно фактически выполняло ввод-вывод только тогда, когда требуется значение thunk, а это именно то, о чем вы просили. Вы можете использовать это, чтобы написать iterateM с вашей желаемой семантикой тривиально.

Примеры как это где unsafeInterleaveIO светит.

Однако, я уверен, вы отметили "небезопасный" в названии - есть и другие примеры, где вы хотите получить прямой контроль над файловыми дескрипторами и использованием ресурсов или тому подобное, где unsafeInterleaveIO действительно будет плохой новостью, и потенциально может даже привести к нарушению ссылочной прозрачности.

(см. этот ответ для дальнейшего обсуждения: когда unsafeInterleaveIO небезопасен?)

Но опять же, в таком случае, я думаю, unsafeInterleaveIO это очевидный, правильный и простой результат.