Abstract data types in a type class definition

Question

I'm trying to understand what's happening with the type s below:

class A a where
    f :: a -> s

data X = X

instance A X where
     f x = "anything"

I expected this to work, thinking that since type s isn't bound to anything, it could be anything. But the compiler says that it "Couldn't match expected type ‘s’ with actual type ‘[Char]’", as if type s was a fixed type like Int, Char…

So my second interpretation was to say that, since we don't know anything about s in the type class declaration, we cannot tell when making X an instance of A if the return value of the function f we give matches type s or not. But there are type classes that use abstract data types that are not bound to anything without problems, like Functor:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Why is the type s above a problem when types a and b here aren't?

By writing f :: a -> s, you say to the compiler that the "user" of the function can decide what to use, not the instance of A. — Willem Van Onsem

leftaroundabout leftaroundabout · Accepted Answer · 2017-10-12T15:57:55

You're trying to express this:

    f :: a -> ∃s . s

...but what the signature you've written says is actually

    f :: a -> ∀s . s

What does all of that mean?

The existential type ∃s . s means, the functions may return a value of some type, i.e. “there exists a type s such that the function returns an s value”.
This is not supported by the Haskell language, because it turns out to be pretty useless.
The universal type ∀s . s means, the function is able to produce a value of any type, i.e. “for all types s, the function can return an s value”.

The latter is very useful; fmap is actually a good example: that function works, no matter what types a and b are, and the user is always guaranteed that the result will actually have the desired type, namely f b.

But that means you can't just pick some particular type in the implementation, like you did with String. ...Well, actually you can do that, but only by wrapping the existential in a data type:

{-# LANGUAGE ExistentialQuantification, UnicodeSyntax #-}

data Anything = ∀ s . Anything s

class A a where
  f :: a -> Anything

instance A X where
  f x = Anything "anything"

...but as I said, this is almost completely useless, because when somebody wants to use that instance they'll have no way to know what particular type the wrapped result value has. And there is nothing you can do with a value of completely unknown type.

Abstract data types in a type class definition

1 Answers