/**
 * N-tuples -- type safe and compile-time checked tuples that can be composed up to an arbitrary size.
 *
 * Sometimes referred to a HLists from the Haskell library by that name. HList is short for heterogeneous list, which accurately
 * reflects their structure in the type system: a singly linked list composed of cons cells and a terminating Nil. However, from
 * a usage perspective they more closely resemble tuples.
 */
object NTuples {
    /** The supertype of NTuples of any size */
    sealed trait NTuple {
        /** Convert an NTuple to an erased list */
        def toList: List[Any]
    }

    /** The "Nil" for NTuples, must be at the end of an NTuple to signal the termination of the list */
    final class NTupleEnd private[NTuples] () extends NTuple {
        /** Produce a new NTuple with the given element as the sole one */
        def :+: [A] (lhs: A): A :+: NTupleEnd = NTupleElement(lhs, this)

        def toList = Nil
    }

    /** The singleton NTupleEnd. Done this way rather than using objects because of Scala's strange handling of object types */
    val NTupleEnd = new NTupleEnd

    /** Cons cell of NTuples, with one element and the rest of the NTuple */
    final case class NTupleElement[B, C <: NTuple](head: B, tail: C) extends NTuple {
        /** Produce a new NTuple with the given element prepended to this NTuple */
        def :+: [A] (lhs: A): A :+: B :+: C = NTupleElement(lhs, this)
        def toList = head :: tail.toList
    }

    /** Type alias for NTupleElement which makes typing naming and construction more succint */
    type :+: [Head, Tail <: NTuple] = NTupleElement[Head, Tail]

    /** Extractor object so that NTuples can be matched */
    object :+: {
        def unapply[A, B <: NTuple](in: NTupleElement[A, B]): Option[(A, B)] = Some(in.head, in.tail)
    }
}