CODEWITHSUNDEEP
scalascala-collections
Michael Zajac
Michael Zajac

Reputation: 55569

How can I handle "flattening" a recursively defined type structure?

Consider these case classes where Blog contains Posts and a Post contains Comments, and then a Relation to relate a single parent to a single child:

case class Comment(id: Int)
case class Post(id: Int, comments: List[Comment])
case class Blog(id: Int, posts: List[Post])

case class Relation[A, B](parent: A, child: B)

What I'm looking to do is recursively collapse a list of these Relations into the top level parent, starting with something like this (the reason for this un-nested structure in the first place is that this is how an SQL result with joined columns would look when parsed): 

val relations = List(
    Relation(Post(1, Nil), Comment(1)),
    Relation(Post(1, Nil), Comment(2)),
    Relation(Post(2, Nil), Comment(3)),
    Relation(Post(3, Nil), Comment(4)),
    Relation(Post(4, Nil), Comment(5))
)

And the output should be: 

List(
    Post(1,List(Comment(1), Comment(2))),
    Post(2, List(Comment(3), Comment(4), Comment(5)))
)

With one level of nesting, this is easy: 

def collapse[A, B](relations: List[Relation[A, B]])(implicit f: (A, List[B]) => A): List[A] = {
    relations.groupBy(_.parent)
       .mapValues(_.map(_.child))
       .toList
       .map(f.tupled)
}

Where the implicit function require looks like this:

implicit def collapsePost(post: Post, comments: List[Comment]): Post = post.copy(comments = comments)

The trouble begins when I want to add another layer of nesting, and B could instead be another Relation. So I've tried many variations of this structure:

sealed abstract class Node
case class Relation[A, B <: Node](parent: A, child: B) extends Node
case class Child[B](value: B) extends Node

So now the example I seek to collapse looks more like this:

val relations = List(
    Relation(Blog(1, Nil), Relation(Post(1, Nil), Child(Comment(1)))),
    Relation(Blog(1, Nil), Relation(Post(2, Nil), Child(Comment(2)))),
    Relation(Blog(1, Nil), Relation(Post(2, Nil), Child(Comment(3))))
)

And the desired output: 

List(
    Blog(1, List(
           Post(1, List(Comment(1))),
           Post(2, List(Comment(2), Comment(3)))
        )
     )
)

The signature of my collapse function remains the same (for now). I can groupBy on the parent of the relations parameter, but then I get stuck at what would be the recursive step. At some point in the chain of functions within collapse, I'll have a Map[A, List[Node]], where List[Node] is either a List[Relation[B, ?]] or List[Child[B]]. The question mark notes my failure to move on. I've tried introducing TypeTags to pattern match the lists, since the types are erased, but the compiler will still complain about the second type parameter of Relation.

i.e. if list is a List[Node], then

list match {
    case rel @ List[Relation[B, _]] => collapse(rel) // Complains about missing TypeTag in recursive call to `collapse`
    case children @ List[Child[B]] => children
}

Is there a way around the missing type parameter in a recursively defined class like this (without the need for reflection, if possible)? Or perhaps I've just gone down the wrong path entirely.

Upvotes: 1

Views: 177

Answers (1)

wingedsubmariner
wingedsubmariner

Reputation: 13667

Here is a solution that doesn't use the Child class or require changes to collapse:

implicit def collapseBlog(blog: Blog, relations: List[Relation[Post, Comment]])(implicit f: (Post, List[Comment]) => Post) = {
  blog.copy(posts = collapse(relations))
}

We are taking advantage of recursive implicit resolution - collapseBlog will use collapsePost as its implicit and together they can collapse the two-level deep structure. Essentially, collapse(relations) becomes collapse(relations)((x, y) => collapseBlog(x, y)(collapsePost)) after implicit resolution.

Upvotes: 1

Related Questions