How does HList.foldRight look for implicits when used in the implementation of a type class?

Question

I am newbie at using Shapeless, and I am experimenting with Shapeless for automatic type class generation and folding over HLists. My goal is to render a HList as (a, b, c, d) using a typeclass implementation of scalaz.Show

My first step was to experiment in the REPL with the following code

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

object prettyPrint extends Poly2 {
  implicit def defaultCase[A] = at((a:A, z:String)=>s", ${a.toString}$z")
}

def print[H, T<:HList](f: H :: T)(implicit folder:RightFolder.Aux[H :: T, String, prettyPrint.type, String]) = {
  f.foldRight("")(prettyPrint)
}

val f = 1::'a::2::'b::HNil
val res = s"(${f.head}${print(f.tail)})" // Results res: String = (1, 'a, 2, 'b)

After this I implemented the following method in my implementation of LabelledTypeClassCompanion[...]. Unfortunately, this code does not compile because the compiler is complaining about missing implicits, even though I can't tell what the difference is between the code in the REPL and the code below. My Question is what is the problem in the code below and how can I fix it?

def showFold[H, T<:HList](f: H::T)(implicit folder:RightFolder.Aux[ H::T, String, prettyPrint.type, String]) = {
  f.foldRight("")(prettyPrint)
}

override def product[H, T <: HList](name: String, ch: ScalazShow[H], ct: ScalazShow[T]): ScalazShow[H :: T] = {
  new ScalazShow[H :: T] {
    override def shows(ft: (H :: T)): String = {
     showFold(ft) // This does not compile
    }

  }
}

Error:(49, 18) could not find implicit value for parameter folder: shapeless.ops.hlist.RightFolder.Aux[shapeless.::[H,T],String,com.fpinscala.ninetynine.prettyPrint.type,String] showFold(ft) // This does not compile

Below is the complete implementation

package com.fpinscala.ninetynine

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

import scalaz.{Show => ScalazShow}

object prettyPrint extends Poly2 {
  implicit def defaultCase[A]:this.Case.Aux[A, String, String] = at[A, String]{
    (a,z) => s", $a$z"
  }
}


object ShowImpl extends LabelledTypeClassCompanion[ScalazShow] {

  implicit def symbolShow : ScalazShow[Symbol] = new ScalazShow[Symbol] {
    override def shows(f: Symbol): String = f.toString()
  }

  implicit def intShow : ScalazShow[Int] = new ScalazShow[Int] {
    override def shows(f: Int): String = f.toString
  }

  override val typeClass: LabelledTypeClass[ScalazShow] = new LabelledTypeClass[ScalazShow] {

    override def coproduct[L, R <: Coproduct](name: String, cl: => ScalazShow[L], cr: => ScalazShow[R]): ScalazShow[L :+: R] = new ScalazShow[L :+: R] {
      override def shows(lr: (L :+: R)): String = lr match {
        case Inl(l) => cl.shows(l)
        case Inr(r) => cr.shows(r)
      }
    }

    override def emptyCoproduct: ScalazShow[CNil] = new ScalazShow[CNil] {
      override def shows(f: CNil): String = ""
    }


    def showFold[H, T<:HList](f: H::T)(implicit folder:RightFolder.Aux[ H::T, String, prettyPrint.type, String]) = {
      f.foldRight("")(prettyPrint)
    }

    override def product[H, T <: HList](name: String, ch: ScalazShow[H], ct: ScalazShow[T]): ScalazShow[H :: T] = {
      new ScalazShow[H :: T] {
        override def shows(ft: (H :: T)): String = {
         showFold(ft) // This does not compile 
        }

      }
    }

    override def project[F, G](instance: => ScalazShow[G], to: (F) => G, from: (G) => F): ScalazShow[F] = new ScalazShow[F] {
      override def shows(f: F): String = instance.shows(to(f))
    }

    override def emptyProduct: ScalazShow[HNil] = new ScalazShow[HNil] {
      override def shows(f: HNil): String = ""
    }

  }
}

Incubation

Answer 1

You can think of a type class constraint as a way to carry some information about a type from a concrete context to a generic context (moving backward through the call stack). In this case you actually really do need that RightFolder instance if you want to write your implementation this way, but the method signatures in LabelledTypeClass don't allow you to carry that information through, so you're out of luck (the basic idea is possible, though—you just need a slightly different approach).

Update

I just realized I misread your question slightly—because you were using the TypeClass type class I assumed you wanted instances for case classes and sealed trait hierarchies as well as hlists and coproducts. My answer gives you all of these (just like TypeClass would), so you can write this:

scala> (123 :: "abc" :: HNil).shows
res2: String = (123, abc)

