HMap.apply can not be used out of the box

[anatoliykmetyuk]

The following program:

object Main extends App {
  import shapeless._

  trait  Key { type Value }
  object Key {
    type Aux[V] = Key { type Value = V }
    def apply[V]: Key.Aux[V] = new Key { type Value = V }
  }

  val name = Key[String]
  val id   = Key[Int   ]

  val map = HMap[(Key.Aux ~?> Id)#λ](
    name -> "John Smith"
  , id   -> 123
  )

  println(map(name))
}

Fails with:

could not find implicit value for parameter cse: shapeless.poly.Case[shapelesshmap.Main.map.type,shapeless.::[shapelesshmap.Main.Key.Aux[String],shapeless.HNil]]
[error]   println(map(name))

This is so, because apply is inherited from Poly1, and it requires an implicit Case instance in scope. HMap class has this instance, but it is not picked up because the map is stored in val.

Normally, we declare Poly as singleton objects, otherwise their Case instances are also not picked up. However, I do not see a type safe way to create an HMap as a singleton object.

The following code works:

object Main extends App {
  import shapeless._

  trait  Key { type Value }
  object Key {
    type Aux[V] = Key { type Value = V }
    def apply[V]: Key.Aux[V] = new Key { type Value = V }
  }

  val name = Key[String]
  val id   = Key[Int   ]

  val map = HMap[(Key.Aux ~?> Id)#λ](
    name -> "John Smith"
  , id   -> 123
  )
  import map.caseRel

  println(map(name))
}

[milessabin]

I agree that the ergonomics aren't perfect here, however you can get close to what you want by defining map as an object,

