Deep-Reverse von verschachtelten Listen in Scala

Question

Ich möchte eine Liste von Listen rekursiv in Scala umkehren.

ich geschrieben habe tiefe Liste kehrt in Python wie folgt aus:

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

Wie würde ich das Äquivalent in Scala zu tun? Das Problem ist nicht der Algorithmus - es ist der Typ, auf dem ich neuer bin.

Ich brauche die Funktion, um eine Liste von [T], oder eine Liste [Liste [T]], oder eine Liste von T und Listen von Ts, zu einer beliebigen Tiefe zu nehmen. Ich habe versucht, eine Fallklasse zu erstellen, die auf einem Beispiel basiert, das ich anderswo gesehen habe. Ich möchte keine Funktion, die Any zurückgibt und Any akzeptiert; das fühlt sich an wie Betrug.

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

Trotzdem konnte ich meine Typen nicht ganz ausgleichen. Ich bin neu in Scala, aber ich dachte mir, dass es eine perfekte Gelegenheit wäre, sich mit Rekursion und Tippen zu beschäftigen.

Answer 1

Es ist eigentlich nicht zu schwer, eine Version des Typs Class-Ansatzes zu schreiben, die sschaef, dass für beliebig verschachtelt Listen funktionieren schlägt:

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) 

Das implizite Argument ev in unserer rev Methode gibt Hinweise darauf, dass A selbst reversibel, und wenn ev null ist, bedeutet das, dass es nicht ist. Wenn wir diesen Beweis haben, dass A umkehrbar ist, verwenden wir es, um die Elemente unserer List[A] umzukehren (das ist, was die map macht), und dann kehren wir die Liste selbst um. Wenn wir diesen Beweis nicht haben (den getOrElse Fall), können wir die Liste einfach umkehren.

konnte Wir schreiben rev etwas weniger prägnant (aber möglicherweise mehr performant) wie folgt aus:

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:

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

Um eine dieser beiden Versionen zu testen, können wir folgendes schreiben erwartet.

---

Ich sollte hinzufügen, dass die folgende ist eine gemeinsame Idiom die implicits Recht in einem Fall wie diesem zu bekommen:

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

Wenn wir listReverser und nestedListReverser auf dem gleichen Niveau gerade geschrieben hatte, wir würden die folgende Fehlermeldung erhalten, wenn wir versuchen, eine Liste von Listen zu umkehren:

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

der Standardansatz, die beiden zu priorisieren ist, die niedrigere Priorität imp zu setzen legal in einem Merkmal (WhateverLow) und das andere in einem Objekt (WhateverHigh), das dieses Merkmal erweitert.In einem ziemlich einfachen Fall wie diesem ist es jedoch prägnanter (und klarer, für mein Auge), den Standard-Argument-Trick in meiner obigen Methode zu verwenden. Aber Sie sehen die andere Version eher im Code anderer Leute.

Answer 2

Wenn Sie wollen das wirklich haben typsicher dann das typeclass Muster ist dein Freund:

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

Das einzige Problem dabei ist, dass Sie eine typeclass für jede verschachtelte Liste Typ benötigen.