在Scala中对嵌套列表进行深度反转 [英] Deep-reverse of nested lists in Scala
问题描述
我想在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的列表和Ts的列表带到任意深度.我尝试根据其他地方看到的示例制作案例类来实现这一点.我不想要一个只返回Any并接受Any的函数；感觉就像在作弊.
case class NL[+T](val v : Either[List[NL[T]],T])
不过，我仍然无法完全平衡我的类型.我是Scala的新手，但我认为这是一个很好的机会来解决递归和键入问题.
编写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)
我们的rev方法中的隐式参数ev证明了A本身是可逆的，并且如果ev为null则意味着它不是可逆的.如果我们有证据表明A是可逆的，则可以使用它来反转List[A]的元素(这是map所做的事情)，然后反转列表本身.如果没有这个证据(在getOrElse情况下)，我们可以反转列表.
我们可以这样写得更简洁一些(但可能更高性能):
case class NL[+T](val v : Either[List[NL[T]],T])
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)(_ + _))
对两者进行优先级排序的标准方法是将较低优先级隐式地放在特征(WhateverLow)中，另一优先级隐含在扩展该特征的对象(WhateverHigh)中.但是，在这样一个相当简单的情况下，在我上面的rev方法中使用默认的参数技巧更加简洁(在我看来是更清晰).但是您更有可能在他人的代码中看到另一个版本.
I'd like to reverse a list of lists, recursively, in Scala.
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
How would I do the equivalent in Scala? The problem isn't the algorithm - it's the type stuff, which I'm newer on.
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])
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.
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)
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.
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)
As expected.
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._
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)(_ + _))
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屋！
