Scala 中嵌套列表的深度反转 [英] Deep-reverse of nested lists in Scala

问题描述

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

I'd like to reverse a list of lists, recursively, in Scala.

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

I've written deep list reverses in Python like this:

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

我将如何在 Scala 中执行等效操作?问题不在于算法 - 而是类型的东西，我对此较新.

How would I do the equivalent in Scala? The problem isn't the algorithm - it's the type stuff, which I'm newer on.

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

I need the function to take a list of [T], or a List[List[T]], or a list of T's and lists of Ts, to any arbitrary depth. I tried making a case class to do that based on an example I'd seen elsewhere. I don't want a function that just returns Any and accepts Any; that feels like cheating.

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

不过，我还是无法完全平衡我的类型.我是 Scala 的新手，但我认为这是处理递归和输入的绝佳机会.

Still, I couldn't quite get my types to balance out. I'm new to Scala, but I figured it'd be a perfect opportunity to mess with recursion and typing.

推荐答案

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

It's actually not too hard to write a version of the type class approach that sschaef proposes that will work for arbitrarily nested lists:

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)

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

The implicit argument ev in our rev method is evidence that A itself is reversable, and if ev is null that means it's not. If we have this evidence that A is reversable, we use it to reverse the elements of our List[A] (this is what the map is doing), and then we reverse the list itself. If we don't have this evidence (the getOrElse case), we can just reverse the list.

我们可以像这样编写 rev 不那么简洁(但可能更高效):

We could write rev a little less concisely (but possibly more performantly) like this:

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
  }
}

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

To test either of these two versions, we can write the following:

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)

正如预期的那样.

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

I should add that the following is a more common idiom for getting the implicits right in a case like this:

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，当我们尝试反转列表列表时，我们会得到以下错误:

If we'd just written listReverser and nestedListReverser at the same level, we'd get the following error when we try to reverse a list of lists:

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)(_ + _))

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

The standard approach to prioritizing the two is to put the lower priority implicit in a trait (WhateverLow) and the other in an object (WhateverHigh) that extends that trait. In a fairly simple case like this, though, it's more concise (and clearer, to my eye) to use the default argument trick in my rev method above. But you're more likely to see the other version in other people's code.

这篇关于Scala 中嵌套列表的深度反转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！