Reading lines in haskell until non-empty string

Question

I am trying to read lines from input in Haskell until I find a non-empty line. Actually, I know how to do it simply using the following code:

notEmpty [] = return ""
notEmpty (l:xs) = do
  s <- l
  if s /= "" then return s
             else notEmpty xs

getLine' = notEmpty $ repeat getLine

Test (I typed two empty lines then 'foo'):

*> getLine'


foo
"foo"

However, for the sake of exercise, I am trying to achieve this using Monoids (http://learnyouahaskell.com/functors-applicative-functors-and-monoids#monoids), trying to mimick the First/getFirst Monoid (see link).

I first created a Monoid on lists that fits my needs (concatenation only keeps the first argument):

newtype FirstSt a = FirstSt { getFirstSt :: [a] }
    deriving (Eq, Ord, Read, Show)

instance Monoid (FirstSt a) where
    mempty = FirstSt []
    FirstSt [] `mappend` x = x
    FirstSt s  `mappend` _ = FirstSt s

Which works well on a infinite list of strings (thanks to laziness):

> getFirstSt . mconcat . map FirstSt $ ["", "", "foo", "", "bar"] ++ repeat ""
"foo"

However, I can't get it to work in the IO Monad. I tried the following:

ioFirstSt = (=<<) (return . FirstSt)
getLine'' = getFirstSt <$> mconcat <$> (sequence . map ioFirstSt $ repeat getLine)

Which has the correct type:

*> :t getLine''
getLine'' :: IO [Char]

However, Haskell keeps wanting to evaluate the whole list before giving it to mconcat... In there a way to keep laziness while navigating in the Monoid/Monad scope?

Answer 1

Your thinking is excellent. Monoid is a great structure for this, but sadly as bheklilr points out, sequence is going to perform all the IO regardless.

Theory vs practicality with a nod to Alternative

It would be nice to make instance Monoid (IO String) but we'd have to wrap it in a newtype to get it to compile, but then we'd lose some interoperability with other IO, so let's just write the functions without the instance.

I like to use <> instead of mappend, but it's taken, and <|> is also taken for Alternative, which is like a Monoid structure for Applicative functors, and you should certainly look into it. I wrote a bit about Alternative in this answer.

Anyway, let's use <||> and copy the fixity of <>:

infixr 6 <||>

Making a Monoid of a Monad of Eq Monoids

We can make a monoid out of IO String because we can check the value returned to see if it's "" and then do the next action if not. That's equivalent to using == to check whether we have mempty, so we can generalise to IO s as long as s is a Monoid with an Eq instance. Secondly, we don't need it to be IO, we could use any Monad:

(<||>) :: (Monoid s, Eq s, Monad m) => m s -> m s -> m s
m <||> n = do
    x <- m
    if x == mempty then n else return x

Notice that that's lazy about computing n - it doesn't bother if we're happy with the output of m. We could then define main = getLine <||> getLine <||> getLine >>= print to give the user up to 3 chances of entering something non-blank for us to print.

Identity and list concatenation

Mathematically that's a monoid with identity

msempty :: (Monoid s, Monad m) => m s
msempty = return mempty

Let's also define the equivalent of mconcat :: Monoid s => [s] -> s:

msconcat :: (Monoid s, Eq s, Monad m) => [m s] -> m s
msconcat = foldr (<||>) (return mempty)

Which lets us rewrite as main = msconcat [getLine,getLine,getLine] >>= print

Lazily combining infinitely many monadic monoids

The real test of laziness here is infinite lists of actions:

main = msconcat (repeat getLine) >>= print

That works fine, and terminates within a finite time if the user ever does something other than enter nothing. Hooray!