Глубокое обратное вложенные списки в Scala

Я хотел бы изменить рекурсивно список списков в Scala.

Я написал глубокие перестановки в Python следующим образом:

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

Как бы сделать эквивалент в Scala? Проблема не в алгоритме - это тип материала, который я новичок.

Мне нужна функция, чтобы взять список [T] или Список [Список [T]], или список T и списки Ts, на любую произвольную глубину. Я попытался сделать класс case, чтобы сделать это на примере, который я видел в другом месте. Мне не нужна функция, которая просто возвращает Any и принимает Any; это похоже на обман.

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

Тем не менее, я не мог заставить мои типы балансировать. Я новичок в Scala, но я решил, что это будет прекрасная возможность возиться с рекурсией и набором текста.

Ответ 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 имеет значение null, это означает, что оно не является. Если у нас есть это доказательство того, что 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)(_ + _))

Стандартный подход к определению приоритетов двух заключается в том, чтобы помещать нижний приоритет неявным в признаке (WhateverLow), а другой в объекте (WhateverHigh), который расширяет этот признак. В довольно простом случае, как это, однако, более кратким (и яснее, на мой взгляд) использовать трюк аргумента по умолчанию в моем методе rev выше. Но вы, скорее всего, увидите другую версию в коде других людей.

Ответ 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))
}

Единственная проблема с этим заключается в том, что для каждого типа вложенного списка вам требуется класс типа.