遞歸地處理scala中的嵌套列表

我的一個參考文獻，編程語言基礎（available here），有一個方便的遞歸函數列表。在第27/50頁上，我們被要求實現swapper（）函數。

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

在Scala中，這就是：

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

我的斯卡拉版本處理所有版本保存最終的X。

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

出於本能，我想這是因爲我對部分沒有交換「的情況下列表（x）:: XS」，但我仍然在努力解決它。

更困難的是，這種情況下打破了尾部呼叫優化。我如何做到這一點，我可以去哪裏瞭解更多關於通用解決方案的信息？

來源

2016-09-06 peoplemerge

您可以使用此foldRight與模式匹配的方法：

甚至simplier（感謝@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 
    }

來源

2016-09-06 01:30:23 Nyavro

OK！感謝您的洞察力，這確實可以簡化事情。雖然添加註釋@tailrec的確抱怨遞歸調用不是尾部位置。 – peoplemerge

一個更簡單的解決這個只是用map方式：

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 
}

來源

2016-09-06 03:56:11 marcospereira

似乎無法處理OP的第三個測試用例。 – jwvh

這似乎工作。

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

的List元件是不一致的，因爲它可能是一個元件，或者它可能是另一個List，所以類型爲List[Any]，這是一個肯定的嘆息有人需要重新考慮這個數據表示。 OK！

來源

2016-09-06 04:14:17 jwvh

遞歸地處理scala中的嵌套列表

回答

相關問題