递归列表连接

我有以下函数返回一个整数列表中的元素之间的距离的列表：递归列表连接

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

递归列表连接

回答

相关问题