Extensible Data Types based on Associated Types
Algebraic data types are notorically hard to extend. To see why, consider the following declarations:
data Bird = Duck | Emu | Seagull canFly :: Bird -> Bool canFly Duck = True canFly Emu = False canFly Seagull = True
It is hard to add another bird, such as Penguin, not only because the definition of the data type would have to be extended, but especially because all functions that consume this data type, such as canFly, need to be extended, too. Obvious attempts to solve the problem, such as requiring a default case, all have serious drawbacks.
In case we know a priori that we might want to extend a data type, we can define it such that it is more flexible.
data Bird ext = Duck | Emu | Seagull | Other ext
However, this requires to define all functions with more foresight, too.
canFly :: (ext -> Bool) -> Bird -> Bool canFly canOtherFly Duck = True canFly canOtherFly Emu = False canFly canOtherFly Seagull = True canFly canOtherFly (Other ext) = canOtherFly ext
At least, we can now define
data OtherBird = Penguin -- This could of course have more than one alternative type ExtBird = Bird OtherBird otherCanFly :: OtherBird -> Bool otherCanFly Penguin = False extCanFly :: ExtBird -> Bool extCanFly = canFly otherCanFly
If all functions that use canFly accept the canOtherFly argument, we can use them on the extended data type without modification, simply by passing in otherCanFly.
This approach certainly has a number of drawbacks. Firstly, explicitly threading the additional argument to canFly through all functions that directly or indirectly use canFly is tedious to begin with, but if we have multiple extensible data types, it can quickly get impractical. Secondly, we might want to extend a data type multiple times; i.e., we might modify the definition of OtherBird to also get an extra type parameter to plug in an another extension. This makes the explicit threading of the extra arguments a notch more tedious. Thirdly, we have to prepare a data type and all its consuming functions suitably to be extensible.
We can not hope to overcome the third point as long as we want to have both standard data types and extensible data types. Having only extensible data types has clear disadvantages as long as they are more work to define and use then vanilla data types. Moreover, they might also be undesirable for formally reasoning about programs. Nevertheless, we might hope to eliminate the first two drawbacks.
Using Associated Types
The above example can be implemented as follows with associated types:
class Birds a where data Bird a canFly :: Bird a -> Bool data Std instance Birds Std where data Bird Std = Duck | Emu | Seagull canFly Duck = True canFly Emu = False canFly Seagull = True
We can extend the Bird data type and all class methods consuming that type by simply adding more instances, such as
data Other instance Birds Other where data Bird Other = Penguin canFly Penguin = False
Here the explicit threading of the manual method to extensible data types is replaced by the dictionary passing mechanism used by the compiler to implement type classes. Moreover, multiple extensions of one data type require no additional work from the programmer. However, we still need to decide a priori whether to define the data type in this manner and we need to put all functions over the data type that we like to be extensible into the class definition. (We'll come back to that last point below.) In essence, we collect all data types whose variants we want to be alternatives for each other into one indexed type family.
Whether functions using methods, such as canFly work transparently in the face of extensions depends on their signature. The following function will obviously only work for standard birds:
swimsAndFlys :: Bird Std -> Bool swimsAndFlys Duck = canFly Duck swimsAndFlys Emu = False swimsAndFlys Seagull = canFly Seagull
In contrast, the next function works fine for any bird we ever include in the class:
tooFatToFly :: Birds a => Bird a -> Bool tooFatToFly bird = not . canFly
Caveat: We cannot easily put the (extended) elements of a data type into a homogenous structure, such as a list; so, [Emu, Penguin] leads to a type error, as it would require Bird Std and Bird Other to unify. Note that, when using the manual encoding outlined initially, [Emu, Penguin] would be ill-typed, too, but [Emu, Other Penguin] would be fine.
It is well known that algebraic data types in functional languages and classes in OO languages have orthogonal extension properties. In a functional language, it is easy to add a new function scrutinising a data type, but hard to add a new variant. In an OO language, it is easy to add a new variant (i.e., instance) to a class, but hard to add a new member function.
Interestingly, our proposed solution to extensible data types based on associated types inherits the properties of OO languages that we can easily add new variants, but have a closed set of class methods operating on these variants. Functions defined outside the class can operate on the variants defined in one instance (such as swimsAndFlys) above, but not on variants spanning multiple instances.
Type Classes with Existential Types
SeanSeefried rightly points out that we can achieve a very similar encoding with a combination of existential types and type classes using an encoding suggested by Konstantin Läufer. The basic definition would be
class Birds a where canFly :: a -> Bool data BIRD = forall a.Birds a => MakeBird a instance Birds BIRD where canFly (MakeBird b) = canFly b data Bird = Duck | Emu | Seagull instance Birds Bird where canFly Duck = True canFly Emu = False canFly Seagull = True
Now, we can extend this with
data ExtBird = Penguin instance Birds ExtBird where canFly _ = False
This leads to the question of what the difference between the associated types and the existential types solution is. There seem to be two main differences:
the denotation of the encoded type family and
the impact on compiler optimisations.
In the associated types variant, the type family is denoted Bird a and its members are obtained by suitable instantiation of the type variable a; i.e., we get Bird Std and Bird Other. In the variant using existential types, the type family is denoted BIRD and its members are Bird and ExtBird. More precisely, with associated types, the family/family-member relationship is embedded in the type structure as it corresponds to type variable instantation. However, with existential types that relationship is a meta property of the program that is not reflected in the type structure (i.e., apart from a suitable choice of identifiers the denotation of the family and it's members bears no resemblence). In other words, associated types allow a deep encoding of type families, whereas the encoding with existantial types is shallow.
The disadvantage of the shallow encoding is that we have to coerce between values of the type family BIRD and its members Bird and ExtBird by adding or stripping the data constructor MakeBird. That's not required for the associated types encoding. Nevtherless, the shallow encoding also has an advantage. We can easily compile a homogenous list from an arbitrary collection of BIRDs, we can't do that with the associated type Bird a. Which of this is a more serious concern probably depends on the requirements of the concrete application.
The construction of the data type BIRD (in the existential types variant) uses a type context, namely Birds a on the existential type. In terms of the implementation, this means that the dictionary representing instances of Birds at runtime will be included into every value of that type. If such a value is decomposed - by pattern matching on MakeBird (as done in the BIRD instance of Birds) - it is this dictionary which is used when class methods are applied to the value embedded in MakeBird. This means that any optimisations that the compiler performs to use type specialisation to eliminate the overhead of dictionary passing will be in vain for values embedded in MakeBird. This is not the case when associated types are used, but whether that's a concern will again depend on the concrete application.
Please email comments to Manuel Chakravarty. [Last update 16 Feb 5]