object map extends HMap[(Key.Aux ~?> Id)#λ](Map(name -> "John Smith", id -> 123))

scala> map(id)
res0: Int = 123

scala> map(name)
res1: String = John Smith

The reason that this works without an import is that the definition of map as an object create an implicit scope with is automatically searched for instances.

[anatoliykmetyuk]

The problem with this solution is that it is not type safe:

  object map extends HMap[(Key.Aux ~?> Id)#λ](Map(name -> 10, id   -> 123))

Compiles perfectly. Further:

val x: Option[String] = map.get(name)

Also works, both on compile and runtime, I think because the type of Option is erased.

Another problem is this:

  object map extends HMap[(Key.Aux ~?> Id)#λ](Map(name -> 10, id   -> 123))
  val m2 = map + (name -> "Foo")

  println(m2(name))

This also fails because implicit Case can not be found. + creates a new map, for which implicits are not available.

I believe this can also be an obstacle for writing combinators for Poly, like andThen or map.

[milessabin]

Agreed. For the object approach to work we would need an HMap constructor which worked similarly to HMap's companion object apply. Would you like to take a swing at that?

[anatoliykmetyuk]

Indeed, this can be a solution. I didn't know it is allowed to have implicit parameters in the constructor, but this worked:

  class Foo(a: Int)(implicit b: String) {
    def f() = println(b)
  }

  implicit val b: String = "foo"

  object foo extends Foo(10)
  foo.f()

However, this will not solve the + problem, since the object created in a method looses its implicit scope when used outside that method.

I think the problem here is that HMap is not an ADT. In fact, I think Poly itself can well be an ADT.

If Poly = Function[HList, _] | AlternativePoly[Poly, Poly], then it is easy to represent both HMap and Poly uniformly. In the current implementation, the Poly is essentially an alternative of ordinary functions.

HMap can be expressed as a set of Poly under alternative, each one defined on a single key type: Alternative[Function[A, B], Tail]. When adding another key-value pair to M <: HMap, the result is Alternative[Function[K, V], M].

The advantage is that we can get rid of the dependency on the self type of the created Polys and HMaps, and hence have combinators on them without related problems. The combinators themselves can be the operations in question reified (AndThen[Poly, Poly], FlatMap[Poly, Poly] etc), like it is done for HLists.

Though if the underlying Scala Map is removed, the advantage of efficient implementation of that Map access operations will also be removed.

An implementation for Case resolution under that ADT can be an ordinary tree traversal till first match:

  implicit def case: Case[Function[A, B], A, B] = ???
  implicit def caseAlt: Case[Alternative[F, G], A, B] = implicitly[Case[F, A, B]] or implicitly[Case[G, A, B]]
  implicit def caseAndThen: Case[AndThen[F, G], A, B]] = implicitly[Case[F, A, T]] and implicitly[Case[G, T, B]] forSome T

What do you think?

[milessabin]

I'm very keen to see people explore alternatives ... give it a try and see where it leads :-)

[anatoliykmetyuk]

Here's a runnable sketch of alternative-based Poly implementation and Poly-based HMap implementation I came up with:

package shapelesshmap

// Tests
object Main extends App {
  // Poly tests
  val f = SimplePoly { x: Int     => x * x }
  val g = SimplePoly { x: String  => x * 2 }
  val m = SimplePoly { x: Double  => x / 2 }
  val k = SimplePoly { x: Boolean => !x    }
  val h = Or(Or(f, k), Or(g, m))

  println(h(2))      // 4
  println(h("Foo"))  // FooFoo
  println(h(2.2))    // 1.1
  println(h(true))   // false

  // HMap tests
  class Rel[K, V]
  trait Key { type Value }
  object Key {
    type Aux[V] = Key { type Value = V }
    implicit def rel[T, K <: Key.Aux[T]]: Rel[K, T] = new Rel[K, T]
  }

  object name extends Key { type Value = String }
  object id   extends Key { type Value = Int    }

  val map = new HMap[Rel, EmptyPoly.type](EmptyPoly)
  val newMap = map + (name, "John Smith") + (id, 10)

  println(newMap(name))  // John Smith
  println(newMap(id))    // 10
}


// Poly base
trait Poly

object Poly {
  implicit def polyOps[P <: Poly](p: P): PolyOps[P] = new PolyOps(p)
}

class PolyOps[P <: Poly](p: P) {
  def apply[A, B](a: A)(implicit e: Executor.Aux[P, A, B]): B = e(p, a)
}

// Executor for Poly
trait Executor[P <: Poly, A] {
  type Out
  def apply(p: P, a: A): Out
}

object Executor { type Aux[P <: Poly, A, Out0] = Executor[P, A] { type Out = Out0 } }


// Simple poly
case class SimplePoly[A, B](work: A => B) extends Poly

object SimplePoly {
  implicit def simpleExec[A, B]: Executor.Aux[SimplePoly[A, B], A, B] = new Executor[SimplePoly[A, B], A] {
    type Out = B
    def apply(p: SimplePoly[A, B], a: A): Out = p.work(a)
  }
}

// Or poly
case class Or[F <: Poly, G <: Poly](f: F, g: G) extends Poly

object Or {
  implicit def f[F <: Poly, G <: Poly, A, B](implicit e: Executor.Aux[F, A, B]): Executor.Aux[Or[F, G], A, B] = new Executor[Or[F, G], A] {
    type Out = B
    def apply(f: Or[F, G], a: A): B = e.apply(f.f, a)
  }

  implicit def g[F <: Poly, G <: Poly, A, B](implicit e: Executor.Aux[G, A, B]): Executor.Aux[Or[F, G], A, B] = new Executor[Or[F, G], A] {
    type Out = B
    def apply(f: Or[F, G], a: A): B = e.apply(f.g, a)
  }
}

// Empty poly
case object EmptyPoly extends Poly

// HMap
class HMap[R[_, _], U <: Poly](val underlying: U) extends Poly {
  def +[K <: AnyRef, V](k: K, v: V)(implicit e: R[K, V]): HMap[R, Or[SimplePoly[k.type, V], U]] =
    new HMap(Or(SimplePoly[k.type, V] { _: k.type => v}, underlying))
}

object HMap {
  implicit def e[R[_, _], U <: Poly, A, B](implicit ue: Executor.Aux[U, A, B]): Executor.Aux[HMap[R, U], A, B] = new Executor[HMap[R, U], A] {
    type Out = B
    def apply(m: HMap[R, U], a: A): B = ue(m.underlying, a)
  }
}

[milessabin]

Do you think you could extend it to polymorphic cases?

[anatoliykmetyuk]

What polymorphic cases do you mean?

[anatoliykmetyuk]

If you meant natural transformations, the following works:

// Natural transformations
trait ~>[F[_], G[_]] extends Poly {
  def f[T](x: F[T]): G[T]
}

object ~> {
  implicit def e[F[_], G[_], T]: Executor.Aux[~>[F, G], F[T], G[T]] = new Executor[~>[F, G], F[T]] {
    type Out = G[T]
    def apply(f: ~>[F, G], a: F[T]): G[T] = f.f(a)
  }
}

val natural = new ~>[List, Option] {
  def f[T](a: List[T]): Option[T] = a.headOption
}

println(natural(List(1)))
println(natural(List("Foo")))

[milessabin]

I meant something like your example built with Or where one of the branches is polymorphic.

[anatoliykmetyuk]

It already supports that out of the box, since the arguments to Or are Poly and ~> extends Poly:

  val natural = new ~>[List, Option] {
    def f[T](a: List[T]): Option[T] = a.headOption
  }
  val f = SimplePoly { x: Int => x * x }
  val polyOr = Or(f, natural)

  println(polyOr(2))    // 4
  println(polyOr(List(2)))  // Some(2)
  println(polyOr(List("Foo")))  // Some(Foo)