Deep-reverse of nested lists in Scala

Question

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.

Answer 1

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.

Answer 2

If you wanna have this really typesafe then the typeclass pattern is your friend:

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

The only problem with this is that you need a typeclass for each nested list type.