'diverging implicit expansion'-error on foldleft HList

Question

I am trying to do a type-calculation to build some nested structure of collections but I get a 'diverging implicit expansion for type shapeless.ops.hlist.LeftFolder'-error when I try to use a Map-like collection with a List[T] as key or value type. This nested structure works:

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

object poly extends Poly2 {
  implicit def wrapMap[T] = at[T, Int]((end, t) => Map(t -> end))
  //other collection wrap functions
}

def foldToNestedCollections[T <: HList, Out](hl: T)(implicit lf: LeftFolder.Aux[T, Any, poly.type, Out]): Out = lf.apply(hl, 1)

foldToNestedCollections(2 :: HNil) //compiles
foldToNestedCollections(2 :: 3 :: HNil) //compiles

this structure gives the error:

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

object poly extends Poly2 {
  implicit def wrapMap[T] = at[T, Int]((end, t) => Map(List(t) -> end)) //or Map(t, List(end)) gives the same error
  //other collection wrap functions
}

def foldToNestedCollections[T <: HList, Out](hl: T)(implicit lf: LeftFolder.Aux[T, Any, poly.type, Out]): Out = lf.apply(hl, 1)

foldToNestedCollections(2 :: HNil) //compiles
foldToNestedCollections(2 :: 3 :: HNil) //does not compile 'diverging ...

Update: If I build a custom converter it works. I build this using an the answer on an earlier question HList to nested Map. Any suggestions why?

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

sealed trait MyLeftFolder[L <: HList, T] {
  type Out

  def convert(hlist: L, value: T): Out
}

object MyLeftFolder {

  type Aux[L <: HList, T, Out2] = MyLeftFolder[L, T] { type Out = Out2 }

  private trait Impl[L <: HList, T, Out2] extends MyLeftFolder[L, T] {
    override type Out = Out2
  }

  implicit def hnil[T]: Aux[HNil, T, T] = new Impl[HNil, T, T] {
    override def convert(hlist: HNil, value: T): T = value
  }

  implicit def hnil2[T]: Aux[HNil.type, T, T] = new Impl[HNil.type, T, T] {
    override def convert(hlist: HNil.type, value: T): T = value
  }


  implicit def recurseint[L <: HList, T](implicit inner: MyLeftFolder[L, T]): Aux[Int :: L, T, Map[List[Int], inner.Out]] = new Impl[Int :: L, T, Map[List[Int], inner.Out]] {
    override def convert(hlist: Int :: L, value: T): Map[List[Int], inner.Out] = {
      val im = inner.convert(hlist.tail, value)
      Map(List(hlist.head) -> im)
    }
  }
}

def foldToNestedCollections[T <: HList](hl: T)(implicit lf: MyLeftFolder[T, Any]): lf.Out = lf.convert(hl, 1)

foldToNestedCollections(2 :: HNil) //compiles
foldToNestedCollections(2 :: 3 :: HNil) //compiles

Obviously Scala compiler heuristics reports about diverging implicit expansion for standard implementation but doesn't for yours. — Dmytro Mitin

Dmytro Mitin Dmytro Mitin · Accepted Answer · 2018-09-05T14:54:12

Use the following custom LeftFolder instead of standard shapeless.ops.hlist.LeftFolder. It differs in usage of Lazy.

import shapeless.{::, DepFn2, HList, HNil, Lazy, Poly2}
import shapeless.poly.Case2

trait LeftFolder[L <: HList, In, HF] extends DepFn2[L, In] with Serializable

object LeftFolder {
  def apply[L <: HList, In, F](implicit folder: LeftFolder[L, In, F]): Aux[L, In, F, folder.Out] = folder

  type Aux[L <: HList, In, HF, Out0] = LeftFolder[L, In, HF] { type Out = Out0 }

  implicit def hnilLeftFolder[In, HF]: Aux[HNil, In , HF, In] =
    new LeftFolder[HNil, In, HF] {
      type Out = In
      def apply(l : HNil, in : In): Out = in
    }

  implicit def hlistLeftFolder[H, T <: HList, In, HF, OutH, FtOut]
    (implicit f : Case2.Aux[HF, In, H, OutH], ft : Lazy[LeftFolder.Aux[T, OutH, HF, FtOut]]): Aux[H :: T, In, HF, FtOut] =
    new LeftFolder[H :: T, In, HF] {
      type Out = FtOut
      def apply(l : H :: T, in : In) : Out = ft.value(l.tail, f(in, l.head))
    }
}

'diverging implicit expansion'-error on foldleft HList

1 Answers