代码之家 › 专栏 › 技术社区 › Travis Brown

为什么我的代码使用列表包中的单子列表如此缓慢?

monad-transformers monads haskell list

13

Travis Brown · 技术社区 · 16 年前

上周用户Masse请求 question about recursively listing files List package 避免在打印开始之前在内存中生成整个列表。我的实现如下:

module Main where

import Prelude hiding (filter) 
import Control.Applicative ((<$>))
import Control.Monad (join)
import Control.Monad.IO.Class (liftIO)
import Control.Monad.ListT (ListT)
import Data.List.Class (cons, execute, filter, fromList, mapL)
import System (getArgs)
import System.Directory (getDirectoryContents, doesDirectoryExist)
import System.FilePath ((</>))

main = execute . mapL putStrLn . listFiles =<< head <$> getArgs

listFiles :: FilePath -> ListT IO FilePath
listFiles path = liftIO (doesDirectoryExist path) >>= listIfDir
  where
    valid "."  = False
    valid ".." = False
    valid _ = True
    listIfDir False = return path
    listIfDir True
      =  cons path
      $  join
      $  listFiles
     <$> (path </>)
     <$> (filter valid =<< fromList <$> liftIO (getDirectoryContents path))

FilePath -> IO [FilePath] 版本。

我做错什么了?我从没用过 列表 包裹的 ListT

3 回复 | 直到 9 年前

1

3

Daniel 16 年前

分析表明 join doesDirectoryExists

  join x
=> (definition of join in Control.Monad)
  x >>= id
=> (definition of >>= in Control.Monad.ListT)
  foldrL' mappend mempty (fmap id x)
=> (fmap id = id)
  foldrL' mappend mempty x

如果在搜索的根目录中 k d ₁ , d ₂ , ... d _k ,然后在申请之后 参加 (...(([] ++ d ₁ ) ++ d ₂ ) ... ++ d _k ) . 自从 x ++ y O(length x) O(d ₁ + (d ₁ + d ₂ ) + ... + (d ₁ + ... d _k -1)) . 如果我们假设文件的数量是 n 它们均匀分布在 d ₁ ... d _k 参加 会是 O(n*k) listFiles

2

Reid Barton 16 年前

我很好奇,同一个程序写出来用起来有多好 logict LogicT ListT ,但以连续传递样式实现,因此它不应具有 concat -你似乎遇到了相关类型的问题。

import Prelude hiding (filter)
import Control.Applicative
import Control.Monad
import Control.Monad.Logic
import System (getArgs)
import System.Directory (getDirectoryContents, doesDirectoryExist)
import System.FilePath ((</>))

main = sequence_ =<< observeAllT . fmap putStrLn . listFiles =<< head <$> getArgs

cons :: MonadPlus m => a -> m a -> m a
cons x xs = return x `mplus` xs

fromList :: MonadPlus m => [a] -> m a
fromList = foldr cons mzero

filter :: MonadPlus m => (a -> Bool) -> m a -> m a
filter f xs = do
  x <- xs
  guard $ f x
  return x

listFiles :: FilePath -> LogicT IO FilePath
listFiles path = liftIO (doesDirectoryExist path) >>= listIfDir
  where
    valid "."  = False
    valid ".." = False
    valid _ = True
    listIfDir False = return path
    listIfDir True
      =  cons path
      $  join
      $  listFiles
     <$> (path </>)
     <$> (filter valid =<< fromList <$> liftIO (getDirectoryContents path))

3

1

sclv 16 年前