Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Type-class instances for types with 2 parameters when the type-class has only one

Consider the following type-class:

class Listable a where
   asList :: a t -> [t]

It's easy enough to create instances for types with one parameter:

instance Listable [] where
   asList = id

instance Listable Maybe where
   asList (Just x) = [x]
   asList Nothing = []

Now how would I make an instance for a pair with two identical type parameters? Of course I could do some wrapping:

data V2 a = V2 a a

v2 (p,q) = V2 p q

instance Listable V2 where
   asList (V2 p q) = [p,q]

Now I could write things like asList $ v2 (47, 11), but this kind of defeats the purpose.

Is there a way to limit the type of pair to cases where both type parameters are equal, and to write a Listable instance for that? If not, what is the usual workaround?

like image 227
Landei Avatar asked Jul 19 '11 12:07

Landei


2 Answers

There are lots of ways to do this, conceptually. Unfortunately, most of them don't actually work. Alas!

First, as a functional programmer, I'd wager that this is what you really want to write:

instance Listable (\a -> (a, a)) where
    asList (p, q) = [p,q]

Unfortunately type-level lambdas don't exist. We could write a named version of the above lambda using a type synonym:

type Same2 f a = f a a

instance Listable (Same2 (,)) where { ... }

That's not allowed either, because the type synonym isn't fully-applied. We could instead imagine the type class taking an extra argument that would describe how to apply the type variables:

class Listable app f where
    asList :: app f a -> [a]

instance Listable __ Maybe where { ... }

instance Listable __ (,) where { ... }

Without even thinking about what app might be, this also fails because we don't have a consistent kind for the f parameter.

Moving on to things that actually work, I think the most common way is to wrap the type synonym approach inside a newtype, then just deal with the wrapping and unwrapping that involves.

newtype Same2 f a = Same2 (f a a)

instance Listable (Same2 (,)) where { ... }

It's workable, if a bit ugly. You can also define type constructor composition and other toys this way, then go nuts with type-level points-free expressions buried under a pile of hoop-jumping boilerplate.

As a final approach, you can also encode the lambda-style approach above "in reverse", going from the fully-applied version, to the single type parameter:

class Listable t where
    type ListableElem t :: *
    asList :: t -> [ListableElem t]

Being able to do this sort of thing is one of the main motivations for type families. The same thing can be expressed with MPTCs and fundeps, but it's 1) equivalent and 2) much uglier, so I won't bother writing it out.

like image 193
C. A. McCann Avatar answered Oct 15 '22 02:10

C. A. McCann


You have to define some wrapper type to do this. (You should use newtype however.) You might even define:

newtype Foo t a = Foo(t a a)

instance Listable (Foo (,)) where
   asList (Foo (a,b)) = [a,b]
like image 43
ysdx Avatar answered Oct 15 '22 01:10

ysdx