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

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

monad-transformers monads haskell list

Travis Brown · 技术社区 · 15 年前

上周用户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 年前

Daniel 15 年前

分析表明 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

Reid Barton 15 年前

我很好奇,同一个程序写出来用起来有多好 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))

sclv 15 年前

推荐文章

Enlico · 运行monad变压器堆产生的任何东西都不是==无?

1 年前

Materia Gravis · Haskell中基于状态筛选列表

2 年前

Patrik · monad transformer中的分布式过程

8 年前

Pedro Rolo · 生成解析器,该解析器在另一个解析器的输出上运行接收到的解析器,并以一元方式连接结果

8 年前

OllieB · 修改transformer堆栈中的内部读取器

8 年前

Nathan Ringo · 将单子添加到transformer堆栈的中间

8 年前

Saurabh Nanda · 如何创建允许IO但不是MonadIO的monad?

9 年前

Savenkov Alexey · Scalaz:如何组合OptionT[State[_],T]类型的单子,这样它就不会终止于None

9 年前

SkyWriter · 在WriterT中包装Maybe以添加日志记录

10 年前

jakubdaniel · 多态函数(如lift)的类型约束

10 年前