algorithm - Scala 树/图实现

Question

我对“客户邀请”有疑问，其中一个人可以邀请另一个人，并且邀请仅在被邀请人邀请某人时才有效。

为了解决这个问题，我想写一个树算法而不是图算法。

我正在尝试用 Scala 编写这个树结构，我是这样开始的:

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)
        */
  }  

}

输入将是这样的:

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

我想使用 Option[List[MyNode]]，因为子节点是可选的，如果节点已被邀请，我想将值设置为一个空列表而不是 None。

树是解决我的问题的最佳结构，还是我应该去图或类似的东西(图中的一个节点可以有多个子节点？)？另一个问题……这些行 (h::t) 和 (h::: t) 有什么区别？

以下代码存在编译错误:

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

如何使用 Option[List]？

Answer 1

应该是

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)
    */}  

你匹配的是选项对象而不是元组。这场比赛并不详尽，因为你错过了

case Some(Nil) => ....

我发现只使用没有可选的列表会更好。这主要是关于语义的。可选意味着有些东西是空的。我们有空列表(Nil)的值，所以我们不需要使用额外的对象来标记这种情况。空列表应该足够了

::: 函数在您的列表前面添加给定列表的元素。这个函数只是用来连接两个列表
:: 是在列表开头添加元素的函数。
同样在 Scala 中，:: 是一个有头和尾的案例类。如果您想了解更多关于 List 实现的信息，我建议您阅读 https://www.amazon.com/Functional-Programming-Scala-Paul-Chiusano/dp/1617290653