logo标签列表

按广度优先顺序列出目录下的所有内容会导致效率低下。

performanceloopshaskelliolazy-evaluation
4

我编写了一个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 的 sequence 函数不能是惰性的或者递归单子函数不能是惰性的

4个回答
12
10

首先，这与严格性无关。像许多单子一样，IO在其单子操作中实际上是非严格的。这与惰性vs.急切I/O有关。

问题在于您首先执行目录遍历，然后再处理结果。您可以通过使用协程将它们交错来改进它们。一种简单的方法是使目录遍历接受回调作为参数：

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

这是最简单且最不灵活的解决方案。一个更加灵活的解决方案是实际上实现协程。你可以使用 free, monad-coroutine 或者 operational 自己实现协程单子，或者使用像conduit, enumerator 或者pipes 之类的许多流抽象，其中最后一个是我个人推荐的简单情况下。

Davorak的答案可能比这个更好。 - ertes
我之前写的iterateM的版本是：iterateM f x = (f x) >>= iterateM f >>= return.(x:). 它可以编译通过，但是当我运行：iterateM (return.(+1)) 0 >>= return.(take 10)，它永远不会终止，直到我按下Ctrl-C。这难道不是因为严格性吗？ - TorosFanny
6
我修改了Davorak链接的旧答案，使用了新的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库的内容，我建议你阅读教程。

你的回答很棒，但是我现在只对一些非常基础的话题感兴趣，你的回答对我来说有点深奥。我会稍后再去看一下。 - TorosFanny
4
众人都告诉你要使用迭代器或管道等当前流行的方法，但还有另一种经典的方法！只需使用来自 System.IO.Unsafe 的 unsafeInterleaveIO。这个类型为IO a -> IO a的函数只是修改了一个IO操作，使其仅在需要值thunk时才实际执行IO操作，这正是您所要求的。您可以使用它来轻松编写具有所需语义的iterateM。
像这样的例子是 unsafeInterleaveIO 显示优势的地方。
但是，我相信您已经注意到名称中的“不安全”--在其他情况下，您需要直接控制文件句柄和资源使用或类似内容时，unsafeInterleaveIO 确实会带来麻烦，甚至可能引入违反引用透明性的问题。
（参见此答案以获取更多讨论：When is unsafeInterleaveIO unsafe?）
但是，在这种情况下，我认为unsafeInterleaveIO 是显而易见、正确且简单的结果。
我发现 Just [1..]>>=return.(take 10) 和 [[1..]]>>=return.(take 10) 的效果正如我们所期望的。但是... - TorosFanny
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接