Sorted grep in Haskell This program implements a sorted grep, that is, a specialized version of grep for sorted files. It uses binary search for the lines of a file that begin with a certain string.

You can copy and paste the code in a file and run it as:

$&gt; runhaskell sgrep.hs "string to find" sorted_file


I'm looking for suggestions about style, efficiency, and correctness.

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 -&gt; Bool
isNL c = c == '\n'

-- Are we at the beginning of file?
isBOF :: Handle -&gt; IO Bool
isBOF = (fmap (== 0)) . hTell

-- Go to beginning of line
goToBOL :: Handle -&gt; IO ()
goToBOL h = do
        bof &lt;- isBOF h
        if bof        
           then return ()
           else do 
                   eof &lt;- hIsEOF h
                   if eof
                      then do 
                              hSeek h RelativeSeek (-2)
                              goToBOL h

                      else do    
                              c &lt;- hGetChar h
                              if isNL c
                                 then return ()
                                 else do
                                         hSeek h RelativeSeek (-2)
                                         goToBOL h

getCurrentLine :: Handle -&gt; IO String
getCurrentLine h = goToBOL h &gt;&gt; hGetLine h

getPrevLine :: Handle -&gt; IO (Maybe String)
getPrevLine h = do
        goToBOL h
        bof &lt;- isBOF h
        if bof
           then return Nothing
           else do
                   hSeek h RelativeSeek (-2)
                   goToBOL h
                   bof &lt;- isBOF h
                   if bof
                      then return Nothing
                      else do
                              hSeek h RelativeSeek (-2)
                              goToBOL h
                              line &lt;- hGetLine h
                              return $ Just line

goTo :: Handle -&gt; Integer -&gt; IO ()
goTo h i = do
        hSeek h AbsoluteSeek i

search :: Chunk -&gt; String -&gt; IO (Maybe String)
search (Chunk h start end) str
        | start &gt;= end = return Nothing
        | otherwise = do
                if mid == (end - 1)
                   then return Nothing
                   else do
                           goTo h mid
                           midLine &lt;- getCurrentLine h
                           prevLine &lt;- getPrevLine h
                           --  putStrLn $ "*** " ++ show start ++ " " ++ show end ++ " " ++ show mid ++ " " ++ midLine ++ ", " ++ show prevLine
                           if str `isPrefixOf` midLine &amp;&amp; ((isNothing prevLine) || not (str `isPrefixOf` (fromJust prevLine)))
                              then return $ Just midLine
                              else if str &lt; midLine
                                      then search (Chunk h start mid) str
                                      else search (Chunk h mid end) str
           where mid = (start + end) `div` 2

sgrep :: Handle -&gt; String -&gt; IO ()
sgrep h s = do
        len &lt;- hFileSize h
        match &lt;- search (Chunk h 0 len) s
        --  putStrLn $ show match
        c &lt;- hGetContents h
        putStrLn . unlines $ takeWhile (isPrefixOf s) (lines c)

main :: IO ()
main = do
        args &lt;- getArgs
        let s = head args
        putStrLn s
        let fname = head $ tail args
        withFile fname ReadMode (\h -&gt; sgrep h s)
Use your monads! Your code exhibits the walking-right antipattern. You can avoid it with when and guard. Consider goToBOL. This is how I would write it:

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


In your other functions, namely getPrevLine and search, you'd better use MaybeT IO x instead of IO (Maybe x) as you can use the monadic combinators better when you do so.