Personal tools

OOP vs type classes

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Removed misleading information on C#/Java generics)
 
(19 intermediate revisions by 14 users not shown)
Line 1: Line 1:
(this is just a sketch now. feel free to edit/comment it. i will include information you provided into the final version of this tutorial)
+
(this is just a sketch now. feel free to edit/comment it. I will include information you provided into the final version of this tutorial)
   
   
I'm almost not used type classes in my application programs, but when
+
I had generally not used type classes in my application programs, but when
I'd gone to implement general-purpose libraries and tried to maintain
+
I'd gone to implement general purpose libraries and tried to maintain
as much flexibility as possible, it was natural to start build large
+
as much flexibility as possible, it was natural to start building large
 
and complex class hierarchies. I tried to use my C++ experience when
 
and complex class hierarchies. I tried to use my C++ experience when
doing this but I was many times bitten by the type classes
+
doing this but I was bitten many times by the restrictions of type classes. After this experience, I think that I now have a better feeling and mind model
restrictions. Now I think that I have better feeling and mind model
+
for type classes and I want to share it with other Haskellers -
for type classes and want to share it with other Haskellers,
 
 
especially ones having OOP backgrounds.
 
especially ones having OOP backgrounds.
   
Brian Hulley provided us the program that emulates OOP in Haskell - as
+
Brian Hulley provided us with the program that emulates OOP in Haskell - as
you can see, it's much larger than equivalent C++ program. Equivalent
+
you can see, it's much larger than equivalent C++ program. An equivalent translation from Haskell to C++ should be even longer :)
Haskell to C++ translation should be even longer :)
 
   
   
== Everything is object? ==
+
== Everything is an object? ==
   
You all know this OOP motto - "everything is object". While I program in
+
Most software developers are familiar with the OOP motto "everything is an object." People accustomed to C++ classes often find the Haskell concept of type classes difficult to grasp. Why is it so different?
C++, it was really hard to do it without classes. But when I, the same
 
John de Mac-Lee programmer, use Haskell, it's hard to find open
 
vacancies for type classes. Why it is so much difference?
 
   
C++ classes pack functions together with data and make it possible to
+
C++ classes pack functions together with data, which makes it convenient to
use different data representations via the same interface. As long as
+
represent and consume data. Use of interfaces (abstract classes) allow classes to interact by contract, instead of directly manipulating the data in the other class. There exist alternative ways in C++ to accomplish such functionality (function pointers, discriminated unions), yet these techniques are not as handy
you need any of these facilities, you are forced to use classes.
+
as classes. Classes are also the primary way to hiding implementation
Although C++ supports alternative ways to implement such functionality
+
details. Moreover, classes represent a handy way to group related
(function pointers, discriminated unions), these are not so damn handy
+
functionality together. It's extremely useful to browse the structure of large C++ project in terms of classes instead of individual functions.
as classes. Classes also the sole method to hide implementation
 
details. Moreover, classes represent handy way to group related
 
functionality together, so i found myself sometimes developing class
 
containing only static functions just to group them into some
 
'package'. It's damn useful to browse structure of large C++ project
 
in terms of classes instead of individual functions.
 
   
But Haskell provides another solutions for all these problems.
+
Haskell provides other solutions for these problems.
   
 
=== Type with several representations: use algebraic data type (ADT) ===
 
=== Type with several representations: use algebraic data type (ADT) ===
   
 
For the types with different representations, algebraic data types
 
For the types with different representations, algebraic data types
(ADT), an analog of discriminated unions, are supported:
+
(ADT) - an analog of discriminated unions - are supported:
   
 
<haskell>
 
<haskell>
Line 36: Line 36:
 
</haskell>
 
</haskell>
   
Haskell provides very easy way to build/analyze them:
+
Haskell provides a very easy way to build/analyze them:
   
 
<haskell>
 
<haskell>
Line 47: Line 47:
 
</haskell>
 
</haskell>
   
So ADTs in general are preferred in Haskell over the type class-based
+
So ADTs in general are preferred in Haskell over the class-based
 
solution of the same problem:
 
solution of the same problem:
   
Line 64: Line 64:
   
   
You can also imagine all the C++ machinery what is required to implement
+
The equivalent C++ implementation using inheritance requires much more machinery than our 5 line, ADT-based solution. This also illustrates a Haskell benefit--it's much easier to define types/functions. Perhaps objects are not as great as you thought before. :D
analog of our 5 lines ADT-based solution to say that objects are not
+
so great as you thought before :D Of course, C++ classes are usually
 
much larger but that's again Haskell benefit - it's so easy to define
 
types/functions that you may use much finer granularity.
 
   
 
<pre>
 
<pre>
Line 71: Line 71:
 
#include <iostream>
 
#include <iostream>
 
using namespace std;
 
using namespace std;
  +
  +
ostream & operator<<(ostream & lhs, pair<float, float> const& rhs) {
  +
return lhs << "(" << rhs.first << "," << rhs.second << ")";
  +
}
   
 
struct Point {
 
struct Point {
pair<float,float> coord();
+
virtual pair<float,float> coord() = 0;
 
};
 
};
   
 
struct FloatPoint : Point {
 
struct FloatPoint : Point {
 
float x, y;
 
float x, y;
FloatPoint (float _x, float _y) { x=_x; y=_y; }
+
FloatPoint (float _x, float _y) : x(_x), y(_y) {}
pair<float,float> coord() { return make_pair(x,y); }
+
pair<float,float> coord() {return make_pair(x,y); }
 
};
 
};
   
 
struct IntPoint : Point {
 
struct IntPoint : Point {
 
int x, y;
 
int x, y;
IntPoint (int _x, int _y) { x=_x; y=_y; }
+
IntPoint (int _x, int _y) : x(_x), y(_y) {}
pair<float,float> coord() { return make_pair(x,y); }
+
pair<float,float> coord() { return make_pair(x,y); }
 
};
 
};
   
main () {
+
int main () {
 
cout << FloatPoint(1,2).coord();
 
cout << FloatPoint(1,2).coord();
 
cout << IntPoint(1,2).coord();
 
cout << IntPoint(1,2).coord();
  +
return 0;
 
}
 
}
 
</pre>
 
</pre>
   
As you see, ADTs together with type inference makes Haskell program
+
As you see, ADTs together with type inference make Haskell programs
about 2 times smaller than its C++ equivalent.
+
about 2 times smaller than their C++ equivalent.
   
   
 
=== Packing data & functions together: use (records of) closures ===
 
=== Packing data & functions together: use (records of) closures ===
   
