Question regarding 15.10 (Type Classes)

[edufuga]

Question regarding 15.10 (Type Classes)

Disclaimer: I didn't fully read the book in order yet, so excuse me in case that my remarks and questions are just an outcome of that.

After reading section 15.10 on Type Classes, I have some trouble understanding the remarks on page 249 and 250 about the zero and fromInt, in the context of the comparison between subtype polymorphism and type classes.

Specifically, this sentence is causing me some trouble:

...you could not rely on subtype polymorphism to implement the average function because there would be no way to obtain a value zero and a function fromInt for a given subtype A.

Question: What does "obtain a value" mean?

As I understand it, if the hypothetical Number supertype had the abstract method fromInt, and zero implemented as fromInt(0) (which is what Numeric does), then I don't see any problem with using subtyping: the concrete subtype like Double or BigDecimal would just implement the fromInt method, to provide the missing functionality. This is the typical Template Method Pattern (which may often be misused in practice).

My point/question is therefore: Am I missing the point? Is this really something one can't do with subtyping, or is it just a different way to structure the code, depending on whether one favors OOP (subtype polymorphism) or FP (ad hoc polymorphism)?

That said, I'm really enjoying the book so far :)

[charpov]

My answer to your question: Both!

Type classes are an alternative for FP languages that don't support subtype polymorphism, such as Haskell. Many problems can be solved with one or the other. Still, there are things that one does better than the other. For instance, uniform processing of a heterogeneous collection, as in Listing 15.4, is a natural use of subtype polymorphism, but is awkward to write using type classes. On the other hand, the average function from Listing 15.15 cannot be written with subtype polymorphism. The reason is that a type class lets you associate values and functions with the type itself, which has no equivalent with subtype polymorphism.

In Scala, Numeric is a type class, which can store a fromInt function. A regular fromInt method, like you suggest, won't work because you would need an object on which to invoke the method. Java has subtype polymorphism but no type classes. Try and write a Java equivalent to Listing 15.15. I can't do it.

The closest I can get would be something like this:

interface Number<A> {
  A plus(A x);
  A divideByInt(int n);
}

public static <A extends Number<A>> A average(List<A> numbers) {
  if (numbers.isEmpty()) throw new IllegalArgumentException();
  var i = numbers.iterator();
  A sum = i.next();
  while (i.hasNext())
    sum = sum.plus(i.next());
  return sum.divideByInt(numbers.size());
}

This works fine, but cannot handle empty lists. Adding a fromInt method to interface Number doesn't help because there's no Number object to invoke it on when the list is empty.

By the way, while the mechanics were always easy to understand, it took me a while to grasp the benefits and proper use of type classes. It's when I faced the task of writing common tests for two separate (and type-unrelated) implementations of the same functionalities that I finally understood how I could benefit from type classes. They let you bridge unrelated types and bring new types into a pre-existing framework (like type Memo in the example pages 248-249).

[edufuga]

Emulating Type Classes in Java

Thank you for your answer! I really appreciate the time and effort, and it's also motivating to engage more actively with the book 🥇.

I suspect the source of confusion from my part is on the interpretation of concepts such as "type classes" or even "subtyping".

I started to write an answer yesterday, but then I decided that I should indeed give it a try and implement Listing 15.15 (with all the necessary things like the Numeric and Fractional types), i.e. the average of a list of numbers of a given type.

Here is what I came up with:

import java.util.ArrayList;
import java.util.List;

interface Numeric<T> {
    T plus(T first, T second);

    T fromInt(Integer number);

    default T zero() {
        return fromInt(0);
    }
}

interface Fractional<T> extends Numeric<T> {
    T div(T numerator, T denominator);
}

interface NumericInt extends Numeric<Integer> {
    @Override
    default Integer fromInt(Integer number) {
        return number;
    }

    @Override
    default Integer plus(Integer first, Integer second) {
        return first + second;
    }
}

interface NumericDouble extends Numeric<Double> {
    @Override
    default Double fromInt(Integer number) {
        return number.doubleValue();
    }

