Add a Heterogeneous List (HList)

[danieldietrich]

When combining Validation results, the Validation Builders use Tuples. Because we currently only have 8 Tuples, Validation is limited to 8 combined results.

Goal of this issue is to increase the limit. There are multiple ways to do so:

• increase the number of Tuples, Functions, CheckedFunctions etc. This is considered not to be practicable for many reasons (pollution of the API, bad type inference performance of IDEs & Compilers, ...)
• Add a Heterogeneous List (namely HList). This seems like a general way to store values of different types. We need to analyze the API and if it fits the requirements of increasing the number of combined Validation results.
• more?

[danieldietrich]

Scala's HList has type inference:

def flatten[T <: Product, L <: HList](t : T)
  (implicit hl : HListerAux[T, L], flatten : Flatten[L]) : flatten.Out =
    flatten(hl(t))

val t1 = (1, ((2, 3), 4))
val f1 = flatten(t1)     // Inferred type is Int :: Int :: Int :: Int :: HNil
val l1 = f1.toList       // Inferred type is List[Int]

val t2 = (23, ((true, 2.0, "foo"), "bar"), (13, false))
val f2 = flatten(t2)
val t2b = f2.tupled
// Inferred type of t2b is (Int, Boolean, Double, String, String, Int, Boolean)

It is said to be nothing more than a stack of Tuple2:

def hcons[A,B](head : A, tail : B) = (a,b)
def hnil = Unit

hcons("foo", hcons(3, hnil)) : (String, (Int, Unit))

Question: How would a sketch of a simple HList implementation look like based on Java/Javaslang?

• sketch an interface HList with implementations HList.Cons and HList.Nil
• methods of our spike are head(), tail() and isEmpty()
• what is the type of HList.of(1, "a", true)?

[danieldietrich]

Let's start with this:

package javaslang.collection;

public interface HList<L extends HList<L>> {

    static HList nil() {
        return HNil.INSTANCE;
    }

    static <H, T extends HList<T>> HList<HCons<H, T>> cons(H head, T tail) {
        return new HCons<H, T>(head, tail);
    }

    static <H> HCons<H, HNil> of(H element) {
        return of(element, nil());
    }

    boolean isEmpty();

    <E> HCons<E, L> prepend(E element);

    // I think head and tail cannot be part of this interface but need to be moved to HCons

    ? head();

    ? tail();

    final class HNil extends HList<HNil> {

        private static final HNil INSTANCE = new HNil();

        private HNil() {
        }

        @Override
        public boolean isEmpty() {
            return true;
        }

        @Override
        public <E> HCons<E, HNil> prepend(E element) {
            return HList.cons(element, this);
        }
        ...
    }

    final class HCons<H, T extends HList<T>> extends HList<HCons<H, T>> {

        private final H head;
        private final T taill;

        private HCons(H head, T tail) {
            this.head = head;
            this.tail = tail;
        }

        @Override
        public boolean isEmpty() {
            return false;
        }

        @Override
        <E> HCons<E, HCons<H, L>> prepend(E element) {
            return HList.cons(element, this);
        }
        ...
    }
}

[danieldietrich]

First thoughts:

Looking at this example impl, I think HLists cannot be constructed by varargs factory methods like HList.of(1, "a", true, 1.0d) without loosing type information. HList needs to be constructed element-by-element.

When building them it is practicable to append elements. When reading them it is practicable to read from oldest (left) to newest (right). Currently we have prepend, i.e. element are read in the different order. Do we really need to reverse them for reading them in the right order or can we write a more smart HList?

[danieldietrich]

This reading: https://apocalisp.wordpress.com/2008/10/23/heterogeneous-lists-and-the-limits-of-the-java-type-system/

[danieldietrich]

The Validation Builders could still use Tuples until Tuple8 and then switch automatically to HList.

In practice, for reasons of readability, the variable types could be moved off-screen ;-p

[danieldietrich]

This is a purely theoretical construct and can currently not implemented in Java in a practical way.

Snippet from the apocalisp blog (see link above):

    // A lot of type annotation
    final HAppend<HNil, HCons<Double, HCons<String, HCons<Integer[], HNil>>>,
      HCons<Double, HCons<String, HCons<Integer[], HNil>>>> zero = append();
    final HAppend<HCons<Boolean, HNil>, HCons<Double, HCons<String, HCons<Integer[], HNil>>>,
      HCons<Boolean, HCons<Double, HCons<String, HCons<Integer[], HNil>>>>> one = append(zero);
    final HAppend<HCons<Integer, HCons<Boolean, HNil>>, HCons<Double, HCons<String, HCons<Integer[], HNil>>>,
      HCons<Integer, HCons<Boolean, HCons<Double, HCons<String, HCons<Integer[], HNil>>>>>> two = append(one);
    final HAppend<HCons<String, HCons<Integer, HCons<Boolean, HNil>>>,
      HCons<Double, HCons<String, HCons<Integer[], HNil>>>,
      HCons<String, HCons<Integer, HCons<Boolean, HCons<Double, HCons<String, HCons<Integer[], HNil>>>>>>>
      three = append(two);