Sorted grep in Haskell
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.