As well as the case class and sealed trait examples I give below. If you don't want case classes and sealed traits you can just remove the genericShow definition.

Why the difference between concrete and generic contexts

Here's a simpler case to start with. Suppose we want to use Show to print a value twice. We can do something like this:

scala> import scalaz._, Scalaz._
import scalaz._
import Scalaz._

scala> val x: Int = 123
x: Int = 123

scala> s"${ x.shows }${ x.shows }"
res0: String = 123123

Here x has a concrete type, and when we call .shows on it, the compiler will try to find an instance of Show for that concrete type. Scalaz provides a Show[Int], so everything works just fine and we get the result we want.

Next we can try writing a generic version:

def toStringTwice[X](x: X): String = s"${ x.shows }${ x.shows }"

But the compiler will complain:

<console>:18: error: value shows is not a member of type parameter X
       def toStringTwice[X](x: X): String = s"${ x.shows }${ x.shows }"
                                                               ^

This is because the compiler can't prove that X has a Show instance, since it doesn't know anything at all about X. You could just write a bunch of overloaded concrete methods:

scala> def toStringTwice(x: String): String = s"${ x.shows }${ x.shows }"
toStringTwice: (x: String)String

scala> def toStringTwice(x: Int): String = s"${ x.shows }${ x.shows }"
toStringTwice: (x: Int)String

...

But this is exactly the kind of annoying boilerplate that type classes are designed to save you from. Instead of enumerating all the types you have Show instances for, you can abstract over them by providing the compiler with exactly as much information as it needs:

scala> def toStringTwice[X: Show](x: X): String = s"${ x.shows }${ x.shows }"
toStringTwice: [X](x: X)(implicit evidence$1: scalaz.Show[X])String

Now you can call it with an Int, or anything else that has a Show instance:

scala> toStringTwice(123)
res2: String = 123123

What you can't do is call it with another unconstrained generic type:

def toStringFourTimes[X](x: X): String = s"${ toStringTwice(x) * 2 }"

Instead you have to add the constraint again:

scala> def toStringFourTimes[X: Show](x: X): String = s"${ toStringTwice(x) * 2 }"
toStringFourTimes: [X](x: X)(implicit evidence$1: scalaz.Show[X])String

And so on—you have to carry along the Show constraint all the way until you've got a concrete type. You can only use toStringTwice in two ways: on a concrete type that has a Show instance, or on a generic type that has a Show constraint.

Note that none of the above is Shapeless-specific—this is simply the way type classes work.

One possible fix

Unfortunately this doesn't seem to me like a very good use case for LabelledTypeClass, since the desired instance doesn't really fit the way of building up instances that the TypeClass type classes support. You could probably do it but I don't really want to try.

There's also an issue in the way your prettyPrint works—it's not actually using the Show instance for A (there's not even one to use), but is instead calling the horrible universal toString.

Here's a quick first draft of how I'd probably write this:

import scalaz.Show, scalaz.Scalaz._
import shapeless._
import shapeless.ops.coproduct.Folder
import shapeless.ops.hlist.RightReducer

object prettyPrint2 extends Poly2 {
  implicit def defaultCase[A: Show]: Case.Aux[A, String, String] =
    at[A, String]((a, z) => s"$a, $z")
}

object prettyPrint extends Poly1 {
  implicit def defaultCase[A: Show]: Case.Aux[A, String] = at[A](_.shows)
}

implicit def hlistShow[L <: HList](implicit
  reducer: RightReducer.Aux[L, prettyPrint2.type, String]
): Show[L] = Show.shows(l => "(" + l.reduceRight(prettyPrint2) + ")")

implicit def coproductShow[C <: Coproduct](implicit
  folder: Folder.Aux[prettyPrint.type, C, String]
): Show[C] = Show.shows(_.fold(prettyPrint))

implicit def genericShow[A, R](implicit
  gen: Generic.Aux[A, R],
  reprShow: Show[R]
): Show[A] = reprShow.contramap(gen.to)

And then:

scala> Foo(123, "abc").shows
res0: String = (123, abc)

scala> (Foo(123, "abc"): Base).shows
res1: String = (123, abc)

You may run into corner cases involving nested case classes, etc. that don't work because of compiler bugs (see my slides here about generic derivation in Scala for some details), but this approach should more or less do what you want.

Sayed

I had a suspicion that my approach was wrong. Your answer confirmed it! I did run into errors where the compiler started complaining about divergent implicit expansion when using nested classes like you said it would . I'll go over your slides to try and resolve that. – Incubation

@HaroonKhan It might be as simple as putting a Lazy around the Generic instance in genericShow. – Sayed