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

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]] 的问题相同。见 Why the Haskell sequence function can't be lazy or why recursive monadic functions can't be lazy

Answer 1

这每隔一段时间就会出现一次，答案最终是使用类似库的迭代器。最近最常被推荐的是Proxy图书馆。

Streaming recursive descent of a directory in Haskell

旧管道解决方案已过时且非迭代式解决方案 breadth-first traversal of directory tree is not lazy

我以前见过 Conduit 解决方案和一些优雅的单子(monad)解决方案，但我现在找不到它们。