Recursively building a list of lists

Question

The following code compiles as long as the return type of the recursive call is Any, but obviously I'm doing something wrong because it should not have to be Any.

  case class Group(
    id: Long = -1,
    parentId: Long = -1,
    name: String = "")

  def makeTree(groupId: Long, groups: List[Group]) = {
    def getAllChildren(gid: Long): Any = {
      def children = for {
        g <- groups; if g.parentId == gid
      } yield g

      if (children.isEmpty) List()
      else {
        children map { x =>
          getAllChildren(x.id)
        }
      }
    }
    getAllChildren(groupId)
  }                                               
  val groups = List(Group(1, 0, "A"), 
                    Group(2, 1, "B"), 
                    Group(3, 1, "C"), 
                    Group(4, 2, "D"))

  makeTree(1, groups)
  //Results in: Any = List(List(List()), List())
  }

If I change the signature of getAllChildren to:

def getAllChildren(gid: Long): List[Group]

then I get an error:

type mismatch;  found   : List[List[Group]]  required: List[Group]

What am I doing wrong here.

Answer 1

Not really speaking scala, but it looks like, for some id, you collect the groups with that id, and then replace each group with a list of it's children, and so on.

Specifically, here:

  if (children.isEmpty) List()
  else {
    children map { x =>
      getAllChildren(x.id)
     }
  }

Indeed, here is the root of your error: Your algorithm allows for infinite recursion, and each recursion adds another List[...] around your return type. But you can't have a type with dynamic depth.

For example, if you try to fix this by giving type List[List[Group]], it will complain that it found List[List[List[Group]]], and so on, until you give up.

This is the way typecheckers tell us that we're about to program a potentially infinite recursion. You may have assumed the invariant that your hierarchy can't involve loops, yet this is not reflected in the types. In fact, it is not hard to construct an example where two groups are each others parents. In that case, your program will produce an ever deeper nesting list until it terminates due to lack of memory.

Note that you can't fix your code simply by using flatMap instead of map: the reason being that getAllChildren never ever produces a list with Group elements. It either returns an empty list, or, a flattened list of empty lists, that is, an empty list. Hence, if it should return at all, it would return an empty list in the flatmap version.