遞歸列表連接

我有以下函數返回一個整數列表中的元素之間的距離的列表：遞歸列表連接

def dists(l: List[Int]) = { 
    //@annotation.tailrec 
    def recurse(from: Int, rest: List[Int]): List[Int] = rest match { 
    case Nil => Nil 
    case to :: tail => to - from :: recurse(to, tail) 
    } 

    l match { 
    case first :: second :: _ => recurse(first, l.tail) 
    case _ => Nil 
    } 
}

的::阻止我使用@tailrec註解雖然看上去調用recurse處於尾部位置。

是否有@tailrec兼容的方式來進行串接？

我可以使用累加器，但然後我將不得不反轉輸入或輸出，對不對？

編輯：我特別感興趣的遞歸方法。我的具體使用情況是比較複雜的一個調用recurse一點可以幾個項目添加到結果列表：

=> item1 :: item2:: recurse(...)

距離函數只是爲了說明問題的例子。

來源

2013-04-29 André Rüdiger

我發現很多次，積累和倒退比我嘗試過的其他替代方案快。它總是取決於具體情況，但不要害怕扭轉。 – huynhjl 2013-04-29 14:47:30

我認爲積累+逆轉是現在的方式。謝謝！ – 2013-04-29 15:29:19

積累和反轉的通常替代方法是差異列表的概念，其中積累了通過附加而不是列表本身來建立列表的函數。這可能不適用於JVM，雖然... – 2013-04-29 16:36:19

我不確定你可以做什麼，你正在試圖做的沒有累加器變量，以確保適當的尾部呼叫優化。我最後用累加器和反向模擬了重做。你可以通過附加而不是前置來消除反轉，但是我相信創建更大的列表時prepend/reverse組合會更有效率。現在

object TailRec { 
    def dists(l: List[Int]) = { 
    @annotation.tailrec 
    def recurse(from: Int, rest: List[Int], acc:List[Int]): List[Int] = rest match { 
     case Nil => acc 
     case to :: tail => 
     val head = to - from 
     recurse(to, tail, head :: acc) 
    } 

    val result = l match { 
     case first :: second :: _ => recurse(first, l.tail, List()) 
     case _ => Nil 
    } 
    result.reverse 
    } 

    def main(args: Array[String]) { 
    println(dists(List(1,5,8,14,19,21))) 

    } 
}

，你想，你可能只是這樣做dists功能與開箱即用的功能，可在List像這樣：

List(1,5,8,14,19,21).sliding(2).filterNot(_.isEmpty).map(list => list.last - list.head)

這最終可能會降低效率，但更簡潔。

來源

2013-04-29 13:52:39 cmbaxter

我認爲，作爲一個fp lang的scala會提供一個比累積+逆轉這樣的基本問題更優雅的方法，但我會忍受它。謝謝！ – 2013-04-29 15:20:17

我沒有想過這裏的細節，但是積累和反轉是否是「正確的」解決方案取決於手頭的算法，而不是使用的語言。那麼，至少它不依賴於使用的特定語言，而是它的評估策略。例如，你可能在Haskell中以不同的方式處理這個問題，因爲大多數人認爲它的尾部遞歸在那裏不常見。 – 2013-04-29 16:27:14

這不是對原始請求的確切回覆，而是對問題的替代解決方案。

您可以簡單地將列表用同一個列表「移位」一個位置壓縮，然後將生成的壓縮列表映射到元組元素的差異。

在代碼

def dist(l: List[Int]) = l.zip(l drop 1) map { case (a,b) => b - a}

如果你無法理解發生了什麼情況我會建議拆分操作，如果你想對鄰居元素進行操作的REPL

scala> val l = List(1,5,8,14,19,21) 
l: List[Int] = List(1, 5, 8, 14, 19, 21) 

scala> l zip (l drop 1) 
res1: List[(Int, Int)] = List((1,5), (5,8), (8,14), (14,19), (19,21)) 

scala> res1 map { case (a, b) => b - a } 
res2: List[Int] = List(4, 3, 6, 5, 2)

來源

2013-04-29 14:13:35

感謝您的回答，但我對遞歸方法更感興趣。我的具體用例稍微複雜一點：對recurse的一次調用可能會在結果列表中添加幾項：''=> item1 :: item2 :: recurse（...）''距離函數是隻是舉例說明問題。 – 2013-04-29 15:02:56

我建議你明確地將此評論添加到原始文章，以免人們錯誤地投票給出此答案。 – 2013-04-29 15:17:03

另外請記住，如果可以使用高級操作（因爲它們在其他結構上工作並且可能比您要做的更優化），則顯式遞歸通常是不鼓勵的。在你的情況下，如果你需要每次迭代發射多個元素，你可以很容易地切換到'flatMap'而不是'map'。 – 2013-04-29 16:34:52

探索列表，sliding是你的朋友：

def dist(list: List[Int]) = list.sliding(2).collect{case a::b::Nil => b-a}.toList

來源

2013-04-29 18:22:05 Landei

對不起，遲到了，斯坦存在於Haskell和ML中的dard模式也在scala中工作。這與cmbaxter的回答非常相似，但我認爲我會添加它以供參考，當我開始Scala時，這樣的東西會大量幫助我。

通過列表遞歸時始終使用累加器模式。此外，我用這裏定義函數的curried形式而不是tupled形式。

同樣與你的代碼有關，我會把所有模式匹配語句放在遞歸函數中，而不是使用外部的val。

def build (l1: List[Int]) (acc: List[Int]): List[Int] = 
l1 match { 
    case Nil => acc 
    case h::t => build (t) (acc.::(h)) 
    case _ => acc 
}             //> build: (l1: List[Int])(acc: List[Int])List[Int]  
    val list1 = List(0, 1, 2)      //> list1 : List[Int] = List(0, 1, 2) 
    val list2 = List(3, 4, 5, 6)     //> list2 : List[Int] = List(3, 4, 5, 6) 
    val b = build(list1)(list2)     //> b : List[Int] = List(6, 5, 4, 3, 0, 1, 2)

來源

2013-07-29 14:47:23

遞歸列表連接

回答

相關問題