Parameterized folding on a shapeless HList

Question

I am trying to implement a method that does parameterized folding on a HList provided by the caller. The HList can have any number of elements (> 0) of the same type.

val list = "a" :: "b" :: "c" :: HNil

def process[L <: HList](mul: Int, l: L) = {
  object combine extends Poly2 {
    implicit def work = at[String, (Int, L)] {
      case (a, (b, acc)) => (b, (a * b) :: acc)
    }
  }
  l.foldRight((mul, HNil))(combine)._2
}

process(3, list)    //  expecting to get aaa :: bbb :: ccc :: HNil

What I get is error about missing implicit: "could not find implicit value for parameter folder: shapeless.ops.hlist.RightFolder[L,(Int, shapeless.HNil.type),combine.type]". From this answer it is clear that compiler wants to see evidence that it can fold the HList.

However I cannot pass a RightFolder as an implicit parameter because Poly2 type is not known outside the method. And even if it were possible, the implicit parameter would only propagate further up the call stack. In fact I don't want the caller to even know whether the method performs folding, mapping, reduction or anything else. All it needs to provide is evidence that the HList is the right kind of HList. I assume the problem is in [L <: HList] which is not specific enough but I am not sure how to make it right.

The following code works as expected but it obviously does not encapsulate folding logic in a method:

val list = "a" :: "b" :: "c" :: HNil

object combineS extends Poly2 {
  implicit def work[L <: HList] = at[String, (Int, L)] {
    case (a, (b, acc)) => (b, (a * b) :: acc)
  }
}

list.foldRight((3, HNil))(combineS)._2

Puttier

Answer 1

The easiest is to extract combine (adding type parameter L) and add necessary implicit parameter to process.

object combine extends Poly2 {
  implicit def work[L <: HList] = at[String, (Int, L)] {
    case (a, (b, acc)) => (b, (a * b) :: acc)
  }
}

def process[L <: HList](mul: Int, l: L)(implicit rightFolder: RightFolder.Aux[L, (Int, HNil.type), combine.type, _ <: (_,_)]) = {
  l.foldRight((mul, HNil))(combine)._2
}

---

And even if it were possible, the implicit parameter would only propagate further up the call stack. In fact I don't want the caller to even know whether the method performs folding, mapping, reduction or anything else.

With type-level programming you encapsulate your logic in a type class rather than method. So you can introduce a type class

trait Process[L <: HList] {
  type Out <: HList
  def apply(mul: Int, l: L): Out
}
object Process {
  type Aux[L <: HList, Out0 <: HList] = Process[L] { type Out = Out0 }

  object combine extends Poly2 {
    implicit def work[L <: HList] = at[String, (Int, L)] {
      case (a, (b, acc)) => (b, (a * b) :: acc)
    }
  }

  implicit def mkProcess[L <: HList, Res, A, L1 <: HList](implicit
    rightFolder: RightFolder.Aux[L, (Int, HNil.type), combine.type, Res],
    ev: Res <:< (A, L1)
  ): Aux[L, L1] = new Process[L] {
    override type Out = L1
    override def apply(mul: Int, l: L): Out = l.foldRight((mul, HNil))(combine)._2
  }
}

def process[L <: HList](mul: Int, l: L)(implicit p: Process[L]): p.Out = p(mul, l)

Geophilous

Dmytro, apparently all my questions are solved by the same or similar pattern. Also apparently there is some conventions for type alias naming such as Out, Aux etc. Can you recommend any articles to read up on it? – Puttier

Thank you. I read it before but apparently it mostly went over my head. Will have to re-read again. – Puttier