निर्देशिका वृक्ष की चौड़ाई-प्रथम ट्रैवर्सल आलसी नहीं है

Question

मैं निर्देशिका पेड़ को पार करने की कोशिश करता हूं। एक बेवकूफ गहराई - पहला ट्रैवर्सल आलसी फैशन में डेटा का उत्पादन नहीं करता है और स्मृति से बाहर चला जाता है। मैंने अगली बार एक चौड़ाई पहली कोशिश की, जो एक ही समस्या दिखाता है - यह उपलब्ध सभी स्मृति का उपयोग करता है और फिर दुर्घटनाग्रस्त हो जाता है।

कोड रहा है:

getFilePathBreadtFirst :: FilePath -> IO [FilePath] 
getFilePathBreadtFirst fp = do 
    fileinfo <- getInfo fp 
    res :: [FilePath] <- if isReadableDirectory fileinfo 
      then do 
       children <- getChildren fp 
       lower <- mapM getFilePathBreadtFirst children 
       return (children ++ concat lower) 
      else return [fp]  -- should only return the files? 
    return res 

getChildren :: FilePath -> IO [FilePath] 
getChildren path = do 
      names <- getUsefulContents path 
      let namesfull = map (path </>) names 
      return namesfull 

testBF fn = do -- crashes for /home/frank, does not go to swap 
    fps <- getFilePathBreadtFirst fn 
    putStrLn $ unlines fps 

मुझे लगता है कि सभी कोड लीनियर या पूंछ पुनरावर्ती है, और मैं उम्मीद होती है कि फ़ाइल नामों की सूची तुरंत शुरू होता है, लेकिन वास्तव में ऐसा नहीं है। मेरे कोड और मेरी सोच में त्रुटि कहां है? मैं आलसी मूल्यांकन कहां खो गया है?

Answer 1

मैं आपके प्रश्न को हल करने के लिए तीन अलग-अलग चाल का उपयोग करूंगा।

• छल 1: फ़ाइल नाम पेड़ traversing के साथ समवर्ती स्ट्रीम करने के लिए pipes पुस्तकालय का उपयोग करें।
• ट्रिक 2: StateT (Seq FilePath) ट्रांसफॉर्मर का उपयोग चौड़ाई-पहले ट्रैवर्सल प्राप्त करने के लिए करें।
• ट्रिक 3: लूप और बाहर निकलने के दौरान मैन्युअल रिकर्सन से बचने के लिए MaybeT ट्रांसफॉर्मर का उपयोग करें।

निम्नलिखित कोड इन तीन चालों को एक मोनड ट्रांसफॉर्मर स्टैक में जोड़ता है।

import Control.Monad 
import Control.Monad.Trans 
import Control.Monad.Trans.Maybe 
import Control.Monad.State.Lazy 
import Control.Pipe 
import Data.Sequence 
import System.FilePath.Posix 
import System.Directory 

loop :: (Monad m) => MaybeT m a -> m() 
loop = liftM (maybe() id) . runMaybeT . forever 

quit :: (Monad m) => MaybeT m a 
quit = mzero 

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

permissible :: FilePath -> IO Bool 
permissible file 
    = fmap (\p -> readable p && searchable p) $ getPermissions file 

traverseTree :: FilePath -> Producer FilePath IO() 
traverseTree path = (`evalStateT` empty) $ loop $ do 
    -- All code past this point uses the following monad transformer stack: 
    -- MaybeT (StateT (Seq FilePath) (Producer FilePath IO))() 
    let liftState = lift 
     liftPipe = lift . lift 
     liftIO = lift . lift . lift 
    liftState $ modify (|> path) 
    forever $ do 
     x <- liftState $ gets viewl 
     case x of 
      EmptyL -> quit 
      file :< s -> do 
       liftState $ put s 
       liftPipe $ yield file 
       p <- liftIO $ doesDirectoryExist file 
       when p $ do 
        names <- liftIO $ getUsefulContents file 
        -- allowedNames <- filterM permissible names 
        let namesfull = map (path </>) names 
        liftState $ forM_ namesfull $ \name -> modify (|> name) 