    @Override
    default Double plus(Double first, Double second) {
        return first + second;
    };
}

interface FractionalDouble extends Fractional<Double>, NumericDouble {
    @Override
    default Double div(Double numerator, Double denominator) {
        return numerator / denominator;
    }
}

class FractionalDoubleEvidence implements FractionalDouble {}

interface FractionalOperations<T> {
    Fractional<T> evidence();

    default T average(List<T> numbers) {
        if (numbers.isEmpty()) {
            return evidence().zero();
        }
        else {
            return evidence().div(
                    numbers.stream().reduce(evidence().zero(), evidence()::plus),
                    evidence().fromInt(numbers.size())
            );
        }
    }
}

class FractionalDoubleOperations implements FractionalOperations<Double> {
    @Override
    public Fractional<Double> evidence() {
        return new FractionalDoubleEvidence();
    }
}

class Scratch {
    // This method corresponds to Listing 15.15 of Page 249.
    // Java has no Context Bounds nor Contextual Abstractions, so things need to be passed explicitly, instead of being
    // rewritten and injected by the compiler.
    public static <T> T average(Fractional<T> evidence, List<T> numbers) {
        return ((FractionalOperations<T>) () -> evidence).average(numbers);
    }

    public static void main(String[] args) {
        System.out.println("First approach to Type Classes as a Pattern, expressible with Java without any comfort");

        /* Without a static average method */
        final FractionalDoubleOperations ops = new FractionalDoubleOperations();

        final List<Double> numbers = List.of(0.0d, 1.0d, 2.0d, 3.0d, 4.0d); // 2.0
        System.out.println(ops.average(numbers));

        final List<Double> empty = new ArrayList<>();
        System.out.println(ops.average(empty)); // 0.0

        /* With a static average method */
        System.out.println(average(new FractionalDoubleEvidence(), numbers)); // 2.0
        System.out.println(average(new FractionalDoubleEvidence(), empty));   // 0.0
    }
}

In the end, this is all very clunky, because Java doesn't have the build-in support for the type class pattern, which is (in my understanding) a consequence of having contextual abstraction (implicits) and context bounds (the A : Fractional in the average method of Listing 15.15). Therefore I needed to create so many types by hand and pass things explicitly in the code.

Edit: In the end, my own understanding/interpretation of type classes is (as you mentioned) as a sort of "adapter" or "bridge" between two unrelated types (i.e. without any common supertypes). So yes, this is a different concept than subtyping, and all I did was to question whether one could do the same in Java / with subtyping and generics (without the comfort of Scala).

[edufuga]

Subtyping version in Java

Ok, I think now I really understand what you meant with the sentence I quoted:

...you could not rely on subtype polymorphism to implement the average function because there would be no way to obtain a value zero and a function fromInt for a given subtype A.

I also understand better your sentence

The reason is that a type class lets you associate values and functions with the type itself, which has no equivalent with subtype polymorphism.

(The rest of the following comments are just to elaborate on those points, so feel free to skip them entirely.)

Indeed, only by using subtyping, without emulating typeclasses (implementing them as a pattern), as I did in my previous comment, it's not possible to implement the average function/method without passing a zero value explicitly.

In other words: Subtyping needs an initial object, from which to call methods from. This sounds/is obvious, in and by itself, but it does have interesting implications on what's possible to do with it.

This is what I came up with, when trying to implement the average method only using Java's subtyping and generics:

import java.util.List;
import java.util.function.Supplier;
import java.util.stream.Collectors;

interface Number<T extends java.lang.Number> {
    T value();

    Number<T> plus(Number<T> that);

