Avoiding infinite recursion with mfix

user_6152736 0
Viewed 99

Let:

{-# LANGUAGE RecursiveDo #-}

test :: [a] -> Maybe Int
test []       = Just 0
test (_ : xs) = mdo
    unless (i == 0) Nothing -- 1
    i <- test xs            -- 2
    Just i

I'm looking for an explanation of why calling e.g. test "hey" results in an infinite loop, and in general how to avoid such behavior when dealing with mfix. Also, is there a way to correct the previous toy-example without exchanging the order of (1) and (2)?

recursion haskell
1 Answers

This part of your code:

mdo unless (i == 0) Nothing
    i <- test xs
    Just i

desugars to:

mfix (\i -> do unless (i == 0) Nothing
               j <- test xs
               Just j)

After renaming the binding of i to j for clarity in the do-expression.

The first mfix law states that mfix f = _|_ iff f is strict. The f in this case is:

\i -> do unless (i == 0) Nothing
         j <- test xs
         Just j

And this function is strict. (If you call f with _|_, you'll get _|_.) Thus mfix on it is _|_ by definition. Substituting back to your original, we get:

test []       = Just 0
test (_ : xs) = _|_

This says that unless you pass test the empty list, it'll always diverge no matter what other input you pass to it.

That's the theory side of it, of course. But practically, I don't see why you'd ever want to do this sort of recursion, mixing a recursively defined function with a monadic-value recursive subpart. Unless this is a mere curiosity, there's probably a better way to structure your program that avoids this issue. But for that, you'll have to share more information as to what you are exactly trying to achieve.

user_9363100
Related