What is the Haskell equivalent of Java's Curiously Recurring Generic Pattern?

Question

A question just came up about java generics. The example code is:

public interface A < T extends A < T> > {

}  

A linked question asks about

Class Enum<E extends Enum<E>> ...

When I try to read the java documentation about these kinds of generic expressions, my eyes glaze over and it's Greek to me.

I'm hoping that I can understand them in terms of the Haskell equivalent!

What is the equivalent (or similar) in Haskell of one or both of these examples?

Answer 1

This trick is used to allow the interface to refer to the concrete implementation type, for example to enforce that the type of the argument and the type of the result are the same type as the implementing class in something like this:

public interface Num<A extends Num<A>> {
    A add(A other); 
}

This is similar to what you get for free with type classes in Haskell:

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

Answer 2

This is interesting, as this has perplexed me also. Let's try to model it. I will probably not end up with the same thing this idiom is used for in Java.

If a type A inherits from a type B, in functional land that means that there is a function B -> A. Do not worry about the difference between classes and interfaces at this point; there is little difference in the functional translation (an interface is just a record of functions). Let's do a non-recursive translation to get a feel for it:

interface Showable {
    string show();
}

interface Describer<T extends Showable> { }

Translating to records of functions:

data Showable = Showable { show :: String }

data Describer t = Describer { showable :: t -> Showable }

If we forget about downcasting, then if we have some object in Java such that all we know about it is that it is a Showable, then it corresponds to having a Showable object in Haskell. On the surface, passing a Showable and passing a string feel like different things, but they are equivalent.

The extends Showable constraint enters in that if we have a Describer t then we know that t "is" Showable; i.e. there exists a function t -> Showable.

makeDescriber :: (t -> Showable) -> Describer t
makeDescriber f = Describer { showable = f }

Now let's go to hammar's exmaple, incorporating polymorphism.

interface Number<A extends Number<A>> {
    A add(A other); 
}

translating to a record of functions

data Number a = Number {
    add :: a -> a,
    number :: a -> Number a
}

So now if we have a Number a, then we know that a "is" a Number a; i.e. there is a function a -> Number a.

Instances of the java interface Number become functions on a type.

intNumber :: Integer -> Number Integer
intNumber x = Number { add = \y -> x + y, number = intNumber }

This function corresponds to a class Integer extends Number<Integer>. If we have two integers x and y, we can add them using this "OO" style:

z :: Integer -> Integer -> Integer
z x y = intNumber x `add` y

And what about the generic function:

T Add< T extends Number<T> >(T x, T y) { return x.add(y); }

(hmm is that correct Java syntax? My experience of this style is from C#)

Remember the constraints become functions, so:

add' :: (t -> Number t) -> t -> t -> t
add' n x y = n x `add` y

Of course, in Haskell, we see how bundling an object together with the operations it supports is kind of convoluted, so we prefer to separate them:

data Num t = Num { add :: t -> t -> t }

add' :: Num t -> t -> t -> t
add' n x y = add n x y

And we instantiate the Num dictionary with the actual operations, eg.

integerNum :: Num Integer
integerNum = Num { add = (+) }

Typeclasses are just a bit of syntactic sugar over this latter idea.

Maybe that helps? I just wanted to see how it would translate literally.