How to define heterogeneous list?

1

I’m struggling to define a type for heterogeneous lists (lists where its elements can be of different types). In Scala, it can be done with the following.

sealed trait HList[+H, +T]
case class Cons[+H, +LH, +LT](head: H, tail: HList[LH, LT]) extends HList[H, HList[LH, LT]]
case object Nil extends HList[Nothing, Nothing]

Could anyone help me with the definition of a heterogeneous list in ReScript?

2

For the time being you are better off defining it in ML syntax and using it from ReScript (if possible, I’m not sure). Check https://github.com/rescript-lang/syntax/issues/74

3

That GitHub issue seems to be more about redefining the [] and :: constructors in order to use the special list syntax. It’s still possible to define a heterogeneous list using regular constructors.

type rec t<'b, 'c> =
  | Nil: t<'b, 'b>
  | Cons('a, t<'b, 'c>): t<'b, 'a => 'c>

let x = Cons(1, Cons("a", Cons(1.5, Nil)))

Playground link.

4 Likes
4

Are those GADTs? That’s quite interesting, that kind of data structure isn’t possible to define in Elm for example

5

Yep, they’re GADTs. Here’s one explanation on how that particular trick works (in OCaml).

6

I’d recommend a different approach to the problem; if you describe your use-case, there will usually be better solutions.

Drup himself disrecommended such trick.

7

As far as alternatives go, it’s worth mentioning that an HList is basically an extensible tuple. So you could just use a series of chained tuples, and that would achieve the same thing.

E.g.:

let hList = (1, ("Hello", (1.234, ())))

The problem with this solution is that we lose the ability to track the types in a recursive function traversing the data structure, which is the main use case for a GADT-based HList. But that might be okay.

But I generally agree with you, @chenglou. We can probably get rid of the HList idea altogether and use a totally different (and simpler) data structure to solve most problems.

2 Likes