Type Constraints in Typeclass

Question

For fun I'm building a parser library. In this library I have a Parser data type:

data Parser e a = Parser (String -> Either e (a, String))

I'm able to define Functor and Applicative instances of Parser, but I don't think I can make an Alternative instance without constraining the "error" type or the "value" type the parser could return. Originally, this made me create an Applicative instance for when the error types are String messages, but I realized that I should be able to release this constraint to any message data type that has an Alternative (or maybe Monoid instead?) instance as well. With that in mind I wrote this:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
instance Alternative e => Alternative (Parser e)
  where
    empty = Parser $ \s -> Left empty
    (<|>) (Parser p1) (Parser p2) = Parser $ \s -> tryParser s p2 $ p1 s
      where
        tryParser s p2 (Left _ ) =  p2 s
        tryParser _ _ x          = x

Unfortunately, this fails to compile. When I load it into ghci I get this error message:

Parsertest.hs:31:47:
    Expecting one more argument to `e'
    In the instance declaration for `Alternative (Parser e)'
Failed, modules loaded: none.

When I search online, this seems to be the solution, but it doesn't work for me. What am I missing?

Answer 1

The problem is that Alternative is for type constructors of kind * -> *, so if you say

instance Alternative e => ....

then e has to be a type constructor, not a type. So e could be [] or Maybe or something, but not Int.

Alternative's operator is <|> which has type Alternative e => e a -> e a -> e a. This forces e to take an argument to make a type, like Maybe has to take an argument, eg Maybe Int.

Use Monoid instead of Alternative, because it's a type class instead of a constructor class. It's operator mappend has type Monoid e => e -> e -> e which is what you want for combining errors.