rekursiv verschachtelte Listen in scala behandeln

Question

Ich unterrichte mich selbst und versuche meine FP-Fähigkeiten zu mästen.

Eine meiner Referenzen, Essentials of Programming Languages ​​(available here), hat eine praktische Liste von einfachen rekursiven Funktionen. Auf Seite 27/50 werden wir aufgefordert, die Funktion swapper() zu implementieren.

(swapper s1 s2 slist) returns a list the same as slist, but 
with all occurrences of s1 replaced by s2 and all occurrences of s2 replaced by s1. 


> (swapper ’a ’d ’(a b c d)) 
(d b c a) 
> (swapper ’a ’d ’(a d() c d)) 
(d a() c a) 
> (swapper ’x ’y ’((x) y (z (x)))) 
((y) x (z (y))) 

In scala, das ist:

swapper("a", "d", List("a","b","c","d")) 
swapper("a", "d", List("a","d",List(),"c","d")) 
swapper("x", "y", List(List("x"), "y", List("z", List("x")))) 

Meine scala Version behandelt alle Versionen der endgültigen x speichern.

def swapper(a: Any, b: Any, lst: List[Any]): List[Any] ={ 
    def r(subList :List[Any], acc : List[Any]): List[Any] ={ 
    def swap (x :Any, xs: List[Any]) = 
     if(x == a){ 
     r(xs, acc :+ b) 
     } else if (x == b) { 
     r(xs, acc :+ a) 
     } else { 
     r(xs, acc :+ x) 
     } 
    subList match { 
    case Nil => 
     acc 
    case List(x) :: xs => 
     r(xs, r(List(x), List()) +: acc) 
    case x :: xs => 
     swap(x,xs) 
    //case List(x) :: xs => 
    } 
    } 
    r(lst, List()) 
} 

Instinktiv ich denke, das ist, weil ich keine Swap auf dem Abschnitt habe „Fall List (x) :: xs“ aber ich bin immer noch kämpfen, um es zu beheben.

Noch schwieriger, dieser Fall bricht die Tail-Call-Optimierung. Wie kann ich das tun und wo kann ich mehr über die allgemeine Lösung erfahren?

Answer 1

können Sie diesen foldRight mit Ansatz Mustererkennung verwenden:

oder sogar simplier (dank @marcospereira):

def swapper(a:Any, b:Any, list:List[Any]):List[Any] = 
    list.map { 
    case item if item==a => b 
    case item if item==b => a 
    case item:List[Any] => swapper(a, b, item) 
    case item => item 
    } 

Answer 2

Ein einfacher Weg, dies zu lösen, ist map nur verwenden:

def swapper[T](a: T, b: T, list: List[T]): List[T] = list.map { item => 
    if (item == a) b 
    else if (item == b) a 
    else item 
} 

Answer 3

Dies scheint zu funktionieren.

def swapper[T](a: T, b: T, lst: List[_]): List[_] = { 
    val m = Map[T, T](a -> b, b -> a).withDefault(identity) 
    def swap(arg: List[_]): List[_] = arg.map{ 
    case l: List[_] => swap(l) 
    case x: T => m(x) 
    } 
    swap(lst) 
} 

Die List Elemente sind inkonsistent, weil es ein Element sein könnte oder es könnte ein anderer List, so dass der Typ sein, ist List[Any], die ein sicher, dass jemand diese Datendarstellung zu überdenken muss seufzen ist.