    // Ideally, this should be a STATIC method (constructor-like), but that's NOT POSSIBLE if the interface is GENERIC.
    // It's not possible, because static methods need to be implemented in the interface.
    // That makes sense, since a generic type is a type constructor itself, which means there isn't a single type.
    // Actually, a PROBLEM or CONSTRAINT due to the way generics are implemented in Java and Scala (type erasure), is
    // that we CAN'T CONSTRUCT an instance only from the generic type T (because it's erased by the compiler).
    // We can't instantiate the type. The only possibility is to pass a function/closure/lambda, that will construct the
    // instance of the type.
    // In other words: Instantiating the specific Number<T> (for a specific T) belongs to the implementation, not to the
    // interface. This means that the "starting" point (the initial number) needs to be passed from the outside.
    Number<T> fromInt(Integer number);

    // Notice that in order to call this method, we already need an OBJECT of (sub)type Number<T>. It suffers the same
    // problems as the "fromInt" method.
    default Number<T> zero() {
        return fromInt(0);
    }
}

interface Fraction<T extends java.lang.Number> extends Number<T> {

    // Covariant override (more specific return type)
    @Override
    Fraction<T> plus(Number<T> that);

    T div(Number<T> that);
}

class DoubleNumber implements Number<Double> {
    private final double value;

    public DoubleNumber(double value) {
        this.value = value;
    }

    @Override
    public Double value() {
        return this.value;
    }

    @Override
    public DoubleNumber plus(Number<Double> that) {
        return new DoubleNumber(this.value() + that.value());
    }

    @Override
    public DoubleNumber fromInt(Integer number) {
        return new DoubleNumber(number.doubleValue());
    }
}

class DoubleFraction implements Fraction<Double> {
    private final double numerator;

    private final double denominator;

    public DoubleFraction(double numerator, double denominator) {
        this.numerator = numerator;
        this.denominator = denominator;
    }

    @Override
    public Double div(Number<Double> that) {
        return this.value() / that.value();
    }

    @Override
    public Double value() {
        return this.numerator/this.denominator;
    }

    @Override
    public Fraction<Double> plus(Number<Double> that) {
        return new DoubleFraction(
                this.numerator + that.value()*this.denominator,
                this.denominator
        );
    }

    @Override
    public Fraction<Double> fromInt(Integer number) {
        return new DoubleFraction(number, 1);
    }
}

class Scratch {

    // Notice the "zeroConstructor", passed as a parameter to the "average" method.
    //  We're not able to instantiate the "T". That doesn't work in Java (nor Scala), due to the type erasure of
    //  generics. This constraint is not really related to subtyping, but is a technical design or decision.
    public static <T extends java.lang.Number> T average(Supplier<Fraction<T>> zeroConstructor, List<Fraction<T>> numbers) {
        if (numbers.isEmpty()) {
            return zeroConstructor.get().value();
        }
        else {
            Fraction<T> numerator = numbers.stream().reduce(zeroConstructor.get(), Fraction::plus);

            // See the comments in the Number<T> interface.
            Number<T> denominator = zeroConstructor.get().fromInt(numbers.size());

            return numerator.div(denominator);
        }
    }

    public static void main(String[] args) {
        final List<Double> numbers = List.of(0.0d, 1.0d, 2.0d, 3.0d, 4.0d);

        final List<Fraction<Double>> fractions = numbers.stream()
                .map(d -> new DoubleFraction(d, 1))
                .collect(Collectors.toList());

        final Supplier<Fraction<Double>> zeroConstructor = () -> new DoubleFraction(0.0d, 1d);

        System.out.println(average(zeroConstructor, fractions)); // 2.0
    }
}

So, while I did indeed implement a working version of the average function as a static method, that function does need to provide the zero value explicitly.

Having default and static method in interfaces does not bring anything at all, since (a) for default methods you do need an initial object, and (b) you can't have static methods in generic types, since those types are generic!

I believe an additional constraint is due to the type erasure of generics in Java and Scala. Since we don't have information on the type T, we can't instantiate it in the code. We can't just construct an instance (like the zero value) of type T in the code of the generic interface. I believe this is the core of the problem.

In short: Your answer is satisfactory now. It made me think and try to write two different Java versions (type classes VS subtyping solution), which made it finally click.

[charpov]

I'm glad we're on the same page. If you like the book, don't forget to leave a positive review on Amazon!