Type-Level Programming in Scala, Part 6e: HList Apply

We’ll continue by defining happly, a heterogeneous apply method. It takes an HList of functions and applies them to the corresponding values in an input HList, producing an HList of results.

First, the example usage looks like:

      // data HLists of type  Double :: Char :: HNil
   val y1 = 9.75 :: 'x' :: HNil
   val y2 = -2.125 :: 'X' :: HNil
   
      // The functions to apply.  z has type:
      //
      //   (Double => Double) :: (Char => Boolean) :: HNil
      //
   val z = ((_: Double) + .5) :: ( (_: Char).isUpper) :: HNil
   
      // apply to first input HList y1
   val z1 = happly(z)(y1)
   
      // check types
   val z1Types : Double :: Boolean :: HNil = z1

      // check values
   val 10.25 :: false :: HNil = z1

      // apply to second input HList y2
   val z2 = happly(z)(y2)
   
      // check types
   val z2Types : Double :: Boolean :: HNil = z2

      // check values
   val -1.625 :: true :: HNil = z2

We’ll implement happly using a type class HApply, which is essentially Function1. We can’t actually use Function1 because existing implicits related to Function1 get in the way.

sealed trait HApply[-In, +Out] {
  def apply(in: In): Out
}

The idea is that given an HList of functions, we produce an HApply that accepts an HList of parameters of the right type and produces an HList of results. For the function `z` from the example, we want an HApply of type:

HApply[ (Double :: Char :: HNil), (Double :: Boolean :: HNil)]

There are two basic cases for this: HNil and HCons. The easy case is mapping an HNil to an HNil, handled by happlyNil.

   implicit def happlyNil(h: HNil) : HApply[HNil, HNil] =
      new HApply[HNil, HNil] {
         def apply(in: HNil) = HNil
      }

As usual, HCons is the interesting case. We accept an HCons cell with a head that is a function and produce an HApply that will accept an input HCons cell of the right type. The HApply then applies the head function to the head value and recurses on the tail. The HApply to use for recursion is provided as an implicit and this is how we require that one HList is an HList entirely of functions and the other HList contains values of the right type to be provided as inputs to those functions.

   implicit def happlyCons[InH, OutH, TF <: HList, TIn <: HList, TOut <: HList]
      (implicit applyTail: TF => HApply[TIn, TOut]) =
         (h: HApply[InH :: TIn, OutH :: TOut]) =>

      new HApply[InH :: TIn, OutH :: TOut] {
         def apply(in: InH :: TIn) =
            HCons( h.head(in.head), applyTail(h.tail)(in.tail) )
      }

In the example, we have:

   val y1 = 9.75 :: 'x' :: HNil

   val z: (Double => Double) :: (Char => Boolean) :: HNil =
       ((_: Double) + .5) :: ( (_: Char).isUpper) :: HNil

So, for happly(z)(y1), our implicit is constructed with:

   happlyCons[ Double, Double, Char => Boolean :: HNil, Char :: HNil, Boolean :: HNil]( 
      happlyCons[ Char, Boolean, HNil, HNil, HNil](
         happlyNil
      )
   )

The first applyCons constructs an HApply that uses the head of z, a function of type `Double => Double`, to map an HList with a head of type Double to an HList with a head of type Double. It uses the HApply from the second happlyCons for mapping the tail of the input HList.

This second HApply uses the second element of z, a function of type `Char => Boolean`, to map an HList with a head of type Char to an HList with a head of type Boolean. Because this is the last element, the recursion ends with happlyNil mapping HNil to HNil.

Finally, we define an entry point. Given an HList of functions and an HList of arguments to those functions, we use happly to grab an HApply implicitly and produce the resulting HList with it:

   def happly[H <: HList, In <: HList, Out <: HList]
      (h: H)(in: In)(implicit toApply: H => HApply[In, Out]): Out =
         toApply(h)(in)
About these ads

9 thoughts on “Type-Level Programming in Scala, Part 6e: HList Apply

  1. I keep ready happly as happily. Which nicely describes the manner in which I am absorbing this series.

    Which existing implicits get in the way of using Function1 rather than HApply?

    • It is an interesting approach and you should write it up. I’d be interested to know how it should be used properly. For example, I tried your test case, but I want the following to be a compile error and not a runtime error:

      scala> val y1 = Box(9.75) :: Box('x') :: Nil
      y1: com.github.okomok.mada.dual.list.Cons[com.github.okomok.mada.dual.Box[Double],com.github.okomok.mada.dual.list.Cons[com.github.okomok.mada.dual.Box[Char],com.github.okomok.mada.dual.list.Nil]] = dual.List(9.75, x)

      scala> val z = Lift1((_: Double) + .5) :: Box(3) :: Nil
      z: com.github.okomok.mada.dual.list.Cons[com.github.okomok.mada.dual.Lift1[Double,Double],com.github.okomok.mada.dual.list.Cons[com.github.okomok.mada.dual.Box[Int],com.github.okomok.mada.dual.list.Nil]] = dual.List(, 3)

      scala> z.zipBy(y1, Apply).force
      java.lang.UnsupportedOperationException: dual.Any.asFunction1
      at com.github.okomok.mada.dual.Any$class.unsupported(Any.scala:109)
      at com.github.okomok.mada.dual.Box.unsupported(Box.scala:14)
      at com.github.okomok.mada.dual.Any$class.asFunction1(Any.scala:29)
      at com.github.okomok.mada.dual.Box.asFunction1(Box.scala:14)
      ...

      The equivalent using HApply is:

      scala> val y1 = 9.75 :: 'x' :: HNil
      y1: HCons[Double,HCons[Char,HNil]] = 9.75 :: x :: HNil

      scala> val z = ((_: Double) + .5) :: 3 :: HNil
      z: HCons[(Double) => Double,HCons[Int,HNil]] = :: 3 :: HNil

      scala> happly(z)(y1)
      error: could not find implicit value for parameter toApply: (HCons[(Double) => Double,HCons[Int,HNil]]) => (HCons[Double,HCons[Char,HNil]]) => Out
      happly(z)(y1)
      ^

      Certainly we’d like the error message to be more helpful in each case.

      • Yes, `f#asFunction1` unfortunately compiles.
        This is the millennium problem for me.
        A workaround will be an `implicit` after all :(
        I wish I had the type-level `throw`…

        Regards,

      • (WP won’t let me reply to your replies, so here they are…)

        @Okomok
        Perhaps write about your system and why it should work or what the obstacles are to making it work. You might get useful feedback from readers.

        @Retronym
        That annotation has to go on the type being searched for, though. So, you’d get the message for Function1 or you’d have to have custom versions of Function1 just to define your own message:
        http://lampsvn.epfl.ch/trac/scala/ticket/2462

        Even then, I think it would be hard to get an error message like:

        type mismatch in the second element of z.
        Expected: Char => ?
        Got: Int

      • > Perhaps write about your system…

        Sadly it might be too difficult for my poor English.
        (First I should write an article by my native language.)
        BTW, the origin of my system is `trait Fold[-Elem, Value]` of your `up` library.
        It inspired me Scala type-system probably has the same power as C++.
        In fact, `mada.dual` is intended to port Boost.Fusion, which too consists of
        pairs of type-level method and generic method.

        Regards,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s