2

我有以下函数返回整数列表的元素之间的距离列表：

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

尽管调用似乎处于尾部位置，但这::阻止了我使用注释。@tailrecrecurse

是否有@tailrec兼容的方式进行连接？

我可以使用累加器，但我必须反转输入或输出，对吗？

编辑：我对递归方法特别感兴趣。我的具体用例有点复杂，因为一次调用recurse可以将多个项目添加到结果列表中：

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

距离函数只是演示问题的一个例子。

4

4 回答 4

5

这不是对确切原始请求的回复，而是该问题的替代解决方案。

您可以简单地压缩列表，将相同的列表“移动”一个位置，然后将生成的压缩列表映射到元组元素的差异。

在代码中

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-29T14:13:35.027 回答
3

我不确定你是否可以在没有累加器变量的情况下做你想做的事情，以确保正确的尾调用优化。我用累加器和最后的反向模拟了一个重做。您可以通过追加而不是前置来消除最后的反向，但我相信前置/反向组合在创建更大的列表时会更有效。

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-29T13:52:39.197 回答
1

如果您想对列表的相邻元素进行操作，sliding您的朋友是：

def dist(list: List[Int]) = list.sliding(2).collect{case a::b::Nil => b-a}.toList
于 2013-04-29T18:22:05.583 回答
1

抱歉有点晚了，Haskell 和 ML 中存在的标准模式也适用于 scala。这与 cmbaxter 的答案非常相似，但我想我只是将其添加以供参考，当我开始使用 Scala 时，这样的事情会对我有很大帮助。

递归遍历列表时始终使用累加器模式。此外，我在这里使用了定义函数的柯里化形式，而不是元组形式。

同样与您的代码有关，我会将所有模式匹配语句放在递归函数本身中，而不是使用外部 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-29T14:47:23.773 回答