Scala - 匿名函数的递归

Question

Scala - 匿名函数的递归

6

我正在完成Scala实验的内容，正在构建一个函数，最终会返回类似于这样的结果:

tails(List(1,2,3,4)) = List(List(1,2,3,4), List(2,3,4), List(3,4), List(4), List())

我通过使用两个函数并在第二个函数上使用一些递归来使其工作。

def tails[T](l: List[T]): List[List[T]] = {
    if ( l.length > 1 )trailUtil(List() ::: List(l))
    else List() ::: List(l);
}

def trailUtil[T](l:List[List[T]]) : List[List[T]] = {
    if ( l.last.length == 0)l
    else trailUtil(l :+ l.last.init);
}

这都很好，但我需要两个函数来实现这个。我试着用匿名函数替换trailUtil(List() ::: List(l))，但我的 IDE 报错说type mismatch; found :List[List[T]] required:Int。请帮我看看。

val ret : List[List[T]] = (ll:List[List[T]]) => {
    if ( ll.last.length == 0) ll else ret(ll :+ ll.last.init)
}
ret(List() ::: List(1))

请问有人能指出我做错了什么，或者提供更好的方法吗？

（我看过这篇stackoverflow帖子，但不同类型对我来说都不起作用）：

- locrizak

你的问题标题中包含“anonymous”。这些不是匿名函数，匿名函数应该采用(inputs) => expression的形式，即没有名称。我不知道在Scala中是否可以递归一个没有名称的函数。在Javascript中，可以使用已弃用的callee来实现。 - Shelby Moore III

4个回答

2

实际上你可以在另一个def中定义def。这允许定义一个真正有名称的函数，可以被引用和用于递归。下面是如何实现tails函数：

def tails[T](l: List[T]) = {
    @annotation.tailrec
    def ret(ll: List[List[T]]): List[List[T]] =
        if (ll.last.isEmpty) ll 
        else ret(ll :+ ll.last.tail)

    ret(l :: Nil)
}

这个实现也是尾递归的。我添加了@annotation.tailrec注释，以确保它确实是尾递归（如果不是，代码将无法编译）。

您还可以使用内置函数tails（请参见ScalaDoc）：

List(1,2,3,4).tails.toList

tails返回Iterator，如果你需要它，你需要将其转换为列表（就像我所做的那样）。此外，结果将在末尾包含一个额外的空值（在我的示例中，结果将是List(List(1, 2, 3, 4), List(2, 3, 4), List(3, 4), List(4), List())），因此你需要处理它。

- tenshi

虽然这是真的，但它与我所拥有的并没有太大的区别。 - locrizak

@locrizak：我认为你不能使用一等函数进行递归，你需要使用“def”来实现。 - tenshi

1

你做错的是这个：

val ret : List[List[T]]

所以ret是一个T类型的列表的列表。然后你这样做：

ret(ll :+ ll.last.init)

这意味着您正在对一个类型为列表的列表调用方法apply。列表的apply方法需要一个Int参数，并返回具有该索引的元素。例如：

scala> List("first", "second", "third")(2)
res0: java.lang.String = third

我猜你想写的是 val ret: List[List[T]] => List[List[T]]，也就是一个接受 List[List[T]] 并返回 List[List[T]] 的函数。但你会遇到其他问题，因为在定义中 val 引用了自身。为了解决这个问题，你可以将其替换为 lazy val：

def tails[T](l: List[T]): List[List[T]] = {
  lazy val ret : List[List[T]] => List[List[T]] = { (ll:List[List[T]]) => 
    if ( ll.last.length == 0) ll 
    else ret(ll :+ ll.last.init)
  }
  if ( l.length > 1 )ret(List() ::: List(l))
  else List() ::: List(l);
}

但是，当然，简单的解决方案是将一个def放在另一个内部，就像tenshi建议的那样。

- Daniel C. Sobral

1

你也可以使用折叠功能：

val l = List(1,2,3,4)

l.foldLeft(List[List[Int]](l))(  (outerList,element) => {
    println(outerList)
    outerList.head.tail :: outerList
})

第一个参数列表是您的起始值/累加器。第二个函数是修改器。通常，它会修改起始值，然后将其传递给列表中的每个元素。我包含了一个println，以便您可以在迭代列表时查看累加器。

- Austen Holmes

太厉害了！你知道使用foldLeft比其他示例有额外的开销吗？ - locrizak

我不这么认为。看一下源代码： https://lampsvn.epfl.ch/trac/scala/browser/scala/tags/R_2_9_1_final/src//library/scala/collection/LinearSeqOptimized.scala#L1 106 override /TraversableLike/ 107 def foldLeft[B](z: B)(f: (B, A) => B): B = { 108 var acc = z 109 var these = this 110 while (!these.isEmpty) { 111 acc = f(acc, these.head) 112 these = these.tail 113 } 114 acc 115 } - Austen Holmes

哇，那个发布不干净。不管怎样，fold left /: 有一个简写：我总是忘记它，直接输入 foldLeft。 - Austen Holmes

很多Scala集合库的编写都是为了看起来像是递归的，但实际上它们是以迭代方式编写的，这是由于JVM和堆栈大小的限制。这就是一个例子。在这里有一个很好的解释，说明了他们试图实现什么：http://www.artima.com/scalazine/articles/scala_collections_architecture.html（也摘自我强烈推荐的书《Programming in Scala》）。 - Austen Holmes

我明白了，大约已经看了250页。我想亲自尝试一些练习，所以我找到了Scala实验室。现在每当我遇到不理解的练习时，就会反复跳回来回。 - locrizak

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tomasz Nurkiewicz · Accepted Answer

这样怎么样：

def tails[T](l: List[T]): List[List[T]] = 
  l match {
    case h :: tail => l :: tails(tail)
    case Nil => List(Nil)
  }

And a little bit less idiomatic version:

def tails[T](input: List[T]): List[List[T]] =
    if(input.isEmpty)
        List(List())
    else
        input :: tails(input.tail)

顺便提一下，尽量避免使用List.length，因为它的时间复杂度是O(n)。

更新：如tenshi所建议的，可以使用尾递归解决：

@tailrec def tails[T](l: List[T], init: List[List[T]] = Nil): List[List[T]] =
    l match {
        case h :: tail => tails(tail, l :: init)
        case Nil => init
    }