Reverso profundo de listas anidadas en Scala

Question

Me gustaría revertir una lista de listas, recursivamente, en Scala.

lista profundo que he escrito en Python invierte así:

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

¿cómo lo haría el equivalente en Scala? El problema no es el algoritmo, es el tipo de cosas, que soy más nuevo.

Necesito la función para tomar una lista de [T], o una Lista [Lista [T]], o una lista de T y listas de Ts, a cualquier profundidad arbitraria. Traté de hacer una clase de caso para hacer eso en base a un ejemplo que había visto en otro lugar. No quiero una función que simplemente devuelva Any y acepte Any; eso se siente como hacer trampa

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

Aún así, no pude hacer que mis tipos se equilibraran. Soy nuevo en Scala, pero pensé que sería una oportunidad perfecta para meterse con la recursividad y el tipeo.

Answer 1

En realidad no es demasiado difícil escribir una versión del enfoque de clase de tipo que sschaef propone que va a trabajar para listas arbitrariamente anidados:

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) 

El argumento implícito ev en nuestro método rev evidencia de que A sí está reversible, y si ev es nulo eso significa que no lo es. Si tenemos esta evidencia de que A es reversible, lo usamos para invertir los elementos de nuestro List[A] (esto es lo que está haciendo el map), y luego invertimos la lista. Si no tenemos esta evidencia (el caso getOrElse), podemos simplemente invertir la lista.

Podríamos escribir rev un poco menos de forma concisa (pero posiblemente más performantly) así:

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

Para probar cualquiera de estas dos versiones, podemos escribir lo siguiente:

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) 

Como esperado.

---

Debo añadir que el siguiente es un lenguaje más común para conseguir los implícitos justo en un caso como este:

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._ 

Si hubiéramos acaba de escribir listReverser y nestedListReverser en el mismo nivel, que tendríamos el siguiente error cuando tratamos de revertir una lista de listas:

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

el enfoque estándar para la priorización de los dos es poner la prioridad más baja imp lícito en un rasgo (WhateverLow) y el otro en un objeto (WhateverHigh) que extiende ese rasgo.En un caso bastante simple como este, sin embargo, es más conciso (y más claro, a mi juicio) utilizar el truco de argumento predeterminado en mi método rev anterior. Pero es más probable que veas la otra versión en el código de otras personas.

Answer 2

Si quieres tener esto realmente typesafe entonces el patrón de clase de tipos es su amigo:

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

El único problema con esto es que se necesita una clase de tipos para cada tipo de lista anidada.