Existential types in Haskell and generics in other languages

Question

I was trying to grasp the concept of existential types in Haskell using the article Haskell/Existentially quantified types. At the first glance, the concept seems clear and somewhat similar to generics in object oriented languages. The main example there is something called "heterogeneous list", defined as follows:

data ShowBox = forall s. Show s => SB s
 
heteroList :: [ShowBox]
heteroList = [SB (), SB 5, SB True]

instance Show ShowBox where
  show (SB s) = show s
 
f :: [ShowBox] -> IO ()
f xs = mapM_ print xs

main = f heteroList

I had a different notion of a "heterogeneous list", something like Shapeless in Scala. But here, it's just a list of items wrapped in an existential type that only adds a type constraint. The exact type of its elements is not manifested in its type signature, the only thing we know is that they all conform to the type constraint.

In object-oriented languages, it seems very natural to write something like this (example in Java). This is a ubiquitous use case, and I don't need to create a wrapper type to process a list of objects that all implement a certain interface. The animals list has a generic type List<Vocal>, so I can assume that its elements all conform to this Vocal interface:

interface Vocal {

    void voice();
}

class Cat implements Vocal {

    public void voice() {
        System.out.println("meow");
    }
}

class Dog implements Vocal {

    public void voice() {
        System.out.println("bark");
    }
}

var animals = Arrays.asList(new Cat(), new Dog());
animals.forEach(Vocal::voice);

I noticed that existential types are only available as a language extension, and they are not described in most of the "basic" Haskell books or tutorials, so my suggestion is that this is quite an advanced language feature.

My question is, why? Something that seems basic in languages with generics (constructing and using a list of objects whose types implement some interface and accessing them polymorphically), in Haskell requires a language extension, custom syntax and creating an additional wrapper type? Is there no way of achieving something like that without using existential types, or is there just no basic-level use cases for this?

Or maybe I'm just mixing up the concepts, and existential types and generics mean completely different things. Please help me make sense of it.

Answer 1

Yes,existential types and generic mean different things. An existential type can be used similarly to an interface in an object-oriented language. You can put one in a list of course, but a list or any other generic type is not needed to use an interface. It is enough to have a variable of type Vocal to demonstrate its usage.

It is not widely used in Haskell because it is not really needed most of the time.

nonHeteroList :: [IO ()]
nonHeteroList = [print (), print 5, print True]

does the same thing without any language extension.

An existential type (or an interface in an object-oriented language) is nothing but a piece of data with a bundled dictionary of methods. If you only have one method in your dictionary, just use a function. If you have more than one, you can use a tuple or a record of those. So if you have something like

interface Shape {
   void Draw();
   double Area();
}

you can express it in Haskell as, for example,

type Shape = (IO (), Double)

and say

circle center radius = (drawCircle center radius, pi * radius * radius)
rectangle topLeft bottomRight = (drawRectangle topLeft bottomRight, 
           abs $ (topLeft.x-bottomRight.x) * (topLeft.y-bottomRight.y))

shapes = [circle (P 2.0 3.5) 4.2, rectangle (P 3.3 7.2) (P -2.0 3.1)]

though you can express exactly the same thing with type classes, instances and existentials

class Shape a where
  draw :: a -> IO ()
  area :: a -> Double

data ShapeBox = forall s. Shape s => SB s
instance Shape ShapeBox where
  draw (SB a) = draw a
  area (SB a) = area a

data Circle = Circle Point Double
instance Shape Circle where
  draw (Circle c r) = drawCircle c r
  area (Circle _ r) = pi * r * r

data Rectangle = Rectangle Point Point
instance Shape Rectangle where
  draw (Rectangle tl br) = drawRectangle tl br
  area (Rectangle tl br) = abs $ (tl.x - br.x) * (tl.y - br.y)

shapes = [Circle (P 2.0 3.5) 4.2, Rectangle (P 3.3 7.2) (P -2.0 3.1)]

and there you have it, N times longer.

Answer 2

is there just no basic-level use cases for this?

Sort-of, yeah. While in Java, you have no choice but to have open classes, Haskell has ADTs which you'd normally use for these kind of use-cases. In your example, Haskell can represent it in one of two ways:

data Cat = Cat

data Dog = Dog

class Animal a where
  voice :: a -> String

instance Animal Cat where
  voice Cat = "meow"

instance Animal Dog where
  voice Dog = "woof"

or

data Animal = Cat | Dog

voice Cat = "meow"
voice Dog = "woof"

If you needed something extensible, you'd use the former, but if you need to be able to case on the type of animal, you'd use the latter. If you wanted the former, but wanted a list, you don't have to use existential types, you could instead capture what you wanted in a list, like:

voicesOfAnimals :: [() -> String]
voicesOfAnimals = [\_ -> voice Cat, \_ -> voice Dog]

Or even more simply

voicesOfAnimals :: [String]
voicesOfAnimals = [voice Cat, voice Dog]

This is kind-of what you're doing with Heterogenous lists anyway, you have a constraint, in this case Animal a on each element, which lets you call voice on each element, but nothing else, since the constraint doesn't give you any more information about the value (well if you had the constraint Typeable a you'd be able to do more, but let's not worry about dynamic types here).

---

As for the reason for why Haskell doesn't support Heterogenous lists without extensions and wrappers, I'll let someone else explain it but key topics are:

• subtyping
• variance
• inference
• https://gitlab.haskell.org/ghc/ghc/-/wikis/impredicative-polymorphism (I think)

In your Java example, what's the type of Arrays.asList(new Cat())? Well, it depends on what you declare it as. If you declare the variable with List<Cat>, it typechecks, you can declare it with List<Animal>, and you can declare it with List<Object>. If you declared it as a List<Cat>, you wouldn't be able to reassign it to List<Animal> as that would be unsound.

In Haskell, typeclasses can't be used as the type within a list (so [Cat] is valid in the first example and [Animal] is valid in the second example, but [Animal] isn't valid in the first example), and this seems to be due to impredicative polymorphism not being supported in Haskell (not 100% sure). Haskell lists are defined something like [a] = [] | a : [a]. [x, y, z] is just syntatic sugar for x : (y : (z : [])). So consider the example in Haskell. Let's say you type [Dog] in the repl (this is equivalent to Dog : [] btw). Haskell infers this to have the type [Dog]. But if you were to give it Cat at the front, like [Cat, Dog] (Cat : Dog : []), it would match the 2nd constructor (:), and would infer the type of Cat : ... to [Cat], which Dog : [] would fail to match.

Answer 3

Since others have explained how you can avoid existential types in many cases, I figured I'd point out why you might want them. The simplest example I can think of is called Coyoneda:

data Coyoneda f a = forall x. Coyoneda (x -> a) (f x)

Coyoneda f a holds a container (or other functor) full of some type x and a function that can be mapped over it to produce an f a. Here's the Functor instance:

instance Functor (Coyoneda f) where
  fmap f (Coyoneda g x) = Coyoneda (f . g) x

Note that this does not have a Functor f constraint! What makes it useful? To explain that takes two more functions:

liftCoyoneda :: f a -> Coyoneda f a
liftCoyoneda = Coyoneda id

lowerCoyoneda :: Functor f => Coyoneda f a -> f a
lowerCoyoneda (Coyoneda f x) = fmap f x

The cool thing is that fmap applications get built up and performed all together:

lowerCoyoneda . fmap f . fmap g . fmap h . liftCoyoneda

is operationally

fmap (f . g . h)

rather than

fmap f . fmap g . fmap h

This can be useful if fmap is expensive in the underlying functor.