[Haskell-cafe] OOP < parametric polymorphism

[apfelmus at quantentunnel.de]

Donald Bruce Stewart wrote:
> deliverable:
>> ...In the tradition of the "letters of an ignorant newbie"...
>>
>> What's the consensus on the OOP in Haskell *now*?  There're some
>> libraries such as OOHaskell, O'Haskell, and Haskell~98's own qualified
>> type system with inheritance.
>>
>> If I have GHC, which way to do anything OOP-like is considered "right" 
>> today?
> 
> Using existentials and typeclasses to do some OO things wouldn't be
> considered unidiomatic (particularly, using existentials to package up
> interfaces to values).
> 
> In general though, using a functional approach will produce better
> (simpler) Haskell code, and make it more likely others will understand it.
> Personally, I run in fear from OO Haskell ;)

Instead of OOP, Haskell uses (parametric) polymorphism which is more
powerful than OOP. For instance, the function

   length :: [a] -> Int

or, with an explicit forall

   length :: forall a . [a] -> Int

counts the number of elements in a list "[a]", regardless of what type
"a" those elements have. Moreover, it is guaranteed that "length" does
not inspect or change the elements, because it must work for all types
"a" the same way (this is called "parametricity"). Another example is

   map :: (a -> b) -> [a] -> [b]

which maps a function over all elements in the list.

In addition, Haskell has type classes (which are similar to "interfaces"
in OOP). The most basic example is

   class Eq a where
      (==) :: a -> a -> Bool

Thus, you have an equality test available on all types that are
instances of this class. For example, you can test whether two Strings
are equal, because String is an instance of Eq. More generally, you say
whether two lists are equal if you know how to test elements for equality:

   instance Eq a => Eq [a] where
      []     == []     = True
      (x:xs) == (y:ys) = (x == y) && (xs == ys)
      _      == _      = False



The important thing I want to point out in this post is that parametric
polymorphism is indeed more powerful than OOP: already a concept like Eq
is impossible to implement in OOP. The problem is best illustrated with
the class Ord (*), which provides an ordering relation. Let's
concentrate on the "smaller than" function

   (<) :: Ord a => a -> a -> Bool

Can I create an interface that expresses the same thing?

   public interface Comparable {
        boolean smaller_than(?? y);
   }

No, because there is no type I can attribute to the second argument of
"smaller_than". The problem is that I can only compare to values of the
*same* type, i.e. the type which implements the interface.

Can I create a class the expresses the same thing?

   public class Comparable {
        boolean smaller_than(Comparable y);
   }

This seems like a solution, but it is not. The problem is subtyping: if
i make integers and strings members of this class, i would be able to
compare the number 1 against the string "hello", which should be
reported as a type error.

I have no formal proof, but I think that the "<" function cannot be
expressed in a type correct way in OOP. AFAIK, only Java Generics can
express the requirement we want:

   interface Ord<A> {
        boolean smaller_than(A x, A y);
   }

   class String implements Ord<String> { ... }

But Generics are a considerable extension to OOP. In fact, there is
nothing really object oriented in here anymore, we're just on our way to
parametric polymorphism.


My final remark is about what this means for the existential quantifier
in Haskell. Because of the injection

   inject :: forall a . a -> (exists a . a)

the existential quantifier can be thought of as implementing some form
of subtyping, i.e. (exists a . a) is a supertype of every a. The point
now is: given

   type ExistsOrd = exists a . Ord a => a

there is *no*

   instance Ord ExistsOrd where ...

because we could compare arbitrary subtypes of ExistsOrd then. In the
end, the existental quantifier has limited use for data abstraction,
it's "forall" that makes things happen.



Regards,
apfelmus


(*) We don't consider Eq because given a test on type equality, we can
generalize the signature of (==)

   (==) :: (Eq a, Eq b) => a -> b -> Bool

Indeed, this is what OOP equality does.