Closed Type Classes

You know how in Haskell there are functions? These things that transform values into other values? Yeah, we have that on the type level as well. These are called type families, and they transform types into other types.

The main difference: Type families actually exist in two variants!

Closed type families are defined by pattern matching, just like regular value-level functions.

Open type families on the other hand are a bit different. These are declared without definitions and individual instances can be added anywhere the type family is in scope, even across module boundaries.

But the title of this post doesn’t say families, does it? So what does this have to do with type classes?

While type classes are usually seen as defining behavior for classes of types, an alternative interpretation is to view them as functions from types to values. After all, Show is really just a way to go from a type a to a function a -> String.

But type classes in Haskell are always open! We can visualize this as a table

There is no fundamental reason why there shouldn’t be anything in that ??? corner!

In fact, closed type classes that are able to pattern match on types would avoid quite a few of the drawbacks of globally coherent instances and would dramatically simplify Type Class Metaprogramming.

To take an example from that blog post, let’s implement a generalized version of concat, that flattens arbitrarily deeply nested lists.

(In Polaris syntax)

type ElementOf(a) = {
    List(List(a)) -> ElementOf(List(a))
    List(a) -> a
}

class flatten(a) : a -> List(ElementOf(a))
class flatten = {
    [[a]] -> \list -> flatten(concat(list))
    [a] -> \x -> x
}

print(flatten([[[1, 2], [3]]], [[4]]))
# [1, 2, 3, 4]

Note that flatten is lowercase because it directly defines a function.

Compared to the same in Haskell, I think this is pretty nice!

type family ElementOf a where
  ElementOf [[a]] = ElementOf [a]
  ElementOf [a]   = a

class Flatten a where
  flatten :: a -> [ElementOf a]

instance Flatten [a] where
  flatten x = x

instance {-# OVERLAPPING #-} Flatten [a] => Flatten [[a]] where
  flatten x = flatten (concat x)

On the implementation side, this would be implemented exactly like regular type classes. Just the instance selection mechanism would be a bit different. flatten would be desugared to something like this:

type FlattenDict(a) = a ->  List(ElementOf(a))

let flattenListList : (FlattenDict(List(a))) ->  (List(List(a)) -> List(a))
let flattenListList(listADict) = \list -> listADict(concat(list))

let flattenSingleList : List(a) -> List(a)
let flattenSingleList(x) = x

print(flattenListList(flattenListList(flattenSingleList)))([[[1, 2], [3]]], [[4]]))

If you have seen something similar before, or if there is anything dramatically problematic about this that I missed, please let me know :)