tree.md

This example highlights the eager evaluation problem. Let's give it a bit of though:

Assume we have a tree:

  A
 / \
B   C
   / \
  B   D

Here we have duplicates, as it will make a problem a bit more general. We want

findPathToNode(tree, A) = Some([A])
findPathToNode(tree, B) = Some([A, B])
findPathToNode(tree, C) = Some([A, C])
findPathToNode(tree, D) = Some([A, C, D])
findPathToNote(tree, E) = None

Side note: from here we see that it makes sense to change the return type to either List[Node], where empty list will indicate non-existence. Or Option[NonEmptyList[Node]] (which is isomorphic to List[Node]) if we want to have Option as outer type (and that actually makes sense).

Current solution is quite unreadable. Let's divide a problem:

findPathToNode(tree, node) = allPaths(tree).find(_.endsWith(node))
// where
allPaths(tree: Tree[A]): List[NonEmptyList[Node]] = ???

The allPaths(tree) is much easier to write:

def allPaths(tree: Tree): List[NonEmptyList[Node]] = 
  NonEmptyList(tree.node) :: tree.children flatMap { child =>
    allPaths(child) map { path =>
      tree.node <:: path
    }
  }

// or with for comprehension
def allPaths(tree: Tree): List[NonEmptyList[Node]] = 
  NonEmptyList(tree.node) :: for {
    child <- tree.children
    path <- allPaths(child)
  } yield (tree.node <:: path)

The problem is that we will generate all the paths, even only the first one is enough, in eager language as Scala.

Thus the allPaths could be rewritten to be of type

def allPaths(tree: Tree): Stream[NonEmptyList[Node]] = ???

The class Stream implements lazy lists where elements are only evaluated when they are needed