Generic traversal of case class hierarchy looking for all fields of String type

lawrence · August 17, 2017, 10:43am

Dear Colleagues,

With apologies in advance as a Scala newbie:

I have a hierarchy of (non-recursive) case classes and implicit vals that I am using with MoultingYAML to scan a simple yaml grammar.

I now want to visit the resulting instance tree (no particular order required) to find and possibly update all fields of String type. Ideally, I would like to do this in such a way that I don’t have to code specifically for each case class but instead generically for all case classes. In addition, I would rather not try to use reflection.

Any pointers in this regard would be very greatly appreciated. (I am reading through Shapeless and Cats documentation, but not yet making the necessary connections yet.)

Kind regards, Lawrence

siddhartha-gadgil · August 17, 2017, 11:18am

Indeed shapeless is a way to do this (though it is a title tricky), and I would strongly recommend the book from which I learnt this.

I assume by hierarchy you mean a sealed trait and case classes extending this (which is idiomatic scala)

regards,
Siddhartha

lawrence · August 17, 2017, 11:38am

Thank you Siddhartha.

Thank you for confirming that Shapeless is a likely fruitful direction to take. I clearly need to read through the Type Astronaut’s book again.

And yes, a sealed trait and case classes is what I mean by hierarchy.

Again, thank you.

Kind regards, Lawrence

Jasper-M · August 17, 2017, 12:32pm

Shapeless does indeed have a pretty steep learning curve, and it has a nice collection of very advanced features that might possibly make this a very easy task once you know and understand them all. But even with the most basic features (which are still pretty advanced…) it’s not that hard to implement this, once you have a very good understanding of how implicit search and Shapeless’ typeclasses work together. The Type Astronaut’s Guide should tell you all you need to know. I think the hardest part is probably learning to think in a more prolog-like way.

A basic implementation for finding all instances of a certain type in a hierarchy of simple case classes might look like this:

scala> :paste
// Entering paste mode (ctrl-D to finish)

import shapeless._

trait Collect[CC, T] {
  def apply(cc: CC): List[T]
}

object Collect extends LowerPriorityCollect {
  implicit def genericCollect[CC, L <: HList, T](
    implicit 
    gen: Generic.Aux[CC, L],
    coll: Collect[L, T]): Collect[CC, T] = 
      new Collect[CC, T] {
        def apply(cc: CC) = coll(gen.to(cc))
      }

  implicit def hnilCollect[T] = 
    new Collect[HNil, T] {
      def apply(l: HNil) = Nil
    }

  implicit def headMatchesCollect[L <: HList, T](
    implicit
    coll: Collect[L, T]): Collect[T :: L, T] = 
      new Collect[T :: L, T] {
        def apply(l: T :: L) = l.head :: coll(l.tail)
      }

  implicit def headIsCaseCollect[CC, L <: HList, T](
    implicit
    collHead: Collect[CC, T],
    collTail: Collect[L, T]): Collect[CC :: L, T] = 
      new Collect[CC :: L, T] {
        def apply(l: CC :: L) = collHead(l.head) ::: collTail(l.tail)
      }
}

trait LowerPriorityCollect {
  implicit def noMatchCollect[H, L <: HList, T](
    implicit
    coll: Collect[L, T]): Collect[H :: L, T] = 
      new Collect[H :: L, T] {
        def apply(l: H :: L) = coll(l.tail)
      }
}

// Exiting paste mode, now interpreting.

scala> case class Bar(a: Int, b: String, c: Double)
defined class Bar

scala> case class Foo(s: String, b: Bar, c: Int)
defined class Foo

scala> val coll = implicitly[Collect[Foo, String]]
coll: Collect[Foo,String] = Collect$$anon$1@10a5faf1

scala>  coll(Foo("a", Bar(1, "b", 3.0), 2))
res0: List[String] = List(a, b)

I will leave adding support for sealed traits as an exercise for the reader

lawrence · August 17, 2017, 1:40pm

That’s great Jasper. Thank you so much.

Kind regards, |Lawrence

lawrence · August 24, 2017, 11:34am

Hi Jasper,

I’ve been working with your suggested code and having quite some success. Again, thank you.

Just a couple of questions though:

The following test vector will fail:

case class Baz(a: String, b: String, c: String, d: Option[String])
case class Bar(a: Int, b: String, c: Double, d: String, e: Int, f: Baz, g: Boolean)
case class Foo(s: String, b: Bar, c: Int)
val coll = implicitly[Collect[Foo, String]]
val baz = Baz(“baz-1”, “baz-2”, “baz-3”, Some(“baz-4”))
val bar = Bar(1, “bar-1”, 3.0, “bar-2”, 23, baz, true)
val foo = Foo(“foo-1”, bar, 2)
println(coll(foo))

