Rust HLists (Heterogenous List)

A heterogeneous list (henceforth “HList”) is a useful abstraction that is implemented in many statically-typed functional programming languages. Unlike normal list-like structures (e.g. Vec, Slice, Array), a heterogenous list is able to hold elements of different types (hence heterogenous) and expose those types in its own type signature.

1
2

let h = hlist!["Joe", "Blow", 30, true];
// h has a static type of: HCons<&str, HCons<&str, HCons<{integer}, HCons<bool, HNil>>>>

Now, you might be thinking “Isn’t that just a tuple?”. The answer is: in a way. Indeed, in terms of data structure, a given implementation of HList is usually really nothing more than deeply nested pairs (tuple of 2 elements) that each hold an element of arbitrary type in its 1st element and knows that its 2nd element is itself an HList-like thing. While it may seem convoluted, HList buys us the ability to abstract over arity, which turns out to be extremely useful, as you can see from this Stackoverflow answer by Miles Sabin, the creater of the Shapeless library, which provides an HList implementation in Scala.

Given that description and justification for the existence of HLists, let’s take a look at how to use Frunk’s implementation of HList in Rust.

Frunk is published to Crates.io, so to begin, add the crate to your list of dependencies:

1
2

[dependencies]
frunk = "0.1.9"

By the way, to take a dive into the deep end, jump straight to HList’s Rustdocs.

Imports

Next, let’s add a few imports. In particular, note that we have a #[macro_use] directive in order to enable the hlist! macro, which makes declaring HLists nicer by saving you the trouble of writing deeply nested HCons.

1
2

#[macro_use] extern crate frunk;
use frunk::hlist::*;

Creating an HList

Making an HList is easy if you use the hlist! macro:

1
2
3
4

let h = hlist!["Joe", "Blow", 30, true];

// You can choose to explicitly annotate the type of HList
let h2: HCons<&str, HCons<&str, HCons<{integer}, HCons<bool, HNil>>>> = hlist!["Joe", "Blow", 30, true];

Writing the type of an HList

Since HLists are a bunch of nested HConss, you may think that writing the type annotation for one would be a PITA. Well, it might have been if not for the type-level macros introduced in Rust 1.13.

1
2
3
4

let h: Hlist!(&str, &str, i32, bool) = hlist!["Joe", "Blow", 30, true];
// We use the Hlist! type macro to make it easier to write
// a type signature for HLists, which is a series of nested HCons
// h has an expanded static type of: HCons<&str, HCons<&str, HCons<i32, HCons<bool, HNil>>>>

Getting the head of an HList

To retrieve the head element of an HList, use the .head accessor

1
2

let h = hList![ "Joe" ];
let joe = h.head;

Getting multiple elements from an HList

To retrieve multiple elements, it’s highly recommended to use the hlist_pat! macro to deconstruct your HList.

1
2
3
4
5
6
7
8

let h = hlist!["Joe", "Blow", 30, true];
// h has a static type of: HCons<&str, HCons<&str, HCons<{integer}, HCons<bool, HNil>>>>

let hlist_pat!(f_name, l_name, age, is_admin) = h;
assert_eq!(f_name, "Joe");
assert_eq!(l_name, "Blow");
assert_eq!(age, 30);
assert_eq!(is_admin, true);

Appending HLists

The Add<RHS> trait is implemented for HList so that you can simply call + to append to an existing HList

1
2
3
4

let joe = hlist!["Joe", "Blow", 30];
let is_admin = hlist![true];

let joe_is_admin = joe + is_admin;

Length

To get the length of an HList, simply call its length() method

1
2

let joe = hlist!["Joe", "Blow", 30];
assert_eq!(joe.length(), 3);

Have fun !

It will be interesting to see what you can cook up with HList. As mentioned before, abstracting over arity allows you to do some really cool stuff, for example Frunk already uses HList to define a Validated abstraction to help accumulate errors over many different Result<T, E> (we’ll go through this in another post):

1
2
3
4
5
6

pub enum Validated<T, E>
    where T: HList
{
    Ok(T),
    Err(Vec<E>),
}

So please check it out, take it for a spin, and come back with any ideas, criticisms, and PRs!

  1. Frunk on Github
  2. Frunk on Crates.io

Comments