CODEWITHSUNDEEP
haskellmonadslazy-evaluation
MorJ
MorJ

Reputation: 586

Haskell tuple monad is too strict?

I was writing my code with Control.Monad.Writer.Lazy using (,) [String] as my writer monad. But I found that (>>=) and (>>) are too strict with the monoid operator? They cause infinte loop with this code for example:

type Wrtr a = ([String], a)
writer (x, w) = (w, x)

main :: IO ()
main = do
    let one = writer ((), ["goodbye"])
    let w = foldr1 (>>) $ repeat one
    let (log, _) = w
    mapM_ putStrLn . take 5 $ log

This code will loop endlessly and never print anything and it's bad for me. So for now I'm using this naive implementation of the same monad, which seems to be fine and lazy:

data Writer w a = Writer w a
instance Functor (Writer w) where
    fmap f (Writer w x) = Writer w (f x)
instance Monoid w => Applicative (Writer w) where
    pure x = Writer mempty x
    (Writer w1 f) <*> (Writer w2 x) = Writer (w1 <> w2) (f x)
instance Monoid w => Monad (Writer w) where
    return = pure
    (Writer w1 x) >>= f =
        let (Writer w2 y) = f x
        in Writer (w1 <> w2) y
writer (x, w) = Writer w x

(You have to define functor and applicative instances because of monoid constraint)

If you then run the code with the same exact main function as above, it will print "goodbye" five times and exit.

So the question is: why are tuples so strict? Or if it's not strictness, what is it and why is it there?

BTW I'm using ghc 8.6.4 and everything else whihch comes with stack lts-13.19

Upvotes: 4

Views: 332

Answers (2)

HTNW
HTNW

Reputation: 29193

That's because your Writer violates the monad laws. Look at this law:

-- forall (f :: a -> Writer m b) (x :: a).
return x >>= f = f x
-- basically f (id x) = f x, which we should agree is pretty important!

But, alas, it doesn't hold! let f = undefined! (or f = const undefined; they are indistinguishable if you don't use seq)

  return x >>= undefined
= Writer mempty x >>= undefined
= let (Writer m y) = undefined
  in  Writer (mempty <> m) y
= Writer (mempty <> undefined) undefined

Yet, by law,

  return x >>= undefined
= undefined x
= undefined

These are not equivalent, therefore your lazy Monad instance is unlawful (and yes, I believe so is the one in mtl). However, Fast and Loose Reasoning is Morally Correct, so we generally just accept it. The idea is that a lazy Writer monad generally follows the laws its supposed to, as long as you keep infinite or bottoming values out of it, but it breaks down at those edge cases. In contrast, the strict implementation is completely lawful, and that is why it is in base. However, as you've discovered, when lazy Writers break the law, they do it in a useful manner, so we place the lazy implementation in mtl.

Here is a demo of this behavior. Notice that the lazy version produces a Writer " in the output before blowing up, while both the strict version and the specification given by the law don't do so.

Upvotes: 5

Will Ness
Will Ness

Reputation: 71065

Hackage says

instance Monoid a => Monad ((,) a) where
    (u, a) >>= k = case k a of (v, b) -> (u <> v, b)

and this means they are strict because of the case (unlike your let (Writer w2 y) = f x):

foldr1 (>>) $ repeat one
= one >> foldr1 (>>) (repeat one)
= (["goodbye"], ()) >>= \_ -> foldr1 (>>) (repeat one)
= case ((\_ -> foldr1 (>>) (repeat one)) ()) of (v, b) -> (["goodbye"] <> v, b)
= case (foldr1 (>>) (repeat one)) of (v, b) -> (["goodbye"] <> v, b)

and this actually forces the nested (foldr1 (>>) ...) before you can ever access the ["goodbye"] <> v part.

This is because case pattern matching is forcing but let patterns are lazy. Your code in effect writes the above as

= let (v, b) = foldr1 (>>) (repeat one) in (["goodbye"] <> v, b)

and all is fine and lazy.

Upvotes: 4

Related Questions