Closed Type Classes
22 March 2023You 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
Open | Closed | |
---|---|---|
Value -> Value | Open function (not in Haskell) | Function |
Type -> Type | Open type family | Closed type family |
Type -> Value | Type class | ??? |
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
= x
flatten x
instance {-# OVERLAPPING #-} Flatten [a] => Flatten [[a]] where
= flatten (concat x) flatten 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 :)