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的列表以及Ts的列表作为列表。我试着根据我在其他地方看到的一个例子做一个案例课。我不想要一个返回Any并接受Any的函数;那感觉就像是作弊。

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

尽管如此，我还是无法让我的类型达到平衡。我是新来的Scala，但我认为这将是一个完美的机会来混淆递归和打字。

Answer 1

这其实不是太难写一个版本sschaef提出，将用于任意嵌套列表的工作类型的类方法：在我们rev方法

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证据表明A本身可逆的，并且如果ev为空，则意味着它不是。如果我们有证据表明A是可逆的，我们用它来反转我们的List[A]的元素（这就是map正在做的），然后我们反转列表本身。如果我们没有这个证据（getOrElse的情况），我们可以颠倒这个列表。

我们可以写rev少一点简洁（但可能更performantly）是这样的：

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) 

由于预期。

---

我要补充一点，下面是一个比较常见的成语用于获取implicits就在这样的情况下：

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

优先化两者的标准方法是将较低优先级的imp （WhateverLow）的合法性，另一个在延伸该特征的对象（WhateverHigh）中。在这样一个相当简单的例子中，尽管如此，在我的rev方法中使用默认参数技巧更简洁（在我眼中更清晰）。但是你更有可能在其他人的代码中看到其他版本。

Answer 2

如果你想拥有这真的安全类型，则类型类模式是您的朋友：

object Reverse extends App { 

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

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

    implicit def List2Reverser[A] = new Reverser[List[List[A]]] { 
    def reverse(xs: List[List[A]]) = 
     xs.map(_.reverse).reverse 
    } 

    implicit def List3Reverser[A] = new Reverser[List[List[List[A]]]] { 
    def reverse(xs: List[List[List[A]]]) = 
     xs.map(_.map(_.reverse).reverse).reverse 
    } 

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

    val xs = List(1,2) 
    val xxs = List(List(1,2),List(1,2),List(1,2)) 
    val xxxs = List(List(List(1,2),List(1,2)),List(List(1,2),List(1,2)),List(List(1,2),List(1,2))) 

    println(deepReverse(xs)) 
    println(deepReverse(xxs)) 
    println(deepReverse(xxxs)) 
} 

与此唯一的问题是，你需要为每个嵌套列表类型的类型类。