Another very typical classes usage is to pack data together with one
+
Another typical class use-case is to pack data together with one
or more functions to proceed them and pass this bunch to some
+
or more processing functions and pass this bunch to some
function. Then this function can call these functions to implement
+
function. Then this function can call the aforementioned functions to implement
some functionality and don't bother how it is internally implemented.
+
some functionality, not bothering how it is implemented internally.
Hopefully Haskell provides better way to implement this - you can
+
Hopefully Haskell provides a better way: you can pass any functions as parameters to other functions directly.
directly pass any functions as parameters to other functions.
+
Moreover, such functions can be constructed on-the-fly, capturing free variables in context, creating the so-called closures. In this way, you construct something like object on-demand and don't even need a type class:
Moreover, you can construct passed functions on-the-fly and capture in
 
these definitions values of identifiers available at the call place,
 
creating so-called closures. In this way, you construct something like
 
object on-the-fly and don't even need a type class:
 
   
 
<haskell>
 
<haskell>
Line 112: Line 117:
 
</haskell>
 
</haskell>
   
Here, we passed to proc two routines - one that increments value of
+
Here, we applied proc to two functions - one incrementing the value of a
counter and another that reads its current value. Another call to proc
+
counter and another reading its current value. Another call to proc
that uses counter with locking, might look as:
+
that uses counter with locking, might look like this:
   
 
<haskell>
 
<haskell>
Line 131: Line 136:
 
i.e. it receive two abstract operations whose implementation may vary
 
i.e. it receive two abstract operations whose implementation may vary
 
in different calls to proc and call them without any knowledge of
 
in different calls to proc and call them without any knowledge of
implementation details. The equivalent C++ code look as:
+
implementation details. The equivalent C++ code could look like this:
   
 
<pre>
 
<pre>
struct Counter {
+
class Counter {
void inc();
+
public:
int read();
+
virtual void inc() = 0;
  +
virtual int read() = 0;
 
};
 
};
   
struct SimpleCounter : Counter {
+
class SimpleCounter : public Counter {
int n;
+
public:
SimpleCounter () { n=0; }
+
SimpleCounter() { n = 0; }
 
void inc() { n++; }
 
void inc() { n++; }
 
int read() { return n; }
 
int read() { return n; }
  +
private:
  +
int n;
 
};
 
};
   
void proc (Counter c) {
+
void proc (Counter &c) {
 
c.inc(); c.inc(); c.inc(); cout << c.read();
 
c.inc(); c.inc(); c.inc(); cout << c.read();
 
}
 
}
 
</pre>
 
</pre>
   
And again, Haskell code is much more simple and straightforward - we
+
And again, Haskell code is much simpler and more straightforward - we
 
don't need to declare classes, operations, their types - we just pass
 
