Thursday, 30 October 2008

2 Minute intro to Associated Types / Type Families

Type Families are an important recent addition to GHC which have been developed over the past couple of years (and indeed are still being developed). They promise to address some of the same issues addressed by functional dependencies whilst avoiding some of the nastier corner cases and allowing for a more solid theoretical underpinning and implementation.

There is a lot of material available on Type Families, in fact it seemed somewhat bewildering to me initially. There doesn't seem to be an "idiot's guide" overview - so that's what this post attempts to do - to provide a just enough background to help you work out which papers etc you want to read next.

Terminology and Syntax

The thing to note is that there are essentially four different concepts, each of which have a couple of different terms for them:

Associated (Data) Type
class ArrayElem e where
data Array e
index :: Array e -> Int -> e

instance ArrayElem Int where
data Array Int = IntArray UIntArr
index (IntArray a) i = ...
Associated (Type) Synonym
class Collection c where
type Elem c
insert :: Elem c -> c -> c

instance Eq e => Collection [e] where
type Elem [e] = e
Data (Type) Family
data family Array e

data instance Array Int = IntArray UIntArr

data instance Array Char = MyCharArray a b
(Type) Synonym Family
type family Elem c

type instance Elem [e] = e

type instance Elem BitSet = Char

Associated or Family?

The first "axis" of categorization is "Associated" vs "Family". The "Associated ..." variants (which were invented first) are those which are declared inside a standard typeclass declaration, the "... Family" variants are stand-alone, top-level, use the "family" keyword and were invented a year or so later. The Family variants (collectively known as Type Families) are strict generalizations of the associated ones, and the associated ones are simple syntactic sugar for the family variants.

Data or Type Synonym?

The other "axis" of categorization is "Data" vs "Type Synonym". This distinction mirrors that of normal Haskell "data" and "type" declarations. The key point is that associated data types and data families let you create a bijection (ie one-to-one mapping) from source type to destination type. Associated type synonyms and synonym families on the other hand allow you to map two different souce types onto the same destination type. The best reference for more details on the difference is the first part of section 7 of the "Associated Type Synonyms" paper.

Equality Constraints
The final piece of syntax allows us to assert type-level equalities using the above:

sumCollection :: (Collection c, Elem c ~ Int) => c -> Int
sumCollection c = sum (toList c)

This (as with the other examples) is slightly modified from one of the papers - in this case the "Associated Type Synonyms" paper where the syntax uses "=" rather than the "~" which was ultimately used.

Many of the above features are actually available in the GHC 6.8 branch but they are only really supported under 6.10 onwards. (I understand that the main reason the code is in 6.8 at all is to facilitate merging of other, unrelated fixes between those branches). I've had success with both kinds of associated types under 6.8 but ran into problems using equality constraints.


Dean Michael said...

Nice write-up. I'm not a Haskell programmer but I am a C++ developer -- that being said what you've written here is very close (if not exactly comparable) to Concepts in the next C++ standard (C++0x).

Ben said...

Thanks for the pointer Dean - I'll have to take a look at them.

Fritz Ruehr said...

You can read a detailed comparison of C+ concepts and Haskll type classes (with associated types, etc.) in the paper "Concepts =? Type Classes" by Jean-Philippe Bernardy, Patrik Jansson, Marcin Zalewski, Sibylle Schupp and Andreas Priesnitz, which was presented at the Workshop on Generic Programming this year (WGP 08).

See the paper archived at Chalmers.

Peter Marks said...

Thanks Ben, finally found a few minutes to read this :-). Still not clear on how functional dependencies map to this stuff. Care to elaborate in a future post?

xiaoxu said...

