– or, “The mother of all type classes”

In “Scrap your type
classes”
Gabriel Gonzalez explains how we can replace type classes with
dictionary passing. In this article I describe a sort of “halfway
house” to scrapping *all* our type classes. Suppose we were only
allowed one type class. Which would we choose? I’ll explain how we
can get (almost) all of the benefits of all type classes with only a
single type class, the “mother of all type classes” (in homage to Dan
Piponi).

We need some uncontroversial language extensions.

```
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE ScopedTypeVariables #-}
```

and then we can present the “mother of all type classes”, called
`Class`

.

```
class Class (f :: k -> *) (a :: k) where
classD :: f a
```

How does this allow us to replace all type classes? Where we previously had

`instance MyClass a where ...`

we will replace it with

`instance Class MyClassD a where ...`

where `MyClassD`

is the type class dictionary that Gabriel
explained to
us.
Let’s implement `Show`

using `Class`

. Firstly we define the
dictionary.

`newtype ShowD a = ShowD { showD :: a -> String }`

and our instance definition fills in the missing operations, for
example for `Int`

and `[Char]`

.

```
instance Class ShowD Int where
= ShowD { showD = show }
classD
instance Class ShowD [Char] where
= ShowD { showD = show } classD
```

(These definitions look circular because they use `show`

. Although
I’m supposed to be showing your how to *implement* `show`

using
`Class`

these definitions are not circular. I’m only using the
prexisting `show`

out of laziness. In a “real” implementation a
library author would fill in the actual body of `show`

.)

Then we can define a type class polymorphic `show`

function

```
showC :: Class ShowD a => a -> String
= showD classD showC
```

and it works just like we would expect

```
> showC (1 :: Int)
"1"
> showC "Hello"
"\"Hello\""
```

Our familiar `Show`

takes a parameter of kind `*`

. Can we do higher
kinded type parameters? Yes, because I carefully defined `Class`

to
be kind polymorphic. Note that in its definition `a :: k`

. How
about `Functor`

then? Again, convert the `Functor`

operations to a
dictionary, fill in the implementation in the instances, and define a
type class polymorphic `fmapC`

.

```
newtype FunctorD f =
FunctorD { fmapD :: forall a b. (a -> b) -> f a -> f b }
instance Class FunctorD Maybe where
= FunctorD { fmapD = \f x -> case x of
classD Nothing -> Nothing
Just x -> Just (f x)
}
instance Class FunctorD [] where
= FunctorD { fmapD = \f x -> case x of
classD -> []
[] :xs) -> f x : fmapD classD f xs
(x
}
fmapC :: Class FunctorD f => (a -> b) -> f a -> f b
= fmapD classD fmapC
```

It works as we expect

```
-- > fmapC (*10) (Just 1)
-- Just 10
-- > fmapC (*10) [1..4]
-- [10,20,30,40]
```

`Show`

and `Functor`

are single parameter type classes. Can we do
*multi*parameter type classes? Yes, by using a type level tuple as the
type parameter. For example, if I want to convert the multiparameter
type class

```
class Set s e where
insert :: s -> e -> s
contains :: s -> e -> Bool
```

to the “mother of all type classes” setup then I can define a dictionary with a type level tuple parameter by using a GADT.

```
data SetD a where
SetD :: (s -> e -> s)
-> (s -> e -> Bool)
-> SetD '(s, e)
```

Then everything proceeds as for `Show`

and `Functor`

, modulo some
ceremony regarding unwrapping the GADT.

```
instance Class SetD '([Int], Int) where
= SetD (\s e -> e:s) (\s e -> e `elem` s)
classD
insertC :: forall s e. Class SetD '(s, e) => s -> e -> s
= case classD' of SetD insert _ -> insert
insertC where classD' = classD :: SetD '(s, e)
containsC :: forall s e. Class SetD '(s, e) => s -> e -> Bool
= case classD' of SetD _ contains -> contains
containsC where classD' = classD :: SetD '(s, e)
```

```
-- > insertC [2 :: Int,3,4] (10 :: Int)
-- [10,2,3,4]
```

We have to give type annotations when we use `insertC`

but that’s due
to `Num`

being type class polymorphic and there being no functional
dependency between `s`

and `e`

. That raises a question. Can we
encode functional dependencies in the “mother of all typeclasses”
`Class`

formulation? No, I don’t see how. I also do not see how we
can have associated types or data.

I haven’t found any other work that presents quite the same
formulation as `Class`

as presented above. I would be grateful to
receive any links to such work. However, a similar scheme was
proposed by John Hughes in Restricted Data Types in
Haskell
and borrowed by Ralf Lammel and Simon Peyton Jones in Scrap your
boilerplate with class: extensible generic
functions.
Hughes introduced the class

```
class Sat t where
dict :: t
```

Is the `Sat`

approach equivalent to the `Class`

approach? Let’s consider a
concrete example. Is

`instance Sat (FunctorD Maybe)`

equivalent to

`instance Class FunctorD Maybe`

No, because `Class FunctorD`

is genuinely something of kind `(* -> *) -> Constraint`

just like `Functor`

is. If I replaced the `Prelude`

definition of `Functor`

with

`type Functor = Class FunctorD`

then I would expect all of Haskell to still work the same. There’s no
way of replacing `Functor`

with `Sat (FunctorD Maybe)`

because the
latter has an insufficiently general type. Still, perhaps a parallel
universe Haskell ecosystem could use the latter quite happily. What
could go wrong? I can’t think of any obvious examples but advanced
`Constraint`

tricks might not be possible.

Oleg Kiselyov published a similar idea in 2007. I present a slight paraphrasing of Oleg’s most refined version. It looks quite similar to the above.

```
class C l t | l -> t where
ac :: l -> t
data NUM a = NUM { nm_add :: a -> a -> a,
nm_mul :: a -> a -> a,
nm_fromInteger :: Integer -> a,
nm_show :: a -> String
}
data CLS a
instance C (CLS (NUM Int)) (NUM Int) where
= NUM (+) (*) fromInteger show ac _
```

Let’s try and refine it further. Firstly we notice that we’re always going to define instances of the form

`instance C (CLS (f a)) (f a) where`

so we may as well drop the second type parameter and use

```
class C t where
ac :: CLS t -> t
instance C (f a) where
...
```

Then we notice that we don’t need the first, phantom, argument to `ac`

any more. Oleg only introduced it to disambiguate instances. With
the record-based approach the type constructor of the record is
sufficient to disambiguate instances, so we can get away with merely

```
class C t where
ac :: t
instance C (f a) where
...
```

which is equivalent to `Sat`

above.

You can “scrap all your type classes but one” and use the “mother of all typeclasses instead”. I’m not suggesting you actually do this but I do think it’s very interesting. It remains to be seen how to fit functional dependencies and associated types and data into this scheme.

Thanks to `rpglover64`

and
`vaibhavsagar`

for
pointing out typos.