don't need to declare classes, operations, their types - we just pass
to the proc implementation of operations it need. Look at
+
to the proc implementation of operations it needs. Look at
http://haskell.org/haskellwiki/IO_inside#Example:_returning_an_IO_action_as_a_result
+
[[IO inside#Example: returning an IO action as a result]]
 
and following sections to find more examples of using closures instead
 
and following sections to find more examples of using closures instead
 
of OOP classes.
 
of OOP classes.
 
   
 
=== Hiding implementation details: use module export list ===
 
=== Hiding implementation details: use module export list ===
Line 164: Line 170:
 
internal data/functions inaccessible to class clients. Unfortunately, this
 
internal data/functions inaccessible to class clients. Unfortunately, this
 
functionality is not part of type class facilities. Instead, you
 
functionality is not part of type class facilities. Instead, you
should use the sole Haskell method of implementation hiding - module
+
should use the sole Haskell method of encapsulation, module
 
export list:
 
export list:
   
Line 180: Line 186:
   
 
Since the constructor for the data type Stack is hidden (the export
 
Since the constructor for the data type Stack is hidden (the export
list would say Stack(Stk) if it were exposed), outside of this module
+
list would say Stack(Stk) if it were exposed), outside of this module a stack can only be built from operations empty, push and pop, and
a stack can only be built from operations empty, push and pop, and
 
 
examined with top and isEmpty.
 
examined with top and isEmpty.
   
Line 186: Line 192:
 
=== Grouping related functionality: use module hierarchy and Haddock markup ===
 
=== Grouping related functionality: use module hierarchy and Haddock markup ===
   
Dividing whole program into classes and using their hierarchy to
+
Dividing a whole program into classes and using their hierarchy to
represent entire program structure is a great instrument for OOP
+
represent entire an program structure is a great instrument for OO languages. Unfortunately, it's again impossible in Haskell. Instead,
languages. Unfortunately, it's again impossible in Haskell. Instead,
+
the structure of a program is typically rendered in a module hierarchy and inside
program structure typically rendered in module hierarchy and inside
+
a module - in its export list. Although Haskell doesn't provide
module - in its export list. Although Haskell language don't provide
+
facilities to describe a hierarchical structure inside of a module, we have
facilities to describe hierarchical structure inside of module, we had
 
 
another tool to do it - Haddock, a de-facto standard documentation tool.
 
another tool to do it - Haddock, a de-facto standard documentation tool.
   
Line 217: Line 223:
 
</haskell>
 
</haskell>
   
Here, Haddock will build documentation for module looking at its
+
Here, Haddock will build documentation for a module using its export list. The export list will be divided into sections (whose
export list. The export list will be divided into sections (whose
 
 
headers given with "-- *") and subsections (given with "-- **"). As
 
headers given with "-- *") and subsections (given with "-- **"). As
the result, module documentation reflect its structure without using
+
a result, module documentation reflects its structure without using
 
classes for this purpose.
 
classes for this purpose.
 
   
 
== Type classes is a sort of templates, not classes ==
 
== Type classes is a sort of templates, not classes ==
   
At this moment C++/C#/Java languages has classes and
+
At this moment, C++ has classes and
templates/generics. What is a difference? With a class, type
+
templates. What is the difference? With a class, type
information carried with object itself while with templates it's
+
information is carried with the object itself while with templates it's
outside of object and is part of the whole operation.
+
outside of the object and is part of the whole operation.
   
For example, if == operation is defined in a class, the actual
+
For example, if the == operation is defined as a virtual method in a class, the actual
procedure called for a==b may depend on run-time type of 'a' but if it
+
procedure called for a==b may depend on the run-time type of 'a', but if
is defined in template, actual procedure depends only on template
+
the operation is defined in template, the actual procedure depends only on the instantiated template (which is determined at compile time).
instantiated (and determined at compile time).
 
   
 
Haskell's objects don't carry run-time type information. Instead,
 
Haskell's objects don't carry run-time type information. Instead,
class constraint for polymorphic operation passed in form of
+
the class constraint for a polymorphic operation is passed in as a
 
"dictionary" implementing all operations of the class (there are also
 
"dictionary" implementing all operations of the class (there are also
other implementation techniques, but this don't matter). For example,
+
other implementation techniques, but this doesn't matter). For example,
   
 
<haskell>
 
<haskell>
Line 243: Line 248:
 
</haskell>
 
</haskell>
   
translated into:
+
is translated into:
   
 
<haskell>
 
<haskell>
Line 250: Line 255:
 
</haskell>
 
</haskell>
   
where first parameter is "dictionary" containing implementation of
+
where the first parameter is a "dictionary" containing the implementation of
 
"==" and "/=" operations for objects of type 'a'. If there are several
 
"==" and "/=" operations for objects of type 'a'. If there are several
class constraints, dictionary for each is passed.
+
class constraints, a dictionary for each is passed.
   
If class has base class(es), the dictionary tuple also includes tuples
+
If the class has base class(es), the dictionary tuple includes the base class dictionaries, so
of base classes dictionaries:
 
   
 
<haskell>
 
<haskell>
Line 266: Line 271:
   
 
<haskell>
 
<haskell>
type CmpDictionary a = (eqDictionary a, a -> a -> Ordering)
+
type CmpDictionary a = (EqDictionary a, a -> a -> Ordering)
cmpList :: CmpDictionary a -> [a] -> [a] -> Bool
+
cmpList :: CmpDictionary a -> [a] -> [a] -> Ordering
 
</haskell>
 
</haskell>
   
   
Comparing to C++, this is like the templates, not classes! As with
+
Compared to C++, this is more like templates, not classes! As with
templates, typing information is part of operation, not object! But
+
templates, type information is part of operation, not the object! But
while C++ templates are really form of macro-processing (like
+
while C++ templates are really a form of macro-processing (like
Template Haskell) and at last end generates non-polymorphic code,
+
Template Haskell) and at last end generate non-polymorphic code,
Haskell's using of dictionaries allows run-time polymorphism
+
Haskell's use of dictionaries allows run-time polymorphism
(explanation of run-time polymorphism?).
+
(explanation of run-time polymorphism? -what is this? a form of dynamic dispatch?).
   
Moreover, Haskell type classes supports inheritance. Run-time
+
Moreover, Haskell type classes support inheritance. Run-time
 
polymorphism together with inheritance are often seen as OOP
 
polymorphism together with inheritance are often seen as OOP
 
distinctive points, so during long time I considered type classes as a
 
distinctive points, so during long time I considered type classes as a
 
form of OOP implementation. But that's wrong! Haskell type classes
 
form of OOP implementation. But that's wrong! Haskell type classes
build on different basis, so they are like C++ templates with added
+
build on a different basis, so they are like C++ templates with added
inheritance and run-time polymorphism! And this means that usage of
+
inheritance and run-time polymorphism! And this means that the usage of
 
type classes is different from using classes, with its own strong and
 
type classes is different from using classes, with its own strong and
 
weak points.
 
weak points.
 
   
 
== Type classes vs classes ==
 
== Type classes vs classes ==
Line 292: Line 296:
 
Here is a brief listing of differences between OOP classes and Haskell type classes
 
Here is a brief listing of differences between OOP classes and Haskell type classes
   
=== Type classes is like interfaces/abstract classes, not classes itself ===
+
=== Type classes are like interfaces/abstract classes, not classes itself ===
   
There is no data fields inheritance and data fields itself
+
There is no inheritance and data fields
(so type classes more like to interfaces than to classes itself)....
+
(so type classes are more like interfaces than classes)....
   
   
Line 376: Line 380:
   
 
There is upcasting mechanism, it just extracts dictionary of a base
 
There is upcasting mechanism, it just extracts dictionary of a base
class from a dictionary tuple, so you can run function that requires
+
class from a dictionary tuple, so you can run a function that requires
 
base class from a function that requires subclass:
 
base class from a function that requires subclass:
   
Line 418: Line 422:
 
=== Downcasting is a mission impossible ===
 
=== Downcasting is a mission impossible ===
   
Selection between instances are done at compile-time, based only on
+
Selection between instances is done at compile-time, based only on
information present at this moment. So don't expect that more concrete
+
information present at the moment. So don't expect that more concrete
 
instance will be selected just because you passed this concrete
 
instance will be selected just because you passed this concrete
 
datatype to the function which accepts some general class:
 
datatype to the function which accepts some general class:
Line 448: Line 452:
 
instance.
 
instance.
   
  +
:<i>Remark: This isn't even a legal program unless you use the <hask>IncoherentInstances</hask> language extension. The error message:</i>
  +
  +
<haskell>
  +
Overlapping instances for Foo a
  +
arising from a use of `foo' at /tmp/I.hs:17:4-6
  +
Matching instances:
  +
instance [overlap ok] (Num a) => Foo a
  +
-- Defined at /tmp/I.hs:10:9-24
  +
instance [overlap ok] Foo Int -- Defined at /tmp/I.hs:13:9-15
  +
(The choice depends on the instantiation of `a'
  +
To pick the first instance above, use -XIncoherentInstances
  +
when compiling the other instance declarations)
  +
</haskell>
  +
:<i>Details: [http://haskell.org/ghc/docs/latest/html/users_guide/type-class-extensions.html#instance-overlap GHC User's Guide]</i>
   
 
=== There is only one dictionary per function call ===
 
=== There is only one dictionary per function call ===
Line 473: Line 491:
 
</haskell>
 
</haskell>
   
This code will not work - a<=b can use nor 'a' nor 'b' dictionary.
+
This code will not work - a<=b can use nor 'a' neither 'b' dictionary.
 
Even if orderings for apples and penguins are defined, we still don't have
 
Even if orderings for apples and penguins are defined, we still don't have
a method to compare penguin with apple!
+
a method to compare penguins to apples!
   
   
Line 488: Line 506:
   
 
There is a major difference though, in C++ (or java, or sather, or c#,
 
There is a major difference though, in C++ (or java, or sather, or c#,
etc..) the dictionary is always attached to the value, the actual class
+
etc.) the dictionary is always attached to the value, the actual class
data type you pass around. in haskell, the dictionary is passed
+
data type you pass around. In Haskell, the dictionary is passed
separately and the appropriae one is infered by the type system. C++
+
separately and the appropriate one is inferred by the type system. C++
doesn't infer, it just assumes everything will be carying around its
+
doesn't infer, it just assumes everything will be carrying around its
 
dictionary with it.
 
dictionary with it.
   
this makes haskell classes signifigantly more powerful in many ways.
+
This makes Haskell classes significantly more powerful in many ways.
   
 
<haskell>
 
<haskell>
Line 501: Line 519:
 
</haskell>
 
</haskell>
   
is imposible to express in OO classes, since both arguments to +
+
is impossible to express in OO classes: since both arguments to +
 
necessarily carry their dictionaries with them, there is no way to
 
necessarily carry their dictionaries with them, there is no way to
statically guarentee they have the same one. Haskell will pass a single
+
statically guarantee they have the same one. Haskell will pass a single
 
dictionary that is shared by both types so it can handle this just fine.
 
dictionary that is shared by both types so it can handle this just fine.
   
in haskell you can do
+
In haskell you can do
   
  +
<haskell>
 
class Monoid a where
 
class Monoid a where
 
mempty :: a
 
mempty :: a
  +
</haskell>
   
in OOP, this cannot be done because where does the dicionary come from?
+
In OOP, this cannot be done because where does the dictionary come from?
since dictionaries are always attached to a concrete class, every method
+
Since dictionaries are always attached to a concrete class, every method
 
must take at least one argument of the class type (in fact, exactly one,
 
must take at least one argument of the class type (in fact, exactly one,
as I'll show below). In haskell again, this is not a problem since the
+
as I'll show below). In Haskell again, this is not a problem since the
dictionary is passed in by the consumer of 'mempty', mempty need not
+
dictionary is passed in by the consumer of 'mempty' - mempty need not
 
conjure one out of thin air.
 
conjure one out of thin air.
 
   
 
In fact, OO classes can only express single parameter type classes where
 
In fact, OO classes can only express single parameter type classes where
 
the type argument appears exactly once in strictly covariant position.
 
the type argument appears exactly once in strictly covariant position.
in particular, it is pretty much always the first argument and often
+
In particular, it is pretty much always the first argument and often
 
(but not always) named 'self' or 'this'.
 
(but not always) named 'self' or 'this'.
 
   
 
<haskell>
 
<haskell>
Line 531: Line 549:
   
 
can be expressed in OO, 'a' appears only once, as its first argument.
 
can be expressed in OO, 'a' appears only once, as its first argument.
 
   
 
Now, another thing OO classes can do is they give you the ability to
 
Now, another thing OO classes can do is they give you the ability to
create existential collections (?) of objects. as in, you can have a
+
create existential collections (?) of objects. As in, you can have a
list of things that have a size. In haskell, the ability to do this is
+
list of things that have a size. In Haskell, the ability to do this is
independent of the class (which is why haskell classes can be more
+
independent of the class (which is why Haskell classes can be more
 
powerful) and is appropriately named existential types.
 
powerful) and is appropriately named existential types.
   
Line 543: Line 560:
 
</haskell>
 
</haskell>
   
what does this give you? you can now create a list of things that have a
+
What does this give you? You can now create a list of things that have a
 
size [Sized] yay!
 
size [Sized] yay!
   
and you can declare an instance for sized, so you can use all your
+
And you can declare an instance for Sized, so you can use all your
 
methods on it.
 
methods on it.
   
Line 554: Line 571:
 
</haskell>
 
</haskell>
   
+
An existential, like Sized, is a value that is passed around with its
an exisential, like Sized, is a value that is passed around with its
 
 
dictionary in tow, as in, it is an OO class! I think this is where
 
dictionary in tow, as in, it is an OO class! I think this is where
people get confused when comparing OO classes to haskell classes. _there
+
people get confused when comparing OO classes to Haskell classes. _There
 
is no way to do so without bringing existentials into play_. OO classes
 
is no way to do so without bringing existentials into play_. OO classes
 
are inherently existential in nature.
 
are inherently existential in nature.
   
so, an OO abstract class declaration declares the equivalent of 3 things
+
So, an OO abstract class declaration declares the equivalent of 3 things
in haskell: a class to establish the mehods, an existential type to
+
in Haskell: a class to establish the methods, an existential type to
carry the values about, and an instance of the class for the exisential
+
carry the values about, and an instance of the class for the existential
 
type.
 
type.
   
an OO concrete class declares all of the above plus a data declaration
+
An OO concrete class declares all of the above plus a data declaration
 
for some concrete representation.
 
for some concrete representation.
 
   
 
OO classes can be perfectly (even down to the runtime representation!)
 
OO classes can be perfectly (even down to the runtime representation!)
emulated in Haskell, but not vice versa. since OO languages tie class
+
emulated in Haskell, but not vice versa. Since OO languages tie class
 
declarations to existentials, they are limited to only the intersection
 
declarations to existentials, they are limited to only the intersection
of their capabilities, because haskell has separate concepts for them,
+
of their capabilities, because Haskell has separate concepts for them;
 
each is independently much much more powerful.
 
each is independently much much more powerful.
   
  +
<haskell>
 
data CanApply = exists a b . CanApply (a -> b) a (b -> a)
 
data CanApply = exists a b . CanApply (a -> b) a (b -> a)
  +
</haskell>
   
 
is an example of something that cannot be expressed in OO, existentials
 
is an example of something that cannot be expressed in OO, existentials
 
are limited to having exactly a single value since they are tied to a
 
are limited to having exactly a single value since they are tied to a
single dictionary
+
single dictionary.
 
   
 
<haskell>
 
<haskell>
Line 590: Line 608:
 
cannot be expressed in OO, because there is no way to pass in the same
 
cannot be expressed in OO, because there is no way to pass in the same
 
dicionary for two elements, or for a returning value to conjure up a
 
dicionary for two elements, or for a returning value to conjure up a
dictionary out of thin air. (if you are not convinced, try writing a
+
dictionary out of thin air. (If you are not convinced, try writing a
 
'Number' existential and making it an instance of Num and it will be
 
'Number' existential and making it an instance of Num and it will be
clear why it is not possible)
+
clear why it is not possible.)
   
negate is an interesting one, there is no technical reason it cannot be
+
negate is an interesting one - there is no technical reason it cannot be
 
implemented in OO languages, but none seem to actually support it.
 
implemented in OO languages, but none seem to actually support it.
   
  +
So, when comparing, remember an OO class always corresponds to a Haskell
  +
class + a related Haskell existential.
   
so, when comparing, remember an OO class always cooresponds to a haskell
+
Incidentally, an extension I am working on is to allow
class + a related haskell existential.
 
 
 
incidentally, an extension I am working on is to allow
 
   
 
<haskell>
 
<haskell>
Line 605: Line 625:
 
</haskell>
 
</haskell>
   
which would have the obvious interpretation, obviously it would only work
+
which would have the obvious interpretation. Obviously it would only work
 
under the same limitations as OO classes have, but it would be a simple
 
under the same limitations as OO classes have, but it would be a simple
 
way for haskell programs to declare OO style classes if they so choose.
 
way for haskell programs to declare OO style classes if they so choose.
   
(actually, it is still signifigantly more powerful than OO classes since
+
(Actually, it is still signifigantly more powerful than OO classes since
 
you can derive many instances, and even declare your own for classes
 
you can derive many instances, and even declare your own for classes
that don't meet the OO consraints, also, your single class argument need
+
that don't meet the OO constraints. Also, your single class argument need
not appear as the first one. it can appear in any strictly covarient
+
not appear as the first one. It can appear in any strictly covariant
 
position, and it can occur as often as you want in contravariant ones!)
 
position, and it can occur as often as you want in contravariant ones!)
 
   
 
=== Type classes correspond to parameterized abstract classes (Gabriel Dos Reis) ===
 
=== Type classes correspond to parameterized abstract classes (Gabriel Dos Reis) ===
Line 683: Line 702:
 
| in OOP, this cannot be done because where does the dicionary come from?
 
| in OOP, this cannot be done because where does the dicionary come from?
   
See above. I believe a key in my suggestion was "paramaterized
+
See above. I believe a key in my suggestion was "parameterized
 
abstract classes", not just "abstract classes".
 
abstract classes", not just "abstract classes".
   
Line 857: Line 876:
 
== Type class system extensions ==
 
== Type class system extensions ==
   
Brief list of extensions, their abbeviated names and compatibility level
+
Brief list of extensions, their abbreviated names and compatibility level
   
 
* Constructor classes (Haskell'98)
 
* Constructor classes (Haskell'98)
Line 875: Line 894:
 
I thanks Ralf Lammel and Klaus Ostermann for their paper
 
I thanks Ralf Lammel and Klaus Ostermann for their paper
 
"Software Extension and Integration with Type Classes" (http://homepages.cwi.nl/~ralf/gpce06/) which prompts me to start thinking about differences between OOP and type classes instead of their similarities
 
"Software Extension and Integration with Type Classes" (http://homepages.cwi.nl/~ralf/gpce06/) which prompts me to start thinking about differences between OOP and type classes instead of their similarities
  +
  +
[[Category:Tutorials]]

Latest revision as of 12:57, 1 June 2012

(this is just a sketch now. feel free to edit/comment it. I will include information you provided into the final version of this tutorial)


I had generally not used type classes in my application programs, but when I'd gone to implement general purpose libraries and tried to maintain as much flexibility as possible, it was natural to start building large and complex class hierarchies. I tried to use my C++ experience when doing this but I was bitten many times by the restrictions of type classes. After this experience, I think that I now have a better feeling and mind model for type classes and I want to share it with other Haskellers - especially ones having OOP backgrounds.

Brian Hulley provided us with the program that emulates OOP in Haskell - as you can see, it's much larger than equivalent C++ program. An equivalent translation from Haskell to C++ should be even longer :)


Contents

[edit] 1 Everything is an object?

Most software developers are familiar with the OOP motto "everything is an object." People accustomed to C++ classes often find the Haskell concept of type classes difficult to grasp. Why is it so different?

C++ classes pack functions together with data, which makes it convenient to represent and consume data. Use of interfaces (abstract classes) allow classes to interact by contract, instead of directly manipulating the data in the other class. There exist alternative ways in C++ to accomplish such functionality (function pointers, discriminated unions), yet these techniques are not as handy as classes. Classes are also the primary way to hiding implementation details. Moreover, classes represent a handy way to group related functionality together. It's extremely useful to browse the structure of large C++ project in terms of classes instead of individual functions.

Haskell provides other solutions for these problems.

[edit] 1.1 Type with several representations: use algebraic data type (ADT)

For the types with different representations, algebraic data types (ADT) - an analog of discriminated unions - are supported:

data Point = FloatPoint Float Float
           | IntPoint Int Int

Haskell provides a very easy way to build/analyze them:

coord :: Point -> (Float, Float)
coord (FloatPoint x y) = (x,y)
coord (IntPoint x y) = (realToFrac x, realToFrac y)
 
main = do print (coord (FloatPoint 1 2))
          print (coord (IntPoint 1 2))

So ADTs in general are preferred in Haskell over the class-based solution of the same problem:

class Point a where
    coord :: a -> (Float, Float)
 
data FloatPoint = FloatPoint Float Float
instance Point FloatPoint where
    coord (FloatPoint x y) = (x,y)
 
data IntPoint = IntPoint Int Int
instance Point IntPoint where
    coord (IntPoint x y) = (realToFrac x, realToFrac y)


The equivalent C++ implementation using inheritance requires much more machinery than our 5 line, ADT-based solution. This also illustrates a Haskell benefit--it's much easier to define types/functions. Perhaps objects are not as great as you thought before. :D


#include <algorithm>
#include <iostream>
using namespace std;

ostream & operator<<(ostream & lhs, pair<float, float> const& rhs) {
    return lhs << "(" << rhs.first << "," << rhs.second << ")";
}

struct Point {
    virtual pair<float,float> coord() = 0;
};

struct FloatPoint : Point {
    float x, y;
    FloatPoint (float _x, float _y) : x(_x), y(_y) {}
    pair<float,float> coord() {return make_pair(x,y); }
};

struct IntPoint : Point {
    int x, y;
    IntPoint (int _x, int _y) : x(_x), y(_y) {}
    pair<float,float> coord() { return make_pair(x,y); }
};

int main () {
    cout << FloatPoint(1,2).coord();
    cout << IntPoint(1,2).coord();
    return 0;
}

As you see, ADTs together with type inference make Haskell programs about 2 times smaller than their C++ equivalent.


[edit] 1.2 Packing data & functions together: use (records of) closures

Another typical class use-case is to pack data together with one or more processing functions and pass this bunch to some function. Then this function can call the aforementioned functions to implement some functionality, not bothering how it is implemented internally. Hopefully Haskell provides a better way: you can pass any functions as parameters to other functions directly. Moreover, such functions can be constructed on-the-fly, capturing free variables in context, creating the so-called closures. In this way, you construct something like object on-demand and don't even need a type class:

do x <- newIORef 0
   proc (modifyIORef x (+1), readIORef x)

Here, we applied proc to two functions - one incrementing the value of a counter and another reading its current value. Another call to proc that uses counter with locking, might look like this:

do x <- newMVar 0
   proc (modifyMVar x (+1), readMVar x)

Here, proc may be defined as:

proc :: (IO (), IO Int) -> IO ()
proc (inc, read) = do { inc; inc; inc; read >>= print }


i.e. it receive two abstract operations whose implementation may vary in different calls to proc and call them without any knowledge of implementation details. The equivalent C++ code could look like this:

class Counter {
public:
    virtual void inc()  = 0;
    virtual int  read() = 0;
};

class SimpleCounter : public Counter {
public:
    SimpleCounter()  { n = 0; }
    void inc()       { n++; }
    int  read()      { return n; }
private:
    int n;
};

void proc (Counter &c) {
    c.inc(); c.inc(); c.inc(); cout << c.read();
}

And again, Haskell code is much simpler and more straightforward - we don't need to declare classes, operations, their types - we just pass to the proc implementation of operations it needs. Look at IO inside#Example: returning an IO action as a result and following sections to find more examples of using closures instead of OOP classes.

[edit] 1.3 Hiding implementation details: use module export list

One more usage of OOP classes is to hide implementation details, making internal data/functions inaccessible to class clients. Unfortunately, this functionality is not part of type class facilities. Instead, you should use the sole Haskell method of encapsulation, module export list:

module Stack (Stack, empty, push, pop, top, isEmpty) where
 
newtype Stack a = Stk [a]
 
empty                 = Stk []
push   x (Stk xs)     = Stk (x:xs)
pop      (Stk (x:xs)) = Stk xs
top      (Stk (x:xs)) = x
isEmpty  (Stk xs)     = null xs

Since the constructor for the data type Stack is hidden (the export list would say Stack(Stk) if it were exposed), outside of this module a stack can only be built from operations empty, push and pop, and examined with top and isEmpty.


[edit] 1.4 Grouping related functionality: use module hierarchy and Haddock markup

Dividing a whole program into classes and using their hierarchy to represent entire an program structure is a great instrument for OO languages. Unfortunately, it's again impossible in Haskell. Instead, the structure of a program is typically rendered in a module hierarchy and inside a module - in its export list. Although Haskell doesn't provide facilities to describe a hierarchical structure inside of a module, we have another tool to do it - Haddock, a de-facto standard documentation tool.

module System.Stream.Instance (
 
    -- * File is a file stream
    File,
    -- ** Functions that open files
    openFile,                  -- open file in text mode
    openBinaryFile,            -- open file in binary mode
    -- ** Standard file handles
    stdin,
    stdout,
    stderr,
 
    -- * MemBuf is a memory buffer stream
    MemBuf,
    -- ** Functions that open MemBuf
    createMemBuf,              -- create new MemBuf
    createContiguousMemBuf,    -- create new contiguous MemBuf
    openMemBuf,                -- use memory area as MemBuf
 
) where
...

Here, Haddock will build documentation for a module using its export list. The export list will be divided into sections (whose headers given with "-- *") and subsections (given with "-- **"). As a result, module documentation reflects its structure without using classes for this purpose.

[edit] 2 Type classes is a sort of templates, not classes

At this moment, C++ has classes and templates. What is the difference? With a class, type information is carried with the object itself while with templates it's outside of the object and is part of the whole operation.

For example, if the == operation is defined as a virtual method in a class, the actual procedure called for a==b may depend on the run-time type of 'a', but if the operation is defined in template, the actual procedure depends only on the instantiated template (which is determined at compile time).

Haskell's objects don't carry run-time type information. Instead, the class constraint for a polymorphic operation is passed in as a "dictionary" implementing all operations of the class (there are also other implementation techniques, but this doesn't matter). For example,

eqList :: (Eq a) => [a] -> [a] -> Bool

is translated into:

type EqDictionary a = (a->a->Bool, a->a->Bool)
eqList :: EqDictionary a -> [a] -> [a] -> Bool

where the first parameter is a "dictionary" containing the implementation of "==" and "/=" operations for objects of type 'a'. If there are several class constraints, a dictionary for each is passed.

If the class has base class(es), the dictionary tuple includes the base class dictionaries, so

class Eq a => Cmp a where
  cmp :: a -> a -> Ordering
 
cmpList :: (Cmp a) => [a] -> [a] -> Ordering

turns into:

type CmpDictionary a = (EqDictionary a, a -> a -> Ordering)
cmpList :: CmpDictionary a -> [a] -> [a] -> Ordering


Compared to C++, this is more like templates, not classes! As with templates, type information is part of operation, not the object! But while C++ templates are really a form of macro-processing (like Template Haskell) and at last end generate non-polymorphic code, Haskell's use of dictionaries allows run-time polymorphism (explanation of run-time polymorphism? -what is this? a form of dynamic dispatch?).

Moreover, Haskell type classes support inheritance. Run-time polymorphism together with inheritance are often seen as OOP distinctive points, so during long time I considered type classes as a form of OOP implementation. But that's wrong! Haskell type classes build on a different basis, so they are like C++ templates with added inheritance and run-time polymorphism! And this means that the usage of type classes is different from using classes, with its own strong and weak points.

[edit] 3 Type classes vs classes

Here is a brief listing of differences between OOP classes and Haskell type classes

[edit] 3.1 Type classes are like interfaces/abstract classes, not classes itself

There is no inheritance and data fields (so type classes are more like interfaces than classes)....


For those more familiar with Java/C# rather than C++, type classes resemble interfaces more than the classes. In fact, the generics in those languages capture the notion of parametric polymorphism (but Haskell is a language that takes parametric polymorphism quite seriously, so you can expect a fair amount of type gymnastics when dealing with Haskell), so more precisely, type classes are like generic interfaces.

Why interface, and not class? Mostly because type classes do not implement the methods themselves, they just guarantee that the actual types that instantiate the type class will implement specific methods. So the types are like classes in Java/C#.

One added twist: type classes can decide to provide default implementation of some methods (using other methods). You would say, then they are sort of like abstract classes. Right. But at the same time, you cannot extend (inherit) multiple abstract classes, can you?

So a type class is sort of like a contract: "any type that instantiates this type class will have the following functions defined on them..." but with the added advantage that you have type parameters built-in, so:

class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  -- let's just implement one function in terms of the other
  x /= y = not (x == y)

is, in a Java-like language:

interface Eq<A> {

  boolean equal(A that);
  boolean notEqual(A that) { 
     // default, can be overriden
     return !equal(that); 
  } 

}

And the "instance TypeClass ParticularInstance where ..." definition means "ParticularInstance implements TypeClass { ... }", now, multiple parameter type classes, of course, cannot be interpreted this way.


[edit] 3.2 Type can appear at any place in function signature

Type can appear at any place in function signature: be any parameter, inside parameter, in a list (possibly empty), or in a result

class C a where
    f :: a -> Int
    g :: Int -> a -> Int
    h :: Int -> (Int,a) -> Int
    i :: [a] -> Int
    j :: Int -> a
    new :: a

It's even possible to define instance-specific constants (look at 'new').

If function value is instance-specific, OOP programmer will use "static" method while with type classes you need to use fake parameter:

class FixedSize a where
  sizeof :: a -> Int
instance FixedSize Int8 where
  sizeof _ = 1
instance FixedSize Int16 where
  sizeof _ = 2
 
main = do print (sizeof (undefined::Int8))
          print (sizeof (undefined::Int16))


[edit] 3.3 Inheritance between interfaces

Inheritance between interfaces (in "class" declaration) means inclusion of base class dictionaries in dictionary of subclass:

class (Show s, Monad m s) => Stream m s where
    sClose :: s -> m ()

means

type StreamDictionary m s = (ShowDictionary s, MonadDictionary m s, s->m())

There is upcasting mechanism, it just extracts dictionary of a base class from a dictionary tuple, so you can run a function that requires base class from a function that requires subclass:

f :: (Stream m s) =>  s -> m String
show ::  (Show s) =>  s -> String
f s = return (show s)

But downcasting is absolutely impossible - there is no way to get subclass dictionary from a superclass one


[edit] 3.4 Inheritance between instances

Inheritance between instances (in "instance" declaration) means that operations of some class can be executed via operations of other class, i.e. such declaration describe a way to compute dictionary of inherited class via functions from dictionary of base class:

class Eq a where
  (==) :: a -> a -> Bool
class Cmp a where
  cmp :: a -> a -> Ordering
instance (Cmp a) => Eq a where
  a==b  =  cmp a b == EQ

creates the following function:

cmpDict2EqDict :: CmpDictionary a -> EqDictionary a
cmpDict2EqDict (cmp) = (\a b -> cmp a b == EQ)

This results in that any function that receives dictionary for Cmp class can call functions that require dictionary of Eq class


[edit] 3.5 Downcasting is a mission impossible

Selection between instances is done at compile-time, based only on information present at the moment. So don't expect that more concrete instance will be selected just because you passed this concrete datatype to the function which accepts some general class:

class Foo a where
  foo :: a -> String
 
instance (Num a) => Foo a where
  foo _ = "Num"
 
instance Foo Int where
  foo _ = "int"
 
f :: (Num a) =>  a -> String
f = foo
 
main = do print (foo (1::Int))
          print (f (1::Int))

Here, the first call will return "int", but second - only "Num". this can be easily justified by using dictionary-based translation as described above. After you've passed data to polymorphic procedure it's type is completely lost, there is only dictionary information, so instance for Int can't be applied. The only way to construct Foo dictionary is by calculating it from Num dictionary using the first instance.

Remark: This isn't even a legal program unless you use the
IncoherentInstances
language extension. The error message:
 Overlapping instances for Foo a
  arising from a use of `foo' at /tmp/I.hs:17:4-6
 Matching instances:
   instance [overlap ok] (Num a) => Foo a
     -- Defined at /tmp/I.hs:10:9-24
   instance [overlap ok] Foo Int -- Defined at /tmp/I.hs:13:9-15
 (The choice depends on the instantiation of `a'
 To pick the first instance above, use -XIncoherentInstances 
 when compiling the other instance declarations)
Details: GHC User's Guide

[edit] 3.6 There is only one dictionary per function call

For "eqList :: (Eq a) => [a] -> [a] -> Bool" types of all elements in list must be the same, and types of both arguments must be the same too - there is only one dictionary and it know how to handle variables of only one concrete type!

[edit] 3.7 Existential variables is more like OOP objects

Existential variables pack dictionary together with variable (looks very like the object concept!) so it's possible to create polymorphic containers (i.e. holding variables of different types). But downcasting is still impossible. Also, existentials still don't allow to mix variables of different types in a call to some polymorhic operation (their personal dictionaries still built for variables of one concrete type):

data HasCmp = forall a. Cmp a => HasCmp a
 
sorted :: [HasCmp] -> Ordering
 
sorted []  = True
sorted [_] = True
sorted (HasCmp a : HasCmp b : xs)  =  a<=b && sorted (b:xs)

This code will not work - a<=b can use nor 'a' neither 'b' dictionary. Even if orderings for apples and penguins are defined, we still don't have a method to compare penguins to apples!


[edit] 4 Other opinions

[edit] 4.1 OO class always corresponds to a haskell class + a related haskell existential (John Meacham)

> Roughly Haskell type classes correspond to parameterized abstract
> classes in C++ (i.e. class templates with virtual functions 
> representing the operations).  Instance declarations correspond to
> derivation and implementations of those parameterized classes.

There is a major difference though, in C++ (or java, or sather, or c#, etc.) the dictionary is always attached to the value, the actual class data type you pass around. In Haskell, the dictionary is passed separately and the appropriate one is inferred by the type system. C++ doesn't infer, it just assumes everything will be carrying around its dictionary with it.

This makes Haskell classes significantly more powerful in many ways.

class Num a where
   (+) :: a -> a -> a

is impossible to express in OO classes: since both arguments to + necessarily carry their dictionaries with them, there is no way to statically guarantee they have the same one. Haskell will pass a single dictionary that is shared by both types so it can handle this just fine.

In haskell you can do

class Monoid a where
        mempty :: a

In OOP, this cannot be done because where does the dictionary come from? Since dictionaries are always attached to a concrete class, every method must take at least one argument of the class type (in fact, exactly one, as I'll show below). In Haskell again, this is not a problem since the dictionary is passed in by the consumer of 'mempty' - mempty need not conjure one out of thin air.

In fact, OO classes can only express single parameter type classes where the type argument appears exactly once in strictly covariant position. In particular, it is pretty much always the first argument and often (but not always) named 'self' or 'this'.

class HasSize a where
        getSize :: a -> Int

can be expressed in OO, 'a' appears only once, as its first argument.

Now, another thing OO classes can do is they give you the ability to create existential collections (?) of objects. As in, you can have a list of things that have a size. In Haskell, the ability to do this is independent of the class (which is why Haskell classes can be more powerful) and is appropriately named existential types.

data Sized = exists a . HasSize a => Sized a

What does this give you? You can now create a list of things that have a size [Sized] yay!

And you can declare an instance for Sized, so you can use all your methods on it.

instance HasSize Sized where
        getSize (Sized a) = getSize a

An existential, like Sized, is a value that is passed around with its dictionary in tow, as in, it is an OO class! I think this is where people get confused when comparing OO classes to Haskell classes. _There is no way to do so without bringing existentials into play_. OO classes are inherently existential in nature.

So, an OO abstract class declaration declares the equivalent of 3 things in Haskell: a class to establish the methods, an existential type to carry the values about, and an instance of the class for the existential type.

An OO concrete class declares all of the above plus a data declaration for some concrete representation.

OO classes can be perfectly (even down to the runtime representation!) emulated in Haskell, but not vice versa. Since OO languages tie class declarations to existentials, they are limited to only the intersection of their capabilities, because Haskell has separate concepts for them; each is independently much much more powerful.

data CanApply = exists a b . CanApply (a -> b) a (b -> a)

is an example of something that cannot be expressed in OO, existentials are limited to having exactly a single value since they are tied to a single dictionary.

class Num a where
   (+) :: a -> a -> a
   zero :: a
   negate :: a -> a

cannot be expressed in OO, because there is no way to pass in the same dicionary for two elements, or for a returning value to conjure up a dictionary out of thin air. (If you are not convinced, try writing a 'Number' existential and making it an instance of Num and it will be clear why it is not possible.)

negate is an interesting one - there is no technical reason it cannot be implemented in OO languages, but none seem to actually support it.

So, when comparing, remember an OO class always corresponds to a Haskell class + a related Haskell existential.

Incidentally, an extension I am working on is to allow

data Sized = exists a . HasSize a => Sized a 
        deriving(HasSize)

which would have the obvious interpretation. Obviously it would only work under the same limitations as OO classes have, but it would be a simple way for haskell programs to declare OO style classes if they so choose.

(Actually, it is still signifigantly more powerful than OO classes since you can derive many instances, and even declare your own for classes that don't meet the OO constraints. Also, your single class argument need not appear as the first one. It can appear in any strictly covariant position, and it can occur as often as you want in contravariant ones!)

[edit] 4.2 Type classes correspond to parameterized abstract classes (Gabriel Dos Reis)

| > Roughly Haskell type classes correspond to parameterized abstract
| > classes in C++ (i.e. class templates with virtual functions 
| > representing the operations).  Instance declarations correspond to
| > derivation and implementations of those parameterized classes.
| 
| There is a major difference though, in C++ (or java, or sather, or c#,
| etc..) the dictionary is always attached to the value, the actual class
| data type you pass around.

I suspect that most of the confusion come from the fact that people believe just because virtual functions are attached to objects, they cannot attach them to operations outside classes. That, to my surprise, hints at a deeper misappreciation of both type classes and so-called "OO" technology. Type classes are more OO than one might realize.

The dictionary can be attached to the operations (not just to the values) by using objects local to functions (which sort of matierialize the dictionary). Consider

   // Abstract class for a collection of classes that implement
   // the "Num" mathematical structure
   template<typename T>
     struct Num {
         virtual T add(T, T) const = 0;
     };
   // Every type must specialize this class template to assert
   // membership to the "Num" structure.  
   template<typename T> struct Num_instance;
   // The operation "+" is defined for any type that belongs to "Num".
   // Notice, membership is asserted aby specializing Num_instance<>.
   template<typename T>
     T operator+(T lhs, T rhs)
     {
        const Num_instance<T> instance;  
        return instance.add(lhs, rhs);
     }
   // "Foo" is in "Num"
   struct Num_instance<Foo> : Num<Foo> {
      Foo add(Foo a, Foo b) const { ... }
   };


The key here is in the definition of operator+ which is just a formal name for the real operation done by instance.add().

I appreciate that inferring and building the dictionary (represented here by the "instance" local to operator+<T>) is done automatically by the Haskell type system. That is one of the reasons why the type class notation is a nice sugar. However, that should not distract from its deerper OO semantics.


[...]

| in haskell you can do
| 
| class Monoid a where
|         mempty :: a
| 
| in OOP, this cannot be done because where does the dicionary come from?

See above. I believe a key in my suggestion was "parameterized abstract classes", not just "abstract classes".


[edit] 5 Haskell emulation of OOP inheritance with record extension

Brian Hulley provided us the code that shows how OOP inheritance can be emulated in Haskell. His translation method supports data fields inheritance, although don't supports downcasting.

> although i mentioned not only pluses but also drawbacks of type
> classes: lack of record extension mechanisms (such at that implemented
> in O'Haskell) and therefore inability to reuse operation
> implementation in an derived data type...

You can reuse ops in a derived data type but it involves a tremendous amount of boilerplate. Essentially, you just use the type classes to simulate extendable records by having a method in each class that accesses the fixed-length record corresponding to that particular C++ class.

Here is an example (apologies for the length!) which shows a super class function being overridden in a derived class and a derived class method (B::Extra) making use of something implemented in the super class:

module Main where
 
{-  Haskell translation of the following C++
 
    class A {
    public:
        String s;
        Int i;
 
        A(String s, Int i) s(s), i(i){}
 
        virtual void Display(){
            printf("A %s %d\n", s.c_str(), i);
        }
 
        virtual Int Reuse(){
            return i * 100;
        }
    };
 
 
    class B: public A{
    public:
        Char c;
 
        B(String s, Int i, Char c) : A(s, i), c(c){}
 
        virtual void Display(){
            printf("B %s %d %c", s.c_str(), i, c);
        }
 
        virtual void Extra(){
            printf("B Extra %d\n", Reuse());
        }
 
    };
 
-}
 
data A = A
                { _A_s :: String
                , _A_i :: Int
                }
 
-- This could do arg checking etc
constructA :: String -> Int -> A
constructA = A
 
 
class ClassA a where
    getA :: a -> A
 
    display :: a -> IO ()
    display a = do
        let
            A{_A_s = s, _A_i = i} = getA a
        putStrLn $ "A " ++ s ++ show i
 
    reuse :: a -> Int
    reuse a = _A_i (getA a) * 100
 
 
data WrapA = forall a. ClassA a => WrapA a
 
instance ClassA WrapA where
    getA (WrapA a) = getA a
    display (WrapA a) = display a
    reuse (WrapA a) = reuse a
 
instance ClassA A where
    getA = id
 
 
data B = B { _B_A :: A, _B_c :: Char }
 
 
constructB :: String -> Int -> Char -> B
constructB s i c = B {_B_A = constructA s i, _B_c = c}
 
class ClassA b => ClassB b where
    getB :: b -> B
 
    extra :: b -> IO ()
    extra b = do
        putStrLn $ "B Extra " ++ show (reuse b)
 
data WrapB = forall b. ClassB b => WrapB b
 
instance ClassB WrapB where
    getB (WrapB b) = getB b
    extra (WrapB b) = extra b
 
instance ClassA WrapB where
    getA (WrapB b) = getA b
    display (WrapB b) = display b
    reuse (WrapB b) = reuse b
 
instance ClassB B where
    getB = id
 
instance ClassA B where
    getA = _B_A
 
    -- override the base class version
    display b = putStrLn $
                "B " ++ _A_s (getA b)
                ++ show (_A_i (getA b))
                ++ [_B_c (getB b)]
 
 
main :: IO ()
main = do
    let
        a = constructA "a" 0
        b = constructB "b" 1 '*'
 
        col = [WrapA a, WrapA b]
 
    mapM_ display col
    putStrLn ""
    mapM_ (putStrLn . show . reuse) col
    putStrLn ""
    extra b
 
{- Output:
 
   > ghc -fglasgow-exts --make Main
   > main
   A a0
   B b1*
 
   0
   100
 
   B Extra 100
 
   >
-}

(If the "caseless underscore" Haskell' ticket is accepted the leading underscores would have to be replaced by something like "_f" ie _A_s ---> _fA_s etc)


[edit] 6 Type class system extensions

Brief list of extensions, their abbreviated names and compatibility level

  • Constructor classes (Haskell'98)
  • MPTC: multi-parameter type classes (Hugs/GHC extension)
  • FD: functional dependencies (Hugs/GHC extension)
  • AT: associated types (GHC 6.6 only)
  • Overlapped, undecidable and incoherent instances (Hugs/GHC extension)


[edit] 7 Literature

The paper that at first time introduced type classes and their implementation using dictionaries was Philip Wadler and Stephen Blott "How to make ad-hoc polymorphism less ad-hoc" (http://homepages.inf.ed.ac.uk/wadler/papers/class/class.ps.gz)

You can find more papers on the Type classes page.

I thanks Ralf Lammel and Klaus Ostermann for their paper "Software Extension and Integration with Type Classes" (http://homepages.cwi.nl/~ralf/gpce06/) which prompts me to start thinking about differences between OOP and type classes instead of their similarities