Existential types in Haskell and generics in other languages

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 = (drawCicrle center radius, pi * radius * radius)
rectangle topLeft bottomRight = (drawRectangle topLeft bottomRight, 
           abs $ (topLeft.x-bottomRight.x) * (topLeft.y-bottomRight.y))

shapes = [circe (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 and 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.


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.

Tags:

Haskell

Existential Type

Recent Posts