list - Scala中List数据结构的基本实现

Question

我正在学习 Scala，在我正在阅读的一本书 (Functional Programming in Scala) 中，我遇到了一个自定义 List 的示例Scala中的实现如下:

sealed trait MyList[+A]
case object MyNil extends MyList[Nothing]
case class Cons[+A](head: A, tail: MyList[A]) extends MyList[A]
object MyList {
  def apply[A](as: A*): MyList[A] =
    if (as.isEmpty) MyNil
    else Cons(as.head, apply(as. tail: _*))
}

我想延长 MyList添加以下功能:

添加 tail返回 MyList 的所有元素的方法没有第一个的实例，例如val x = MyList(1,2,3); x.tail == MyList(2,3) .

添加 sum仅在 MyList 时适用的方法包含 Int s (对于所有数字类型甚至更好)。所以例如val x = MyList(1,2,3); x.sum == 6

上面2个问题的想法是要理解:(1)如何与我的类的实例交互以及(2)如何在这种情况下使用多态性。经过一番搜索，我什至不知道如何从这些问题开始，这就是我问这个问题的原因。

任何提示将不胜感激。非常感谢!

更新:

一些更新:

首先，我想指出，我前面提到的函数式编程类(class)中编程挑战的解决方案可以找到 here。 ，但是，我正在寻找与作者要求的有所不同的东西。

我设法找到了第一个问题的答案“如何在我的实例本身上使用 tail，例如 MyList(1,2,3).tail？”。为了解决这个问题，我不得不以下列方式修改原始特征:

sealed trait MyList[+A] {
  def tail: MyList[A] = MyList.tail(this)
}

我不确定这是否是做我想做的事情的最佳方式，但它确实有效。如果有人有更好的建议，请告诉我。

第二部分更难。我想在同一特征中添加以下内容:

def sum[Int]: MyList[Int] = MyList.sum(this)

但是 IntelliJ 提示 this 的类型这是 A我需要有条件地在 this 上应用它属于 Int 类型.

另一种选择是执行以下操作:

def sum: Int = this match {
    case x: MyList[Int] => MyList.sum(x)
 }

但是如果我们想为 String 创建另一个实现呢？这也将返回 String ?这不可能是正确的解决方案，我还没有找到。请帮忙 :)

Answer 1

。尾部

我注意到您的 Cons类已经有一个公共(public) tail成员。我很想从那里开始，让它变得普遍......

sealed trait MyList[+A] {
  def tail: MyList[A]
}

...并添加 MyNil执行。

case object MyNil extends MyList[Nothing] {
  def tail: MyList[Nothing] = 
    throw new java.lang.UnsupportedOperationException("tail of empty list")
}

这就是标准库 List处理空列表的尾部。另一个可能更温和的选择是返回 this使尾空 MyList只是空的 MyList .

离开 class Cons和 object MyList不变，我们得到了预期的结果。

MyList('s','h','o','w').tail  //res0: MyList[Char] = Cons(h,Cons(o,Cons(w,MyNil)))
MyList(9).tail.tail           //java.lang.Unsupported...

。和

这有点棘手。我们希望每个 .sum仅当元素是可求和类型时才调用编译，例如 Int .实现此目的的 Scala 方法要求调用站点提供元素类型可接受的隐式“证据”。

sealed trait MyList[+A] {
  def sum(implicit ev : A =:= Int) : Int  //can sum only if A is Int
}

唉，这不会编译，因为 MyList在 A 上是协变的, 但作为传递参数的类型将 A处于反变位置。

Error: covariant type A occurs in invariant position in type A =:= Int of value ev

幸运的是，有一个解决方法:使用与 A 相关的不同类型参数。但不限于它的协变关系。

sealed trait MyList[+A] {
  def sum[B >: A](implicit ev : B =:= Int) : Int = 0  //default behavior
}

case object MyNil extends MyList[Nothing] { ... //unchanged

case class Cons[+A](head: A, tail: MyList[A]) extends MyList[A] {
  override def sum[B >: A](implicit ev :B =:= Int) : Int = head + tail.sum[B]
}

object MyList { ... //unchanged

MyList(23,31,12).sum   //res0: Int = 66
MyList("as","is").sum  //won't compile

数字[A]

这适用于 Int ，但是对于每个可求和类型都必须做同样的事情会很痛苦。幸运的是，标准库提供了 Numeric类型类，它为其伞下的所有数字类型( zero ， one ， plus() 等)。

所以，把它们放在一起:

sealed trait MyList[+A] {
  val tail: MyList[A]
  def sum[B >: A](implicit ev : Numeric[B]): B = ev.zero
}

case object MyNil extends MyList[Nothing] {
  val tail: MyList[Nothing] = this
}

case class Cons[+A](head: A, tail: MyList[A]) extends MyList[A] {
  override def sum[B >: A](implicit ev : Numeric[B]): B = ev.plus(head, tail.sum[B])
}

object MyList {
  def apply[A](as: A*): MyList[A] =
    if (as.isEmpty) MyNil else Cons(as.head, apply(as.tail: _*))
}