What's wrong with the types for my Parser class?

Question

I've been having some free time these days so I decided to learn some haskell.

For practice I am translating a project I made in one of my classes in SCALA. But I have problems with this part of the code. It is pretty simple to understand.

The idea is to model some Parsers that would take some string and would parse it to a ParserOutput that contains the parsed element "output" and the "remainder" (part of the string that couldn't be parsed).

I could have done this without defining a new class (just using the data "MyParser") but I thought it would be interesting to define a class so that I could define in one place all the methods that I expect Parsers to work on.

data ParserOutput a = 
    Failure | Success { output :: a, remainder :: String } 
        deriving (Show)

data MyParser t = MyParser (String -> ParserOutput t)

class Parser p where
    parse :: p -> String -> ParserOutput t

instance Parser (MyParser t) where
    parse (MyParser parserDefinition) = parserDefinition

The error I am getting is:

* Couldn't match type `t1' with `t'
      `t1' is a rigid type variable bound by
        the type signature for:
          parse :: forall t1. MyParser t -> String -> ParserOutput t1
        at ...
      `t' is a rigid type variable bound by
        the instance declaration
        at ...
      Expected type: String -> ParserOutput t1
        Actual type: String -> ParserOutput t
    * In the expression: parserDefinition
      In an equation for `parse':
          parse (MyParser parserDefinition) = parserDefinition
      In the instance declaration for `Parser (MyParser t)'
    * Relevant bindings include
        parserDefinition :: String -> ParserOutput t
          (bound at ...)
        parse :: MyParser t -> String -> ParserOutput t1
          (bound at ...)

Answer 1

The type signature

parse :: p -> String -> ParserOutput t

says parse can be used with any types p and t chosen by the caller.

Now p is actually somewhat restricted because it must be an instance of Parser, so the effective type is

parse :: (Parser p) => p -> String -> ParserOutput t

but t is still completely free and unrelated to p.

As a user of a function, I should (given a parser value px) be able to write e.g.

( parse px "" :: ParserOutput Int,
  parse px "" :: ParserOutput String,
  parse px "" :: ParserOutput (Double -> Double -> [Bool])
)

Again, the type signature says I can choose t freely and differently in each call.

Your MyParser instance doesn't satisfy this requirement. For clarity, let's use a different name for the type parameter:

instance Parser (MyParser r) where
    parse (MyParser parserDefinition) = parserDefinition

In this instance, parse should have type

parse :: MyParser r -> String -> ParserOutput t

but the actual type is

parse :: MyParser r -> String -> ParserOutput r

With parserDefinition the result type depends directly on the parser type, but the class declaration doesn't reflect that.

---

If you really want to use a class for this, you need to make this relationship explicit.

For example, you could abstract over the type constructor MyParser, not MyParser t:

class Parser p where
    parse :: p t -> String -> ParserOutput t

instance Parser MyParser where
    parse (MyParser parserDefinition) = parserDefinition

This is slightly less general than your original attempt because it requires Parser instances to be parameterized by their result type.

To allow arbitrary parser / result types, we'd have to use something like functional dependencies:

{-# LANGUAGE FunctionalDependencies, FlexibleInstances #-}

class Parser p t | p -> t where
    parse :: p -> String -> ParserOutput t

instance Parser (MyParser t) t where
    parse (MyParser parserDefinition) = parserDefinition

Or using associated type families:

{-# LANGUAGE TypeFamilies #-}

class Parser p where
    type Result p
    parse :: p -> String -> ParserOutput (Result p)

instance Parser (MyParser t) where
    type Result (MyParser t) = t
    parse (MyParser parserDefinition) = parserDefinition