Implementing Path dependent Map types in Shapeless

Question

I am wanting to put together a map which contains path dependent type mapping from outer to inner:

import shapeless._
import shapeless.ops.hlist._

abstract class Outer {
  type Inner
  def inner: Inner
}

private case class Derp(hl: HList) {
  def get(outer: Outer): outer.Inner = hl.select[outer.Inner]
  def put(outer: Outer)(inner: outer.Inner): Derp = Derp(hl :: inner :: HNil)
  def delete(outer: Outer)(c: outer.Inner): Derp = ???
}

The theory is that by using an HList, I can avoid using type selectors and ensure that programs can only get at an instance of Inner that was created by Outer.

Is this possible, or even a good idea? Most of the HList questions seem to be about arity and case classes, and I feel like I'm working outside the box.

Note that I am aware of https://stackoverflow.com/a/30754210/5266 but this question is about the Shapeless HList implementation in particular -- I don't know how to remove elements from HList and potentially return Option[outer.Inner].

Jeremy Jeremy · Accepted Answer · 2018-01-17T07:39:02

First, you'll almost certainly need to parameterize Derp:

case class Derp[L <: HList](hl: L)

This is because whenever you have a Derp, the compiler will need to know what its static HList type is in order to do anything useful.

HList types encode the information about every type in the list – like

type Foo = Int :: String :: Boolean :: HNil

As soon as you say hl: HList, that information is lost.

Next, you'll want to properly specify the return types of your operations:

def get[O <: Outer](o: O)(implicit selector: Selector.Aux[L, o.type, o.Inner]): o.Inner = selector(hl)

def put[O <: Outer](o: O)(i: o.Inner): Derp[FieldType[o.type, o.Inner] :: L] = copy(hl = field[o.type](i))

This is "tagging" each Inner value with the Outer's type, so you can retrieve it later (which is what the Selector.Aux does). All interesting stuff in Shapeless happens through typeclasses that come with it (or that you define yourself), and they rely on type information to work. So the more type information you can retain in your operations, the easier it will be.

In this case, you'll never return Option, because if you try to access a value that isn't in the map, it won't compile. This is typically what you'd use HList for, and I'm not sure it matches your use case.

Shapeless also has HMap, which uses key-to-value mappings like a normal Map. The difference is that each key type can map to a different value type. This seems more in line with your use case, but it's organized a bit differently. To use HMap, you define a relation, as a type function. A type function is a typeclass with a dependent type:

trait MyRelation[Key] {
  type Value
}

object MyRelation {
  type Aux[K, V] = MyRelation[K] { type Value = V }

  implicit val stringToInt: Aux[String, Int] = new MyRelation[String] { type Value = Int }
  implicit val intToBool: Aux[Int, Boolean] = new MyRelation[Int] { type Value = Boolean }

}

Now you can define an HMap over MyRelation, so when you use String keys you'll add/retrieve Int values, and when you use Int keys you'll add/retrieve Boolean values:

val myMap = HMap[MyRelation.Aux]("Ten" -> 10, 50 -> true)
val myMap2 = myMap + ("Fifty" -> 50)
myMap2.get("Ten") // Some(10), statically known as Option[Int]
myMap2.get(44)    // None, statically known as Option[Boolean]

This is a bit different from your example, in that you have a value with a dependent type, and you want to use the outer type as the key, and the inner type as the value. It's possible to express this as a relation for HMap as well, by using K#Inner =:= V as the relation. But it will often surprise you by not working, because path-dependent types are tricky and really depend on concrete subtypes of the outer (which will require a lot of boilerplate) or singleton types (which will be difficult to pass around without losing the necessary type information).

Implementing Path dependent Map types in Shapeless

1 Answers