Are HLists nothing more than a convoluted way of writing tuples?

Question

I am really interested in finding out where the differences are, and more generally, to identify canonical use cases where HLists cannot be used (or rather, don't yield any benefits over regular lists).

(I am aware that there are 22 (I believe) TupleN in Scala, whereas one only needs a single HList, but that is not the kind of conceptual difference I am interested in.)

I've marked a couple of questions in the text below. It might not actually be necessary to answer them, they are more meant to point out things that are unclear to me, and to guide the discussion in certain directions.

Motivation

I've recently seen a couple of answers on SO where people suggested to use HLists (for example, as provided by Shapeless), including a deleted answer to this question. It gave rise to this discussion, which in turn sparked this question.

Intro

It seems to me, that hlists are only useful when you know the number of elements and their precise types statically. The number is actually not crucial, but it seems unlikely that you ever need to generate a list with elements of varying but statically precisely known types, but that you don't statically know their number. Question 1: Could you even write such an example, e.g., in a loop? My intuition is that having a statically precise hlist with a statically unknown number of arbitrary elements (arbitrary relative to a given class hierarchy) just isn't compatible.

HLists vs. Tuples

If this is true, i.e, you statically know number and type - Question 2: why not just use an n-tuple? Sure, you can typesafely map and fold over an HList (which you can also, but not typesafely, do over a tuple with the help of productIterator), but since number and type of the elements are statically known you could probably just access the tuple elements directly and perform the operations.

On the other hand, if the function f you map over an hlist is so generic that it accepts all elements - Question 3: why not use it via productIterator.map? Ok, one interesting difference could come from method overloading: if we had several overloaded f's, having the stronger type information provided by the hlist (in contrast to the productIterator) could allow the compiler to choose a more specific f. However, I am not sure if that would actually work in Scala, since methods and functions are not the same.

HLists and user input

Building on the same assumption, namely, that you need to know number and types of the elements statically - Question 4: can hlists be used in situations where the elements depend on any kind of user interaction? E.g., imagine populating an hlist with elements inside a loop; the elements are read from somewhere (UI, config file, actor interaction, network) until a certain condition holds. What would the type of the hlist be? Similar for an interface specification getElements: HList[...] that should work with lists of statically unknown length, and that allows component A in a system to get such a list of arbitrary elements from component B.

Answer 1

Addressing questions one to three: one of the main applications for HLists is abstracting over arity. Arity is typically statically known at any given use site of an abstraction, but varies from site to site. Take this, from shapeless's examples,

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)

Without using HLists (or something equivalent) to abstract over the arity of the tuple arguments to flatten it would be impossible to have a single implementation which could accept arguments of these two very different shapes and transform them in a type safe way.

The ability to abstract over arity is likely to be of interest anywhere that fixed arities are involved: as well as tuples, as above, that includes method/function parameter lists, and case classes. See here for examples of how we might abstract over the arity of arbitrary case classes to obtain type class instances almost automatically,

// A pair of arbitrary case classes
case class Foo(i : Int, s : String)
case class Bar(b : Boolean, s : String, d : Double)

// Publish their `HListIso`'s
implicit def fooIso = Iso.hlist(Foo.apply _, Foo.unapply _)
implicit def barIso = Iso.hlist(Bar.apply _, Bar.unapply _)

// And now they're monoids ...

implicitly[Monoid[Foo]]
val f = Foo(13, "foo") |+| Foo(23, "bar")
assert(f == Foo(36, "foobar"))

implicitly[Monoid[Bar]]
val b = Bar(true, "foo", 1.0) |+| Bar(false, "bar", 3.0)
assert(b == Bar(true, "foobar", 4.0))

There's no runtime iteration here, but there is duplication, which the use of HLists (or equivalent structures) can eliminate. Of course, if your tolerance for repetitive boilerplate is high, you can get the same result by writing multiple implementations for each and every shape that you care about.

In question three you ask "... if the function f you map over an hlist is so generic that it accepts all elements ... why not use it via productIterator.map?". If the function you map over an HList really is of the form Any => T then mapping over productIterator will serve you perfectly well. But functions of the form Any => T aren't typically that interesting (at least, they aren't unless they type cast internally). shapeless provides a form of polymorphic function value which allows the compiler to select type-specific cases in exactly the way you're doubtful about. For instance,

