为什么我的代码使用List包中的monadic列表这么慢？

Question

上周,用户Masse问了一个关于递归列出 Haskell目录中文件的问题.我的第一个想法是尝试使用List包中的 monadic列表,以避免在打印开始之前在内存中构建整个列表.我实现如下:

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]版本慢了几十倍.

我究竟做错了什么？我从来没有使用像这样的玩具示例之外的List包ListT,所以我不知道期望什么样的性能,但处理目录~30,000个文件的30秒(相对于几分之一秒)似乎也是如此慢.

Answer 1

分析表明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子目录，并且它们的内容已经在列表中计算：，那么应用后您将得到（大致）：。由于需要时间，所以整个事情都需要时间。如果我们假设文件数量为且它们均匀分布，那么计算时间将为且这仅适用于 的第一级。d1, d2, ... dkjoin(...(([] ++ d1) ++ d2) ... ++ dk)x ++ yO(length x)O(d1 + (d1 + d2) + ... + (d1 + ... dk-1))nd1 ... dkjoinO(n*k)listFiles

我认为这是您的解决方案的主要性能问题。