Articles are meaningful, and your blog is nice!
polo jacket
polo shirt
ralp lauren jacket
cheap polo shirts
spyder jackets
discount polo shirts
ralph lauren shirt
columbia jacket
north face jacket
cheap ralph lauren shirts
women's columbia jackets
polo t shirts
polo men's shirt
ralph lauren men's shirt
polo mens shirt
cheap polo jackets
ralph lauren mens shirt
wholesale polo jacket
ralp lauren polo shirts
short sleeve polo shirt
men polo shirt
lacoste polo shirts
wholesale polo shirts
men's polo shirts
cheap polo ralph lauren
cheap polo t-shirts
cheap polo clothes
custom polo shirts
discount north face jackets
ladies spyder jacket
tennis rackets
tennis racket
tennis racquet
tennis racquets
wilson tennis rackets
prince tennis rackets
head tennis rackets
babolat tennis rackets
best tennis racket
cheap tennis rackets
wilson tennis racquets
head tennis racquets
babolat tennis racquets
cheap tennis racket

Bayan Ankara Escort said...

Ankara Escort, Escort Ankara, Escort Ankara Bayan
Escort Ankara, Escort Ankara Bayan, Ankara Escort Bayan
Bayan Ankara Escort, Ankara Bayan Escort, Ankara Escort Kızlar
Escort Kızlar Ankara, Escort Bayan Ankara, Escort Bayanlar Ankara
Escort Bayanlar Ankara, Ankara Bayan Escortlar, Ankara Eskort Bayan
Escort Kızlar Ankara, Ankara Escort Kadınlar, Ankara Eskort Bayanlar
Ankarada Tele Kızlar, Ankara Escort Kızlar, Ankara Eskort Bayan
Bursa Escort, Bayan Escort Bursa, Bursa Eskort Bayan
Kayseri Escort, Bayan Escort Kayseri, Kayseri Eskort Bayan
Escort Bayan Ankara
Escort Bayan
Escort Ankara
Escort Ankara Bayan

Escort Bayan Ankara,
Escort Bayan,
Ankara Escort,
Ankara Escort Bayan,
Escort Bayan Ankara,
Escort Bayan,
Escort Ankara Bayan,
Ankara Escort,
Ankara Escort Bayan,
Escort Bayan Ankara
Ankara Escort Bayan
Escort Ankara
Bayan Ankara Escort
Escort Ankara
Escort Bursa
Escort Ankara Bayan
Ankara Escort Bayan
Escort Bayan Ankara

Amy de Buitléir said...

I have this post bookmarked, and I have referred to it dozens of times over the past year. Thank you for clarifying this subject for me.

Jaya Mittal said...

Goa Excellent Escorts Agency has a great site for that guys who want different services related to foreigners or Indian all type escorts girls. We provide you best offer of the beauty and good-looking Goa Escorts. Our girls are presenting to all gentlemen maximum and full secure moment. If guys you are looking for a beautiful Escorts in Goa, then girls are waiting to meeting with you.

Checkout our Links Partners:- Jaipur Escorts Hyderabad Escorts Mumbai Escorts Mumbai Escorts Mumbai Escorts Mumbai Escorts Mumbai Escorts Mumbai Escorts Mumbai Escorts

jayamittal5 said...

Welcome to this young and newest Escorts Agency. We start this escorts agency in the last month of 2014 it develops the centre of visitors from all over India. All gentlemen who belong to other cities join this models escorts agency here and get entertainment only entertainment.

Bangalore Escorts
Bangalore Escorts Agency
Bangalore Escorts Services
Independent Bangalore Escorts
Escorts in Bangalore
Independent Escorts in Bangalore
Bangalore Escorts Girls
Bangalore Escort

Kolkata Escorts
Kolkata Escorts Agency
Kolkata Escorts Services
Independent Kolkata Escorts
Escorts in Kolkata
Independent Escorts in Kolkata
Kolkata Escorts Girls
Kolkata Escort

Chennai Escorts
Chennai Escorts Agency
Chennai Escorts Services
Independent Chennai Escorts
Escorts in Chennai
Independent Escorts in Chennai
Chennai Escorts Girls
Chennai Escort

Escorts services in Chennai
Chennai Escorts
Chennai Escorts Agency
Chennai Escorts Services
Independent Chennai Escorts
Escorts in Chennai
Independent Escorts in Chennai
Chennai Escorts Girls
Chennai Escort