如何在 Scala 中实现不变列表? [英] How should an invariant List be implemented in Scala?

问题描述

我想在 Scala 中实现一个链表，其中类型参数是不变的，与标准库 List 不同.

I want to implement a linked list in Scala where the type parameter is invariant, unlike the standard library List.

这是一个尝试:

sealed trait InvariantList[T]
case object Nil extends InvariantList[_]
case class Cons[T](head : T, tail : InvariantList[T]) extends InvariantList[T]

object InvariantList {
  def map[A, B](xs : InvariantList[A])(f : A => B) : InvariantList[B] = {
    xs match {
      case Nil => Nil[B]
      case Cons(head, tail) => Cons(f(head), map(tail)(f))
    }
  }
}

object Example {
  val xs = Cons(7, Cons(5, Nil[Int]))
  InvariantList.map(xs)(_ + 1)
}

这与我想要的非常接近，但是在map的实现和示例使用中必须指定Nil的类型参数很烦人.

This is pretty close to what I want, but it is annoying to have to specify the type parameter of Nil in the implementation of map and in the example use.

我也尝试过使用 case class Nil[T]() extends InvariantList[T]，但这也很难看，因为我必须把括号放在所有地方.

I also tried using case class Nil[T]() extends InvariantList[T], but this is also ugly because I have to put the parens all over the place.

在不变链表实现中定义 Nil 的推荐方法是什么?我认为这个问题更普遍地适用于任何具有空构造函数的情况的不变数据结构.我希望它像标准库List 一样方便使用(方便的是我不必指定类型参数或添加括号).

What is the recommended way of defining Nil in an invariant linked list implementation? I think the question applies more generally to any invariant data structure that has cases with empty constructors. I would like it to be as convenient to use as the standard library List (convenient in that I don't have to specify the type parameter or add parens).

推荐答案

标准库没有用于其不变集合的 Nil 元素.例如，Set 和 ListBuffer 是不变的，但它们没有 Nil 子类型.他们要求你说 Set.empty[A] 或 ListBuffer.empty[A].

The standard library doesn't have a Nil element for its invariant collections. For example, Set and ListBuffer are invariant, but they do not have Nil sub-type. They require you to say Set.empty[A] or ListBuffer.empty[A].

scala> val l : ListBuffer[Int] = Nil
<console>:11: error: type mismatch;
 found   : scala.collection.immutable.Nil.type
 required: scala.collection.mutable.ListBuffer[Int]
       val l : ListBuffer[Int] = Nil
                                 ^

scala> val set: Set[Int] = Nil
<console>:11: error: type mismatch;
 found   : scala.collection.immutable.Nil.type
 required: Set[Int]
       val set: Set[Int] = Nil
                           ^

有一个 case 对象 Nil extends InvariantList[_] 由于不变性而不起作用.每个列表类型都需要它自己的空表示.因为空的 List[Dog] 与空的 List[Animal] 不同，如果 Dog <: Animal 等

Having a single case object Nil extends InvariantList[_] won't work because of invariance. Every list type would require it's own empty representation. Because an empty List[Dog] would not be the same as an empty List[Animal], if Dog <: Animal, etc.

您本质上要求的是一个单例符号 Nil 被视为许多不同的类型.我认为您在案例类方面走在正确的轨道上，因为这将允许您为每种列表类型使用一个 Nil[A].不幸的是，这永远不会允许您在 Nil 上进行模式匹配，只能在 Nil() 上进行模式匹配，因为您需要一个带参数的提取器，而不是一个用于单例的提取器(您的 Nil 不是).如果想要不写类型参数和括号的方便，可以在同一个包里写一个这样的方法:

What you're essentially asking for is a singleton symbol Nil to be treated like many different types. I think you're on the right track with a case class, because that will allow you one Nil[A] per list type. Unfortunately that will never allow you to pattern-match on Nil, only Nil(), because you need an extractor with parameters and not one for a singleton (which your Nil is not). If you want the convenience of not writing the type parameter and parentheses, you can write a method like this in the same package:

def nil[A] = Nil[A]()

这并不理想，但可以部分解决您的问题.综合起来:

It's not ideal, but it will partially solve your problem. Putting it all together:

sealed trait InvariantList[A]

case class Nil[A]() extends InvariantList[A]

case class Cons[A](head : A, tail : InvariantList[A]) extends InvariantList[A]

object InvariantList {

  def map[A, B](xs : InvariantList[A])(f : A => B) : InvariantList[B] = {
    xs match {
      case Nil() => nil
      case Cons(head, tail) => Cons(f(head), map(tail)(f))
    }
  }

}

scala> val xs = Cons(7, Cons(5, nil))
xs: Cons[Int] = Cons(7,Cons(5,Nil()))

scala> InvariantList.map(xs)(_ + 1)
res0: InvariantList[Int] = Cons(8,Cons(6,Nil()))

这篇关于如何在 Scala 中实现不变列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！