An Introduction to Type Families

2017-06-21
haskell

Review

Before discussing type families, we need to review type synonyms, type classes, multi-parameter type classes and functional dependencies.

Type synonyms

Type synonyms are a form of syntactic sugar. They allow us to give a new name to an existing type. You can treat them as the same as the original type. They are useful annotations for the programmer, but they can be ignored by the compiler.

Type classes

Type classes allow us to put constraints on polymorphic type parameters. For example, the print function from base puts a constraint on the its polymorphic type variable.

We can read it is as print accepts any type a that has an instance of the Show type class. The compiler will reject any a that does not have an instance of Show. When we make an instance of a type class for a type, we overload the operations associated with that particular type class. In this case Show is expecting a type of kind *.

Type classes can also support higher-kinded types such as * -> *.

While * -> * is not explicitly stated, the f occurs on the left hand side of a type variable, the compiler can infer that f is a type of kind * -> *.

In Haskell, type class instances are global, import any file with a type class instance and that instance is automatically propagated to all other files importing it. Then, for any function requiring a type class, the instance are implicitly used. One type cannot have multiple instances of a single type class.

Multi-parameter type classes

By default, Haskell 2010 does not support multi-parameter type classes. We need to add the language pragma {-# LANGUAGE MultiParamTypeClasses #-} to enable them.

We will often need {-# LANGUAGE FlexibleInstances #-} to handle Multi-parameter type classes when we want to add more restrictions to instances.

Type classes are a set of types. Multi-parameter type classes is a relationship between types.

Functional dependencies

Because multi-parameter type classes may introduce ambiguity. We need {-# LANGUAGE FunctionalDependencies #-} to constrain the parameters of type classes.

The right hand side of the class declaration | a b -> c states that c’s type is determined by a and b. For any given a and b you can only have one c. c should not be a free variable, it is determined by the other two variables.

Here is general container type class using functional dependencies.

Type Families

With type classes, we can associate the set of functions from a type class with a type. Type families allow us to associate types with a type. They define partial functions from types to types by pattern matching on input types. Type families are type-indexed data types and name functions on types. The data types and functions are retrieved by the types provided.

Type families come in three variations:

  • data families
  • open type synonym families
  • closed type synonym families

Data Family

Data family type families create a new data type. They restrict the codomain and require each instance to define a new type constructor for the function’s result.

They can be declared at the top level, with or without kind declaration.

Or they can be declared within a class. These are known as associated types.

An array example with an associated type.

Type Synonym Families

Type synonym families permit types in the codomain of the type function to be any type with the appropriate kind.

Open type families are declared at the top level.

We can close a type synonym family by adding a where clause. Also, it guarantees that the associated functions will be tried in order of declaration.

Examples

A general concat type family can be used to concat different types. You must decide what the resulting type is for any pair of types.

A general container type family.

What to Remember About Type Families

  • Data families create new types, every instance of a data family declares new constructors.

  • Type families can only refer to other existing types.

References