HList foldLeft with tuple as zero

Question

I'm trying to foldLeft on a HList with an accumulator of type (HL, Int), where HL is a HList. The program below does not compile. However, if I switch to a simpler accumulator of type HL (by just switching the commented lines with the ones above), it compiles and it works.

Wrapping an HList in a tuple breaks the implicit resolution for the leftFolder. What am I missing?

package foo.bar

import shapeless.{:+:, ::, CNil, Coproduct, Generic, HList, HNil, Lazy, Poly2}
import shapeless.ops.hlist.{LeftFolder, Reverse}

object StackOverflow extends App {

  trait MyTypeclass[T] {
    def doSomething(t: T): (T, Int)
  }

  implicit lazy val stringInstance: MyTypeclass[String] = (t: String) => (t, 0)
  implicit val hnilInstance: MyTypeclass[HNil] = (t: HNil) => (t, 0)
  implicit def hlistInstance[H, T <: HList](
    implicit
    head: Lazy[MyTypeclass[H]],
    tail: MyTypeclass[T]
  ): MyTypeclass[H :: T] =
    (ht: H :: T) =>
      ht match {
        case h :: t =>
          val (hres, hint) = head.value.doSomething(h)
          val (tres, tint) = tail.doSomething(t)
          (hres :: tres, hint + tint)
    }
  implicit val cnilInstance: MyTypeclass[CNil] = (t: CNil) => ???
  implicit def coproductInstance[L, R <: Coproduct](
    implicit
    head: Lazy[MyTypeclass[L]],
    tail: MyTypeclass[R]
  ): MyTypeclass[L :+: R] = (lr: L :+: R) => ???

  object leftFolder extends Poly2 {
    implicit def caseAtSimple[F, HL <: HList]: Case.Aux[HL, F, F :: HL] =
      at {
        case (acc, f) => f :: acc
      }
    implicit def caseAtComplex[F, HL <: HList]: Case.Aux[(HL, Int), F, (F :: HL, Int)] =
      at {
        case ((acc, i), f) => (f :: acc, i)
      }
  }

  implicit def genericInstance[T, HL <: HList, LL <: HList](
    implicit
    gen: Generic.Aux[T, HL],
    myTypeclass: Lazy[MyTypeclass[HL]],
//    folder: LeftFolder.Aux[HL, HNil, leftFolder.type, LL],
    folder: LeftFolder.Aux[HL, (HNil, Int), leftFolder.type, (LL, Int)],
    reverse: Reverse.Aux[LL, HL]
  ): MyTypeclass[T] = (t: T) => {
    val generic = gen.to(t)
    val (transformed, idx) = myTypeclass.value.doSomething(generic)
//    val ll = transformed.foldLeft(HNil: HNil)(leftFolder)
    val (ll, _) = transformed.foldLeft((HNil: HNil, 0))(leftFolder)
    val reversed = reverse(ll)
    (gen.from(reversed), idx)
  }

  def doSomething[T](t: T)(implicit myTypeclass: MyTypeclass[T]): T = myTypeclass.doSomething(t)._1

  case class Foo(
    str1: String,
    str2: String
  )

  val original = Foo("Hello World!", "Hello there!")
  val result = doSomething(original)
  println(result == original)
}

Dmytro Mitin · Accepted Answer · 2020-11-06T23:33:37.290

2

You want implicits to do too much work in a single step.

Try to add one more type parameter Out

implicit def genericInstance[T, HL <: HList, Out, LL <: HList](
  implicit
  gen: Generic.Aux[T, HL],
  myTypeclass: Lazy[MyTypeclass[HL]],
  //folder: LeftFolder.Aux[HL, (HNil, Int), leftFolder.type, (LL, Int)],
  folder: LeftFolder.Aux[HL, (HNil, Int), leftFolder.type, Out],
  ev: Out <:< (LL, Int), // added
  reverse: Reverse.Aux[LL, HL]
): MyTypeclass[T] = (t: T) => {
  val generic = gen.to(t)
  val (transformed, idx) = myTypeclass.value.doSomething(generic)
  //val (ll, _) = transformed.foldLeft((HNil: HNil, 0))(leftFolder)
  val (ll, _) = ev(transformed.foldLeft((HNil: HNil, 0))(leftFolder))
  val reversed = reverse(ll)
  (gen.from(reversed), idx)
}

Read about over-constrained implicits:

https://books.underscore.io/shapeless-guide/shapeless-guide.html#sec:type-level-programming:chaining (4.3 Chaining dependent functions)

Scala shapeless Generic.Aux implicit parameter not found in unapply

Extract FieldType key and value from HList

How to implicitly figure out the type at the head of a shapeless HList

How to infer inner type of Shapeless record value with unary type constructor?

edited Nov 06 '20 at 23:33

answered Nov 04 '20 at 23:20

Dmytro Mitin

48,194
3
28
66

Still not compiling. I activated -Xlog-implicits, and I get the error: "hasMatchingSymbol reported error: Cannot prove that Out =:= (LL, Int)" – pgrandjean Nov 05 '20 at 01:36
@pgrandjean Well, it seems to work with `=:=` https://scastie.scala-lang.org/erH3enRuREu0kN3RkxCOzA But if it works for you with `<:<`, so much the better. – Dmytro Mitin Nov 05 '20 at 01:47
@pgrandjean What are your Scala and Shapeless versions? At Scastie I used Scala 2.13.3 and Shapeless 2.4.0-M1. – Dmytro Mitin Nov 05 '20 at 01:51
Using Scala 2.12.12 and Shapeless 2.3.3 – pgrandjean Nov 05 '20 at 01:55
@pgrandjean Yeah, in 2.12.12+2.3.3 I can reproduce your error https://scastie.scala-lang.org/8MdBlFHkQ42mSUPVzvYdJg and confirm that `<:<` works https://scastie.scala-lang.org/vTFDEsGUQ7iDWtuSWN9qzg So this depends on versions used. – Dmytro Mitin Nov 05 '20 at 02:01
@pgrandjean Thanks for your edit proposal but I rejected it because `<:<` is not a method. – Dmytro Mitin Nov 05 '20 at 02:03
ok, no problem. I was just trying to use the same word used as in TTAGTS. – pgrandjean Nov 05 '20 at 02:06
@pgrandjean If you're talking about *"Here’s a revised version of the method using `=:=` to constrain `Repr`..."* then "method" refers here to `def getWrappedValue`. – Dmytro Mitin Nov 05 '20 at 02:14
@pgrandjean Since `=:=` or `<:<` defines an implicit conversion you can replace the line `val (ll, _) = ev(transformed.foldLeft((HNil: HNil, 0))(leftFolder))` with just `val (ll: LL, _) = transformed.foldLeft((HNil: HNil, 0))(leftFolder)`. – Dmytro Mitin Nov 05 '20 at 10:59

HList foldLeft with tuple as zero

1 Answers1

Linked