by only including foo-1 in the resulting list. I ‘fixed’ this by changing genericCollect to include a lazy/value pair like so:

implicit def genericCollect[CC, L <: HList, T](
  implicit
  gen: Generic.Aux[CC, L],
  coll: Lazy[Collect[L, T]]): Collect[CC, T] =
    new Collect[CC, T] {
      def apply(cc: CC) = coll.value(gen.to(cc))
    }

though I cannot say that I feel comfortable with my limited understanding of why this works. In any event, the output is now:

List(foo-1, bar-1, bar-2, baz-1, baz-2, baz-3)

which, of course, is better but lacks the baz-4 which is an Option[String].

Somewhat feeling in the dark I added:

implicit def headIsOptionCollect[CC, L <: HList, T](
  implicit
  collHead: Collect[CC, T],
  collTail: Collect[L, T]): Collect[CC :: L, T] =
    new Collect[CC :: L, T] {
      def apply(l: Option[CC] :: L) = {
        (l.head: Option[CC]) match {
          case Some(ll) => collHead(ll) ::: collTail(l.tail)
          case None => collTail(l.tail)
        }
      }
    }

and received the compilation error:

[error] /home/ubuntu/Workspac/dev/sbt-scala/test.scala:48: object creation impossible, since method apply in trait Collect of type (cc: CC :: L)List[T] is not defined
[error] new Collect[CC :: L, T] {
[error] ^
[error] one error found
[error] (compile:compileIncremental) Compilation failed
[error] Total time: 11 s, completed Aug 24, 2017 12:21:53 PM

and am now somewhat lost …

Any guidance you can give me on this would be very greatly appreciated.

Kind regards, Lawrence

Jasper-M · August 24, 2017, 12:35pm

Hi Lawrence,

For your first problem: you made the right assessment that you need to introduce Lazy there. As to why it is needed I don’t think I can say a lot more than the explanation that the Type Astronaut’s Guide gives. Actually I was a bit surprised that my smaller example worked without Lazy, otherwise I would have added it myself.

The cause of the compilation error that you’re getting is that you forgot to add Option[ ] in the return type of headIsOptionCollect and in new Collect[...]. However it wouldn’t solve your problem. For Option[String] to work you would have to add a special Option case of headMatchesCollect. If you want Option[SomeCaseClass] to work your headIsOptionCollect is the right way to go. So a complete solution for optional case class fields is adding these cases to the Collect companion object:

implicit def headOptionMatchesCollect[L <: HList, T](
  implicit
  collTail: Collect[L, T]): Collect[Option[T] :: L, T] =
    new Collect[Option[T] :: L, T] {
      def apply(l: Option[T] :: L) = l.head match {
        case Some(head) =>  head :: collTail(l.tail)
        case None => collTail(l.tail)
      }
    }
    
implicit def headOptionIsCaseCollect[CC, L <: HList, T](
  implicit
  collHead: Collect[CC, T],
  collTail: Collect[L, T]): Collect[Option[CC] :: L, T] = 
    new Collect[Option[CC] :: L, T] {
      def apply(l: Option[CC] :: L) = l.head match {
        case Some(head) => collHead(head) ::: collTail(l.tail)
        case None => collTail(l.tail)
      }
    }

Anyway, if you would add support for sealed traits (with the help of Shapeless Coproducts) these special cases for Option would become redundant, since Option[String] is also a coproduct Some[String] :+: None.type :+: CNil where Some[String] is a case class with a String field and None is a case object.

lawrence · August 24, 2017, 1:06pm

Hi Jasper,

Again, many many thanks. That gets me going again.

But, I shall also try and re-express the solution using Coproducts as you suggest. (I feel as if I tripped over the solution to the sealed traits challenge in your first post by indirect means Sorry for that.

Kind regards, Lawrence

Jasper-M · August 24, 2017, 1:13pm

Well, if you actually have no real need for adding full support for Coproducts then simply adding the special cases for Option will probably be a lot easier… I only added that part since you said in one of your first posts that you had sealed traits in your hierarchy.

Kind regards,
Jasper

kal · October 18, 2023, 2:25am

Hi Jasper

Trying to get my head around the shapeless library but struggling. I have a fairly similar use case whereby I need to traverse a hierarchy of case classes (which have arrays or seq or options as fields) and modify the string fields. The solution should return the same hierarchy with the modifications. Quicklens works for this but I’m looking for a generic solution that can handle different hierarchies.

Would you be able to provide or point me to such a solution? I’m using scala 2.13.

Regards
Kal