Extractor for a shapeless HList that mimics parser concatenation `~`

Question

Question

Is it somehow possible to create an extractor for shapeless' HList that looks like the following.

val a ~ _ ~ b = 4 :: "so" :: 4.5 :: HNil
=> a == 4 && b == 4.5

1. Replace :: by ~, which shouldn't be the problem.
2. Get rid of the terminating HNil. Are there any problems that might arise?

Motivation

After much sweat and tears I managed to arrive at the point, where the following code works:

for(
  x1 :: _ :: x2 :: HNil <- (expInt ~ "+" ~ expInt).llE
) yield (x1 + x2)

expInt parses an Int in some monad E. The type of (expInt ~ "+" ~ expInt).llE is E[Int :: String :: Int :: HNil].

I want the pattern on the left of the <- to somehow resemble the construction of the combinator parser on the right.

Answer 1

This can be done, and has a couple of interesting twists.

The first is that, typically, for matching a structure that's built with a right associative constructor (ie. ::) you would use a correspondingly right associative extractor, otherwise you would decompose and bind the extracted elements in reverse order. Unfortunately right associative extractors must, like right associative operators, end with a : in Scala and that would clobber your parser combinator syntax since the extractor name would have to be ~: instead of plain ~. However, I'll postpone this for the moment and work with right associativity.

The second twist is that we need the unapply method to yield results of different types depending on whether we're matching an HList of more than two elements or of exactly two elements (and we shouldn't be able to match a list of less that two elements at all).

If we're matching a list of more than two elements we need to decompose the list into a pair consisting of the head and the HList tail, ie. given l: H :: T where T <: HList we must yield a value of type (H, T). If, on the other hand, we're matching a list of exactly two elements, ie. of the form E1 :: E2 :: HNil, we need to decompose the list into a pair consisting of just those two elements, ie (E1, E2) rather than a head and a tail which would be (E1, E2 :: HNil).

This can be done using exactly the same type level programming techniques that are used throughout shapeless. First we define a type class which is going to do the work of the extractor, with instances corresponding to each of the two cases described above,

import shapeless._

trait UnapplyRight[L <: HList] extends DepFn1[L]

trait LPUnapplyRight {
  type Aux[L <: HList, Out0] = UnapplyRight[L] { type Out = Out0 }
  implicit def unapplyHCons[H, T <: HList]: Aux[H :: T, Option[(H, T)]] =
    new UnapplyRight[H :: T] {
      type Out = Option[(H, T)]
      def apply(l: H :: T): Out = Option((l.head, l.tail))
    }
}

object UnapplyRight extends LPUnapplyRight {
  implicit def unapplyPair[H1, H2]: Aux[H1 :: H2 :: HNil, Option[(H1, H2)]] =
    new UnapplyRight[H1 :: H2 :: HNil] {
      type Out = Option[(H1, H2)]
      def apply(l: H1 :: H2 :: HNil): Out = Option((l.head, l.tail.head))
    }
}

Then we define our extractor in terms of it like so,

object ~: {
  def unapply[L <: HList, Out](l: L)
    (implicit ua: UnapplyRight.Aux[L, Out]): Out = ua(l)
}

And then we're good to go,

val l = 23 :: "foo" :: true :: HNil

val a ~: b ~: c = l
a : Int
b : String
c : Boolean

So far, so good. Now let's return to the associativity issue. If we want to achieve the same effect with a left associative extractor (ie. ~ instead of ~:) we'll need to change the way the decomposition is done. First let's desugar the right associative extractor syntax we just used. The expression,

val a ~: b ~: c = l

is equivalent to,

val ~:(a, ~:(b, c)) = l

By contrast, the left associative version,

val a ~ b ~ c = l

is equivalent to,

val ~(~(a, b), c) = l

To make this work as an extractor for HLists our unapply type class must peel elements off from the end, rather from beginning of the list. We can do this with the aid of shapeless's Init and Last type classes,

trait UnapplyLeft[L <: HList] extends DepFn1[L]

trait LPUnapplyLeft {
  import ops.hlist.{ Init, Last }
  type Aux[L <: HList, Out0] = UnapplyLeft[L] { type Out = Out0 }
  implicit def unapplyHCons[L <: HList, I <: HList, F]
    (implicit
      init: Init.Aux[L, I],
      last: Last.Aux[L, F]): Aux[L, Option[(I, F)]] =
    new UnapplyLeft[L] {
      type Out = Option[(I, F)]
      def apply(l: L): Out = Option((l.init, l.last))
    }
}

object UnapplyLeft extends LPUnapplyLeft {
  implicit def unapplyPair[H1, H2]: Aux[H1 :: H2 :: HNil, Option[(H1, H2)]] =
    new UnapplyLeft[H1 :: H2 :: HNil] {
      type Out = Option[(H1, H2)]
      def apply(l: H1 :: H2 :: HNil): Out = Option((l.head, l.tail.head))
    }
}

object ~ {
  def unapply[L <: HList, Out](l: L)
    (implicit ua: UnapplyLeft.Aux[L, Out]): Out = ua(l)
}

And now we're done,

val a ~ b ~ c = l
a : Int
b : String
c : Boolean