placplacboom placplacboom - 1 month ago 31
Scala Question

Scala Tree/Graph Implementation

I have a problem about a "customer invitation" where a person can invite another person and the invitation is only valid if the invited person invitee someone.

To solve this problem, i was thinking to write a Tree algorithm instead a Graph algorithm.

I'm trying to write this tree structure in Scala and here is how i've started:

case class MyNode(key:Int, children:Option[List[MyNode]] = None)

class MyNodeManager {

def find(key: Int, tree: Option[List[MyNode]]) = tree match {
case None => None
case (h :: t) =>
println("aa")
/*if(h.key == key)
Option(h)
else
find(h ::: t)
*/
}

}


The input will be something like:

val invites = List((1, 2), (1, 3), (3, 6))


I would like to work with Option[List[MyNode]] because children are option and if the node has been invited, i would like to set value an empty list instead None.

Tree is the best structure to solve my problem or should i go to Graph or something like that (a node in a graph can have multiple children?)? And the other question..what's the difference on those lines (h :: t) and (h ::: t)?

The following code has a compile error:

Error:(16, 13) constructor cannot be instantiated to expected type;
found : scala.collection.immutable.::[B]
required: Option[List[MyNode]]
case (h :: t) =>
^


How can i work with Option[List]?

Answer

Should be

def find(key: Int, tree: Option[List[MyNode]]) = tree match {
case None => None
case Some(h :: t) =>
  println("aa")
/*if(h.key == key)
    Option(h)
  else
    find(h ::: t)
    */}  

You are match Option object not tuple. This match is not exhaustive because you are missing

case Some(Nil) => ....

I find it will be better to use only list without Optional. This is mostly about semantic. Optional means something is empty. We have value for empty list (Nil) so we don't need to use additional object to mark such situation. Empty list should be enough

::: function adds the elements of a given list in front of your list. Simply this function is used to concatenate two list
:: is function which add element at the begging of the list.
Also in Scala :: is a case class which have head and tail. If you want to know more about List implementation I suggest you to read https://www.amazon.com/Functional-Programming-Scala-Paul-Chiusano/dp/1617290653