list - Scala 中嵌套列表的深度反转

Question

我想在 Scala 中递归地反转列表列表。

我已经在 Python 中编写了这样的深层列表反转:

def deepReverse(items):
    if type(items) == list:
        return [deepReverse(item) for item in reversed(items)]
    else: 
        return items

我将如何在 Scala 中做等效的事情？问题不在于算法——它是类型的东西，我比较新。

我需要该函数来获取任意深度的 [T] 列表或 List[List[T]] 或 T 列表和 T 列表。我尝试根据我在其他地方看到的一个例子制作一个案例类来做到这一点。我不想要一个只返回 Any 并接受 Any 的函数；感觉像是在作弊。

case class NL[+T](val v : Either[List[NL[T]],T])

尽管如此，我还是无法完全平衡我的类型。我是 Scala 的新手，但我认为这是一个搞乱递归和打字的绝佳机会。

Answer 1

编写 sschaef 提出的适用于任意嵌套列表的类型类方法的版本实际上并不难:

trait Reverser[C] {
  def reverse(xs: C): C
}

implicit def rev[A](implicit ev: Reverser[A] = null) = new Reverser[List[A]] {
  def reverse(xs: List[A]) =
    Option(ev).map(r => xs map r.reverse).getOrElse(xs).reverse
}

def deepReverse[A](xs: A)(implicit ev: Reverser[A]): A = ev.reverse(xs)

隐式参数 ev在我们的 rev方法是证据 A本身是可逆的，如果 ev为空，这意味着它不是。如果我们有证据表明 A是可逆的，我们用它来反转我们 List[A] 的元素(这就是 map 正在做的事情)，然后我们反转列表本身。如果我们没有这个证据( getOrElse 案例)，我们可以颠倒列表。

我们可以写 rev不那么简洁(但可能更高效)，如下所示:

implicit def rev[A](implicit ev: Reverser[A] = null) = if (ev == null) {
  new Reverser[List[A]] {
    def reverse(xs: List[A]) = xs.reverse
  }
} else {
  new Reverser[List[A]] {
   def reverse(xs: List[A]) = (xs map ev.reverse).reverse
  }
}

要测试这两个版本中的任何一个，我们可以编写以下内容:

scala> deepReverse(List.tabulate(3)(identity))
res0: List[Int] = List(2, 1, 0)

scala> deepReverse(List.tabulate(2,3) { case (a, b) => a + b })
res1: List[List[Int]] = List(List(3, 2, 1), List(2, 1, 0))

scala> deepReverse(List.tabulate(2, 3, 4, 5, 6) {
     |   case (a, b, c, d, e) => a + b + c + d + e
     | }).head.head.head.head
res2: List[Int] = List(15, 14, 13, 12, 11, 10)

正如预期的那样。

我应该补充一点，以下是在这样的情况下正确使用隐式的更常见的习语:

trait ReverserLow {
  implicit def listReverser[A] = new Reverser[List[A]] {
    def reverse(xs: List[A]) = xs.reverse
  }
}

object ReverserHigh extends ReverserLow {
  implicit def nestedListReverser[A](implicit ev: Reverser[A]) =
    new Reverser[List[A]] {
      def reverse(xs: List[A]) = xs.map(ev.reverse).reverse
    }
}

import ReverserHigh._

如果我们刚刚写了 listReverser和 nestedListReverser在同一级别，当我们尝试反转列表列表时，我们会收到以下错误:

scala> deepReverse(List.tabulate(2, 3)(_ + _))
<console>:12: error: ambiguous implicit values:
 both method listReverser...
 and method nestedListReverser...
 match expected type Reverser[List[List[Int]]]
              deepReverse(List.tabulate(2, 3)(_ + _))

对两者进行优先排序的标准方法是将较低的优先级隐含在一个 trait ( WhateverLow ) 中，另一个放在扩展该 trait 的对象 ( WhateverHigh ) 中。不过，在这样一个相当简单的情况下，在我的 rev 中使用默认参数技巧更简洁(在我看来更清晰)。方法同上。但是您更有可能在其他人的代码中看到其他版本。