Why is GHC complaining about wrong type?

Question

This little function checks a (finite) Brainfuck string for validity. It check's whether the [ and ] are balanced. The code is very straightforward and written to be tail-recursive:

-- checks Brainfuck for validity.
validateBrainfuck :: Monad m => String -> m String
validateBrainfuck s = maybe (return s) (fail . fromJust) (validate s 0) where
  validate :: String -> Int -> Maybe String -- Here inversed: String means error
  validate (']':_ ) 0 = Just "Too many closing brackets"
  validate (']':xs) c = validate xs (pred c)
  validate ('[':xs) c = validate xs (succ c)
  validate ( x :xs) c = validate xs       c
  validate []       0 = Nothing
  validate []       _ = Just "Too many opening brackets"

Now, GHC complains about typing issues:

Brainfuck.hs:62:58:
    Couldn't match expected type `Maybe String'
           against inferred type `[Char]'
      Expected type: Maybe (Maybe String)
      Inferred type: Maybe String
    In the third argument of `maybe', namely `(validate s 0)'
    In the expression:
        maybe (return s) (fail . fromJust) (validate s 0)

Maybe I'm just too silly to figure out what went wrong, but this looks very weird for me.

Answer 1

Look at the type of maybe and think what it should do:

maybe :: b -> (a -> b) -> Maybe a -> b

If the maybe value contains no result (i.e. Nothing), maybe returns the b argument.

Otherwise - when Just a is given - it applies the given function to the valid result. We don't need any fromJust extraction here.

Your code just becomes

maybe (return s) fail (validate s 0)