यह चौड़ाई-पहले फ़ाइल नाम है कि पेड़ ट्रेवर्सल के साथ समवर्ती सेवन किया जा सकता का एक जनरेटर पैदा करता है।

printer :: (Show a) => Consumer a IO r 
printer = forever $ do 
    a <- await 
    lift $ print a 

>>> runPipe $ printer <+< traverseTree path 
<Prints file names as it traverses the tree> 

तुम भी चुन सकते हैं सभी मूल्यों मांग नहीं करने के लिए:: आप का उपयोग कर मूल्यों का उपभोग इससे भी महत्वपूर्ण बात

-- Demand only 'n' elements 
take' :: (Monad m) => Int -> Pipe a a m() 
take' n = replicateM_ n $ do 
    a <- await 
    yield a 

>> runPipe $ printer <+< take' 3 <+< traverseTree path 
<Prints only three files> 

, कि पिछले उदाहरण केवल पेड़ पार किए जाने के रूप में ज्यादा के रूप में आवश्यक तीन उत्पन्न करने के लिए फाइलें और फिर यह रुक जाएगी। यह पूरे पेड़ को बर्बाद कर देता है जब आप चाहते थे कि 3 परिणाम थे!

pipes लाइब्रेरी चाल के बारे में और जानने के लिए, pipes tutorial पर Control.Pipes.Tutorial पर परामर्श लें।

लूप चाल के बारे में और जानने के लिए, यह blog post पढ़ें।

मुझे चौड़ाई पहले ट्रैवर्सल के लिए कतार चाल के लिए एक अच्छा लिंक नहीं मिला, लेकिन मुझे पता है कि यह कहीं कहीं बाहर है। अगर कोई और इसके लिए एक अच्छा लिंक जानता है, तो बस इसे जोड़ने के लिए मेरा जवाब संपादित करें।

Answer 2

मैंने पाइप और पेड़ ट्रैवर्सल के प्रबंधन को अलग कर दिया है। यहाँ पहली बार पाइप (! अनिवार्य रूप से गोंजालेस की कोड - धन्यवाद) के लिए कोड:

traverseTree :: FilePath -> Producer FilePath IO() 
--^traverse a tree in breadth first fashion using an external doBF function 
traverseTree path = (`evalStateT` empty) $ loop $ do 
-- All code past this point uses the following monad transformer stack: 
-- MaybeT (StateT (Seq FilePath) (Producer FilePath IO))() 
let liftState = lift 
    liftPipe = lift . lift 
    liftIO = lift . lift . lift 
liftState $ modify (|> path) 
forever $ do 
    x <- liftState $ gets viewl 
    case x of 
     EmptyL -> quit 
     file :< s -> do 
      (yieldval, nextInputs) <- liftIO $ doBF file 
      liftState $ put s 
      liftPipe $ yield yieldval 
      liftState $ forM_ nextInputs $ \name -> modify (|> name) 

अगले पेड़ ट्रेवर्सल के लिए कोड:

doBF :: FilePath -> IO (FilePath, [FilePath]) 
doBF file = do 
    finfo <- getInfo file 
    let p = isReadableDirectoryNotLink finfo 
    namesRes <- if p then do 
     names :: [String] <- liftIO $ getUsefulContents file 
     let namesSorted = sort names 
     let namesfull = map (file </>) namesSorted 
     return namesfull 
     else return []   
    return (file, namesRes) 

मैं एक समान कार्य वाले doBF को बदलने के लिए आशा पहले गहराई को पार करने के लिए।मुझे लगता है कि मैं ट्रैवर्सट्री को अधिक सामान्य बना सकता हूं और न केवल फाइलपैथ ~ स्ट्रिंग के लिए, लेकिन मुझे नहीं लगता कि कौन सी कक्षा अनुक्रमों पर खाली कार्य है। आम तौर पर उपयोगी हो सकता है।