Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Listing all the contents of a directory by breadth-first order results in low efficiency

I writed a Haskell module to list all the contents of a directory by breadth-first order. The below is the source code.

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

It works correct but when performing on a large directory, it will "suspend" for a little while, and spring out all the results.

After a research I find it is the same question with sequence $ map return [1..]::[[Int]] see Why the Haskell sequence function can't be lazy or why recursive monadic functions can't be lazy

like image 397
TorosFanny Avatar asked Nov 28 '22 09:11

TorosFanny


1 Answers

This comes up every once in a while and the answer ends up being use an iteratee like library. Most often suggested recently has been the Proxy library.

  • Streaming recursive descent of a directory in Haskell
  • Older pipes solution out of date and non-iteratee like solution breadth-first traversal of directory tree is not lazy

I have seen Conduit solutions before and a few elegant monadic solutions, but I am not finding them now.

like image 137
Davorak Avatar answered Dec 04 '22 07:12

Davorak