Sorted Grep: Wie würden Sie dieses Programm verbessern?

  • Dieses Programm implementiert eine sortierte grep , d. h. eine spezielle Version von grep für sortierte Dateien Es verwendet die binäre Suche nach Zeilen einer Datei, die mit einer bestimmten Zeichenfolge beginnt.

    Sie können den Code in eine Datei kopieren und einfügen und als folgenden Befehl ausführen:

         $> runhaskell sgrep.hs "string to find" sorted_file
     

    Ich suche Vorschläge zu Stil, Effizienz und Korrektheit.

         module Main where
    
        import Data.List (isPrefixOf)
        import Data.Maybe (isNothing, fromJust)
        import System.Environment (getArgs)
        import System.IO
    
        -- Chunk of a file
        data Chunk = Chunk Handle Integer Integer
    
        -- Is char newline?
        isNL :: Char -> Bool
        isNL c = c == '\n'
    
        -- Are we at the beginning of file?
        isBOF :: Handle -> IO Bool
        isBOF = (fmap (== 0)) . hTell
    
        -- Go to beginning of line
        goToBOL :: Handle -> IO ()
        goToBOL h = do
                bof <- isBOF h
                if bof        
                   then return ()
                   else do 
                           eof <- hIsEOF h
                           if eof
                              then do 
                                      hSeek h RelativeSeek (-2)
                                      goToBOL h
    
                              else do    
                                      c <- hGetChar h
                                      if isNL c
                                         then return ()
                                         else do
                                                 hSeek h RelativeSeek (-2)
                                                 goToBOL h
    
        getCurrentLine :: Handle -> IO String
        getCurrentLine h = goToBOL h >> hGetLine h
    
        getPrevLine :: Handle -> IO (Maybe String)
        getPrevLine h = do
                goToBOL h
                bof <- isBOF h
                if bof
                   then return Nothing
                   else do
                           hSeek h RelativeSeek (-2)
                           goToBOL h
                           bof <- isBOF h
                           if bof
                              then return Nothing
                              else do
                                      hSeek h RelativeSeek (-2)
                                      goToBOL h
                                      line <- hGetLine h
                                      return $ Just line
    
        goTo :: Handle -> Integer -> IO ()
        goTo h i = do
                hSeek h AbsoluteSeek i
    
        search :: Chunk -> String -> IO (Maybe String)
        search (Chunk h start end) str
                | start >= end = return Nothing
                | otherwise = do
                        if mid == (end - 1)
                           then return Nothing
                           else do
                                   goTo h mid
                                   midLine <- getCurrentLine h
                                   prevLine <- getPrevLine h
                                   --  putStrLn $ "*** " ++ show start ++ " " ++ show end ++ " " ++ show mid ++ " " ++ midLine ++ ", " ++ show prevLine
                                   if str `isPrefixOf` midLine && ((isNothing prevLine) || not (str `isPrefixOf` (fromJust prevLine)))
                                      then return $ Just midLine
                                      else if str < midLine
                                              then search (Chunk h start mid) str
                                              else search (Chunk h mid end) str
                   where mid = (start + end) `div` 2
    
        sgrep :: Handle -> String -> IO ()
        sgrep h s = do
                len <- hFileSize h
                match <- search (Chunk h 0 len) s
                --  putStrLn $ show match
                c <- hGetContents h
                putStrLn . unlines $ takeWhile (isPrefixOf s) (lines c)
    
        main :: IO ()
        main = do
                args <- getArgs
                let s = head args
                putStrLn s
                let fname = head $ tail args
                withFile fname ReadMode (\h -> sgrep h s)
     
    26 November 2011
    jd.
2 answers
  • Benutze deine Monaden! Ihr Code zeigt das Rechts-Antipattern. Sie können es mit when und guard vermeiden. Betrachten Sie goToBOL. So würde ich es schreiben:

     -- Go to beginning of line
    goToBOL :: Handle -> IO ()
    goToBOL h = do
            bof <- isBOF h
            when (not bof) $ do      
            eof <- hIsEOF h
            if eof then do hSeek h RelativeSeek (-2)
                           goToBOL h
                   else do c <- hGetChar h
                           when (not $ isNL c) $ do
                           hSeek h RelativeSeek (-2)
                           goToBOL h
     

    In Ihren anderen Funktionen, nämlich getPrevLine und search verwenden Sie besser MaybeT IO x anstelle von IO (Maybe x), da Sie die monadischen Kombinatoren besser verwenden können, wenn Sie dies tun.

    27 November 2011
    James Simm
  • Zusätzlich zu den Punkten von @ FUZxxl:

    Sie rufen sgrep nur aus der letzten Zeile von main auf, und die Parameter sind falsch herum. Wechseln Sie zu

     sgrep :: String -> Handle -> IO ()
    sgrep s h = do
                ...
     

    und

             ...
            withFile fname ReadMode (sgrep s)
     

    Und ich würde ein Muster mit den Befehlszeilenargumenten abgleichen (vorausgesetzt, Sie benötigen nicht die Vorteile von System.Console.GetOpt ):

     main :: IO ()
    main = do
            (s : fname : _) <- getArgs
            putStrLn s
            withFile fname ReadMode (sgrep s)
     
    27 November 2011
    dave4420