Introduction

(Just skip the intro section if you already know all this stuff.)

What is a "Finite Type"?

Mathematically speaking, a "class" is just a set of objects -- specifically, the set of all possible unique instances that can be created from it. Essentially, when you write the code for a class, you're writing a set builder that can be used to generate the elements of that set. Furthermore, a "finite set" refers to a set with a finite cardinality, which is handy because it's generally difficult to perform operations on infinite sets. As an example, consider this class:

class SetOfTwo {
  final boolean value;
  
  SetOfTwo(boolean value) {
    this.value = value;
  }
}

This class has cardinality two, since it can only take on two distinct instances -- the one where value = true and the one where value = false. Thus, this class is a finite type because two is, by all conventional laws of mathematics, finite.

What is an "Algebraic Type"?

While types may be sets, they themselves belong to another set -- the set of all types. This superset is equipped with a very handy property: we can compose types to create more types using the set operations that we all know and love. You've almost certainly done this before in your own code, but you might not recognize it for what it is. Consider this example:

class Brand {
  final String name;
  
  Brand(String name) {
    this.name = name;
  }
}

class Colour {
  final int rgb;
  
  Colour(int rgb) {
    this.rgb = rgb;
  }
}

class Car {
  final Brand brand;
  final Colour colour;
  
  Car(Brand brand, Colour colour) {
    this.brand = brand;
    this.colour = colour;
  }
}

Seems like your everyday Java class, right? But what we've done here is use the Cartesian product set operation to join two sets! By defining the class Car as a tuple (Brand, Colour) drawing an element from Brand and another from Colour, we've successfully constructed an entirely new class by composing the elements of existing classes.

It's also worth noting that the cardinality of the new class |Car| is equal to the product of the cardinalities of the component classes |Brand| * |Colour|. This is exactly what we expect for a Cartesian product.

See this kata for more details on algebraic types...

Then, What's a "Finite Algebraic Type"?

A finite algebraic type is simply an algebraic type that is also finite. As a trivial example, consider a singleton class Unit, which by definition satisfies |Unit| = 1. We could then use the Cartesian product to create a class (Unit, Unit), which would also necessarily satisfy |(Unit, Unit)| = 1. This logically makes sense, since a pair created from elements of a set with only one element can obviously have only one distinct instance.

Pre-loaded

This kata is pre-loaded with various classes that are used to compose algebraic types, the source code of which can be found in this Gist. You really should read the full source, but a brief summarization of the types defined therein is presented below. Since Java does not support true algebraic types, they are instead implemented as no-op interfaces with concrete classes implementing each component type. All the types also implement Finite to ensure that a reasonable lower bound can be imposed.

Nil := {}
Unit := { Unit }

Maybe a := Just a | Nothing
Either a b := Left a | Right b
Pair a b := Pair a b
Mapping a b := a -> b

Also pre-loaded is a TypeToken class used to transfer data about parameterized types. Since Java lacks built-in reified generics, TypeToken is used as a compromise. The full source code is available in this Gist. If you wish to write extensive tests, it might be worth reading through the full source, but a brief summarization of the outwards-facing parts is presented below for those less inclined. Note that T and parameters are now qualified with extends Finite, a change made so you don't have to do extra unnecessary typecasting for this kata:

class TypeToken<T extends Finite> {
  
  /**
   * The base class represented by this type token.
   */
  final Class<T> type;
  
  /**
   * The type parameters to the base class represented by this type token.
   */
  final TypeToken<? extends Finite>[] parameters;

}

Specification

You will need to write a method that takes a TypeToken for a finite algebraic type and produces the set equal to that type (i.e. all the possible unique instances that type can take on):

/**
 * Given a finite algebraic type, computes the set of all possible values in that type.
 * @param type The type to explode.
 * @return The set of all possible values the given type can take on.
 */
Set<Finite> explode(TypeToken<? extends Finite> type);

As an example, suppose we receive a type token representing the type Maybe<Unit>. This type can take on one of two values: Just Unit and Nothing. We could naively implement this logic like this:

public static Set<Finite> explode(TypeToken<? extends Finite> type) {
  if (type.type == Maybe.class && type.parameters[0].type == Unit.class) {
    return Set.of(new Just<>(Unit.INSTANCE), new Nothing<>());
  } else {
    // other stuff here...
  }
}

Stuff Worth Noting

Constructing Mappings

Mappings A -> B are constructed as maps. You can chain bind calls to build a mapping like this:

Mapping<Maybe<Unit>, Unit> mapping = new Mapping<>()
    .bind(new Just<>(Unit.INSTANCE), Unit.INSTANCE)
    .bind(new Nothing<>(), Unit.INSTANCE);

Other Information

• You will never have to think about null in this kata. Nullability is evil!
• The methods equals, hashCode, and toString have already been implemented for all the pre-loaded classes to save you the trouble.

Good luck! I hope you did your homework!