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?

AndrewC · Accepted Answer · 2013-08-13T23:10:05.060

6

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.

edited Aug 13 '13 at 23:10

answered Aug 13 '13 at 23:05

AndrewC

32,300
7
79
115

That makes things compile again. Do you know where I can read up on when Monoid, Alternative, MonadPlus make sense to be used? – chanko08 Aug 13 '13 at 23:57
1

Wellllll, I wrote [an answer](http://stackoverflow.com/a/13115196/1598537) and [another](http://stackoverflow.com/a/13174738/1598537) on a similar topic ([here](http://stackoverflow.com/questions/13080606)) if you're happy with rather theoretical discussions there. If you want more practical advice after reading them, you could try asking that as a new question, but be careful to make it clear that you've read them and that you want guidance for when to choose them, or if it's a minor clarification of one of those answers, ask in a comment. – AndrewC Aug 14 '13 at 01:20
@chanko I should have said that Alternative _is_ right for the parser, whilst Monoid makes sense for the error type. – AndrewC Aug 14 '13 at 07:27
Yeah, I knew that if I'm keeping with the applicative parser that I should keep the Alternative instance. Reading those links is making me consider extending my parser type to have a null parser instead. This way the alternative instance structure doesn't have to rely on the internals of the parser itself. Thank you for helpful links! – chanko08 Aug 14 '13 at 13:57
1

@chanko08 I think `<|>` should backtrack and use the second parser if the first one fails. (This is what parsers I've used do, and it allows you to replace `|` in a grammar with `<|>` in code. Therefore it should be looking at the input - the internals of the parser are relevant I think. Making a Null parser is easier, but failure and backtracking are more useful. The problem is that backtracking is hard without the Wadler's "How to replace failure with a list-of-successes" approach. – AndrewC Aug 15 '13 at 13:21
Yeah that's what my implementation does for `<|>`, this to me is more of an issue of what makes sense for `empty` to be. As you say, if I go with a `NullParser` extension to my parser than I see issues with how errors will propogate. If I go with the current solution than I'm forcing structure on the error type where I'm not really seeing is necessary. In the end, the structure probably isn't a big deal really, I just have some design things to mull over. Thanks for the feedback! – chanko08 Aug 16 '13 at 15:37

Type Constraints in Typeclass

1 Answers1