4

ディレクトリのすべての内容を幅優先順にリストする 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

正常に動作しますが、大きなディレクトリで実行すると、しばらくの間「中断」し、すべての結果が表示されます。

調査の結果、Haskell シーケンス関数が遅延できない理由または再帰的なモナド関数が遅延できない理由sequence $ map return [1..]::[[Int]]を参照してくださいと同じ質問であることがわかりました

4

4 に答える 4

12

これは時々発生し、答えはライブラリのような反復を使用することになります。最近最もよく提案されているのはProxyライブラリです。

以前に Conduit ソリューションといくつかのエレガントなモナド ソリューションを見たことがありますが、今は見つかりません。

于 2013-01-23T08:05:05.833 に答える
9

まず、厳しさとは関係ありません。多くのモナドと同様に、IO は実際にはそのモナド操作において厳密ではありません。これは、レイジー対熱心な I/O に関連しています。

問題は、最初にディレクトリ トラバーサルを実行してから、結果を処理することです。コルーチンを使用してそれらをインターリーブすることで、これを改善できます。簡単な方法の 1 つは、ディレクトリ トラバーサルがコールバックを引数として受け取るようにすることです。

getDirectoryContents' :: (MonadIO m) => (FilePath -> m a) -> FilePath -> m ()
getDirectoryContents' k fp = {- ... -}

これは、最も単純で柔軟性の低いソリューションです。より柔軟な解決策は、実際にコルーチンを実装することです。free、monad-coroutine 、またはoperatingを使用して独自のコルーチン モナドをロールするか、または、このような単純なケースに対する私の個人的な推奨事項である、conduit、enumerator、またはpipesなどの多くのストリーミング抽象化の 1 つを使用することができます。

于 2013-01-23T08:21:30.750 に答える
6

pipes新しいライブラリを使用するために、Davorak がリンクしている古い回答を変更しました。

StateP幅優先走査を実行できるように、走査されていないディレクトリのキューを保持するために使用します。MaybeP便宜上、ループから抜け出すために使用します。

import Control.Monad
import Control.Proxy
import Control.Proxy.Trans.Maybe
import Control.Proxy.Trans.State as S
import Data.Sequence hiding (filter)
import System.FilePath.Posix
import System.Directory

getUsefulContents :: FilePath -> IO [FilePath]
getUsefulContents path
  = fmap (filter (`notElem` [".", ".."])) $ getDirectoryContents path

traverseTree
    :: (Proxy p)
    => FilePath
    -> () -> Producer (MaybeP (StateP (Seq FilePath) p)) FilePath IO r
traverseTree path () = do
    liftP $ S.modify (|> path)
    forever $ do
        x <- liftP $ S.gets viewl
        case x of
            EmptyL    -> mzero
            file :< s -> do
                liftP $ S.put s
                respond file
                p <- lift $ doesDirectoryExist file
                when p $ do
                    names <- lift $ getUsefulContents file
                    let namesfull = map (file </>) names
                    liftP $ forM_ namesfull $ \name ->
                        S.modify (|> name)

これは、ファイルの幅優先の遅延プロデューサーを定義します。印刷ステージに接続すると、ツリーを走査するときにファイルが印刷されます。

main = runProxy $ evalStateK empty $ runMaybeK $
    traverseTree "/tmp" >-> putStrLnD

怠惰とは、3 つのファイルのみを要求した場合、3 つのファイルを生成するために必要なだけツリーをトラバースし、停止することを意味します。

    main = runProxy $ evalStateK empty $ runMaybeK $
        traverseTree "/tmp" >-> takeB_ 3 >-> putStrLnD

pipesライブラリについて詳しく知りたい場合は、チュートリアルを読むことをお勧めします。

于 2013-01-23T16:34:20.823 に答える
3

誰もが、現在一般的なアプローチである iteratee やパイプなどを使用するように言っています。しかし、これを行う別の古典的な方法があります。unsafeInterleaveIOから使用するだけSystem.IO.Unsafeです。このタイプの関数がIO a -> IO a行うのは、値サンクが要求されたときにのみ実際に IO を実行するように IO アクションを変更することだけです。これはまさにあなたが求めていたものです。iterateMこれを使用して、目的のセマンティクスを簡単に記述できます。

このような例は、unsafeInterleaveIO輝く場所です。

ただし、名前に「安全でない」という意味があることに気付いたはずです。ファイルハンドルやリソースの使用状況などを直接制御したい場合、unsafeInterleaveIO実際に悪いニュースになり、潜在的に導入する可能性さえある他の例があります。参照透過性の違反。

(詳細については、この回答を参照してください: When is unsafeInterleaveIO unsafe? )

unsafeInterleaveIOしかし、繰り返しますが、このような場合、当然のことであり、正しく、率直な結果だと思います。

于 2013-01-23T19:27:39.730 に答える