Fold over HList with unknown Types

Question

I have kind of a complex type hierarchy, but to break it down there are two base traits: Convertable and Conversion[A <: Convertable, B <: Convertable, e.g. there is a Conversion which can convert a Mealy-automaton to a Moore-automaton. Every Conversion[A,B] has a convert(automaton: A) : B method.

Now I want to introduce the concept of smart Conversions, which are basically a List of normal Conversions, which will be performed one after another. Therefore I have introduced an AutoConversion trait, extending a Conversion, which has a val path : HList parameter, to represent the chain of conversions, and should implement the convert method, so that AutoConversions just have to provide the list of actual Conversions to take. I think you could implement this with a fold over the path, so here is my first try:

package de.uni_luebeck.isp.conversions

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

trait AutoConversion[A <: Convertable, B <: Convertable] extends Conversion[A, B] {
  val path: HList

  object combiner extends Poly {
      implicit def doSmth[C <: Convertable, D <: Convertable] = 
         use((conv : Conversion[C, D] , automaton : C) => conv.convert(automaton))

}

  override def convert(startAutomaton: A): B = {
    path.foldLeft(startAutomaton)(combiner)
  }
}

This won't work, because no implicit Folder can be found, so I'm guessing I have to provide more Type information for the Compiler somewhere, but don't know where

Answer 1

You're right about needing more type information, and in general if you have a value with HList as a static type, it's likely you'll need to change your approach. There's essentially nothing you can do with an HList if all you know is that it's an HList (besides prepend values to it), and you'll usually only ever write HList as a type constraint.

In your case what you're describing is a kind of type-aligned sequence. Before you move forward with this approach, I'd suggest being really sure that you actually need to. One of the nice things about functions (and function-like types like your Conversion) is that they compose: you have an A => B and a B => C and you compose them into an A => C and can forget about B forever. You get a nice clean black box, which is generally exactly what you want.

In some cases, though, it can be useful to be able to compose function-like things in such a way that you can reflect on the pieces of the pipeline. I'm going to assume that this is one of those cases, but you should confirm that for yourself. If it's not, you're in luck, because what's coming is kind of messy.

I'll assume these types:

trait Convertable

trait Conversion[A <: Convertable, B <: Convertable] {
  def convert(a: A): B
}

We can define a type class that witnesses that a specific HList is composed of one or more conversions whose types line up:

import shapeless._

trait TypeAligned[L <: HList] extends DepFn1[L] {
  type I <: Convertable
  type O <: Convertable
  type Out = Conversion[I, O]
}

L contains all of the type information about the pipeline, and I and O are the types of its endpoints.

Next we need instances for this type class (note that this must be defined together with the trait above for the two to be companioned):

object TypeAligned {
  type Aux[L <: HList, A <: Convertable, B <: Convertable] = TypeAligned[L] {
    type I = A
    type O = B
  }

  implicit def firstTypeAligned[
    A <: Convertable,
    B <: Convertable
  ]: TypeAligned.Aux[Conversion[A, B] :: HNil, A, B] =
    new TypeAligned[Conversion[A, B] :: HNil] {
      type I = A
      type O = B
      def apply(l: Conversion[A, B] :: HNil): Conversion[A, B] = l.head
    }

  implicit def composedTypeAligned[
    A <: Convertable,
    B <: Convertable,
    C <: Convertable,
    T <: HList
  ](implicit
    tta: TypeAligned.Aux[T, B, C]
  ): TypeAligned.Aux[Conversion[A, B] :: T, A, C] =
    new TypeAligned[Conversion[A, B] :: T] {
      type I = A
      type O = C
      def apply(l: Conversion[A, B] :: T): Conversion[A, C] =
        new Conversion[A, C] {
          def convert(a: A): C = tta(l.tail).convert(l.head.convert(a))
        }
    }
}

And now you can write a version of your AutoConversion that keeps track of all of the type information about the pipeline:

class AutoConversion[L <: HList, A <: Convertable, B <: Convertable](
  path: L
)(implicit ta: TypeAligned.Aux[L, A, B]) extends Conversion[A, B] {
  def convert(a: A): B = ta(path).convert(a)
}

And you can use it like this:

case class AutoA(i: Int) extends Convertable
case class AutoB(s: String) extends Convertable
case class AutoC(c: Char) extends Convertable

val ab: Conversion[AutoA, AutoB] = new Conversion[AutoA, AutoB] {
  def convert(a: AutoA): AutoB = AutoB(a.i.toString)
}

val bc: Conversion[AutoB, AutoC] = new Conversion[AutoB, AutoC] {
  def convert(b: AutoB): AutoC = AutoC(b.s.lift(3).getOrElse('-'))
}

val conv = new AutoConversion(ab :: bc :: HNil)

And conv will have the expected static type (and implement Conversion[AutoA, AutoC]).