Clever Geek Handbook

Scala: find method in tree with optional return type

I am writing a find method on a tree like structure. This is my code:

def find[T](node: Node, findThisGuy: T): Option[Node] = {
    if (node.data == findThisGuy) {
        Some(node)
    } else {
        if (node.children.nonEmpty) {
            node.children.foreach(child => {
                find(child, findThisGuy)
            })
        } else {
            None
        }
    }
}

The problem here is internal if it has a return type Unit

that matches the return type of the ie function Option[Node]

. So how can I determine the return type of internal if

? I am open to suggestions for a better implementation of the above method.

+3


source to share


2 answers


I think this will do the trick:



def find[T](node: Node, findThisGuy: T): Option[Node] = {
  if (node.data == findThisGuy) {
    Some(node)
  } else {
    node.children.view
      .map(child => find(child, findThisGuy))
      .collectFirst{case Some(guy) => guy}
  }
}
+2


source


Your problem is that you are not using self-start return in find

. You should use a standard for:

def find[T](node: Node, findThisGuy: T): Option[Node] = {
  if (node.data == findThisGuy)
    return Some(node)

  for (c <- node.children) {
    val found = find(c, findThisGuy)
    if (found.isDefined)
      return found
  }
  None
}


Note that there is no need to query if (node.children.nonEmpty)

if you go to the array later. An empty traversal does nothing.

Also, it might look less functional, but has the advantage that it stops searching as soon as it finds a node, instead of evaluating ALL children. General error IMHO.

+1


source






More articles:


All Articles