// size is a function from values of arbitrary type to a 'size' which is
// defined via type specific cases
object size extends Poly1 {
  implicit def default[T] = at[T](t => 1)
  implicit def caseString = at[String](_.length)
  implicit def caseList[T] = at[List[T]](_.length)
}

scala> val l = 23 :: "foo" :: List('a', 'b') :: true :: HNil
l: Int :: String :: List[Char] :: Boolean :: HNil =
  23 :: foo :: List(a, b) :: true :: HNil

scala> (l map size).toList
res1: List[Int] = List(1, 3, 2, 1)

With respect to your question four, about user input, there are two cases to consider. The first is situations where we can dynamically establish a context which guarantees that a known static condition obtains. In these kinds of scenarios it's perfectly possible to apply shapeless techniques, but clearly with the proviso that if the static condition doesn't obtain at runtime then we have to follow an alternative path. Unsurprisingly, this means that methods which are sensitive to dynamic conditions have to yield optional results. Here's an example using HLists,

trait Fruit
case class Apple() extends Fruit
case class Pear() extends Fruit

type FFFF = Fruit :: Fruit :: Fruit :: Fruit :: HNil
type APAP = Apple :: Pear :: Apple :: Pear :: HNil

val a : Apple = Apple()
val p : Pear = Pear()

val l = List(a, p, a, p) // Inferred type is List[Fruit]

The type of l doesn't capture the length of the list, or the precise types of its elements. However, if we expect it to have a specific form (ie. if it ought to conform to some known, fixed schema), then we can attempt to establish that fact and act accordingly,

scala> import Traversables._
import Traversables._

scala> val apap = l.toHList[Apple :: Pear :: Apple :: Pear :: HNil]
res0: Option[Apple :: Pear :: Apple :: Pear :: HNil] =
  Some(Apple() :: Pear() :: Apple() :: Pear() :: HNil)

scala> apap.map(_.tail.head)
res1: Option[Pear] = Some(Pear())

There are other situations where we might not care about the actual length of a given list, other than that it is the same length as some other list. Again, this is something that shapeless supports, both fully statically, and also in a mixed static/dynamic context as above. See here for an extended example.

It is true, as you observe, that all of these mechanism require static type information to be available, at least conditionally, and that would seem to exclude these techniques from being usable in a completely dynamic environment, fully driven by externally provided untyped data. But with the advent of the support for runtime compilation as a component of Scala reflection in 2.10, even this is no longer an insuperable obstacle ... we can use runtime compilation to provide a form of lightweight staging and have our static typing performed at runtime in response to dynamic data: excerpt from the preceding below ... follow the link for the full example,

val t1 : (Any, Any) = (23, "foo") // Specific element types erased
val t2 : (Any, Any) = (true, 2.0) // Specific element types erased

// Type class instances selected on static type at runtime!
val c1 = stagedConsumeTuple(t1) // Uses intString instance
assert(c1 == "23foo")

val c2 = stagedConsumeTuple(t2) // Uses booleanDouble instance
assert(c2 == "+2.0")

I'm sure @PLT_Borat will have something to say about that, given his sage comments about dependently typed programming languages ;-)

Answer 2

Just to be clear, an HList is essentially nothing more than a stack of Tuple2 with slightly different sugar on top.

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

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

So your question is essentially about the differences between using nested tuples vs flat tuples, but the two are isomorphic so in the end there really is no difference except convenience in which library functions can be used and which notation can be used.

Answer 3

There are a lot of things you can't do (well) with tuples:

• write a generic prepend/append function
• write a reverse function
• write a concat function
• ...

You can do all of that with tuples of course, but not in the general case. So using HLists makes your code more DRY.

Answer 4

I can explain this in super simple language:

The tuple vs list naming isn't significant. HLists could be named as HTuples. The difference is that in Scala+Haskell, you can do this with a tuple (using Scala syntax):

def append2[A,B,C](in: (A,B), v: C) : (A,B,C) = (in._1, in._2, v)

to take an input tuple of exactly two elements of any type, append a third element, and return a fully typed tuple with exactly three elements. But while this is completely generic over types, it has to explicitly specify the input/output lengths.

What a Haskell style HList lets you do is make this generic over length, so you can append to any length of tuple/list and get back a fully statically typed tuple/list. This benefit also applies to homogeneously typed collections where you can append an int to a list of exactly n ints and get back a list that is statically typed to have exactly (n+1) ints without explicitly specifying n.