@tailrec错误 - “针对超类型的递归调用” [英] @tailrec error - "recursive call targeting a supertype"

问题描述

我有以下问题。

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {

  @tailrec final def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet =
    if(p(elem))
      (this remove elem).filterAcc(p, acc incl elem)
    else
      (this remove elem).filterAcc(p, acc)

}

Scala拖动我，它无法优化@tairec，因为我的方法包含一个针对超类型的递归调用。 （NonEmpty的超类是TweetSet类，其中filterAcc方法被定义）。如何处理这样的错误？

Scala tels me, that it can not optimize @tairec, because my method contains a recursive call targeting a supertype. (Superclass of NonEmpty is class TweetSet, where the method filterAcc is defined). How to deal with such an error?

推荐答案

这是预期的行为。由于 @tailrec 的工作方式，错误发生：本质上，编译器试图将递归调用转换为本地循环。尽管事实上你的方法是递归的，但它通过调用它自己而不是相同类型的另一个实例，而是超类型的 - 因为 TweetSet 可能提供了一个完全不同的 filterAcc 的实现，编译器不能确保这个方法可以安全地扩展到一个循环。

This is intended behavior. The error occurs due to how @tailrec works: in essence, the compiler tries to transform a recursive call into a local loop. In spite of the fact that your method is recursive, it recurses by calling itself on another instance not even of the same type, but of the supertype - and since other children of TweetSet may provide a completely different implementation of filterAcc, the compiler cannot make sure this method can be safely expanded into a loop.

尾递归函数的经验法则是确保它总是完全调用本身作为最后一条语句 - 在您的情况下，而不是调用

A rule of thumb for tail-recursive functions is to ensure that it always calls exactly itself as the last statement - in your case, instead of calling

(this remove elem).filterAcc(...)

你必须按照模拟 this remove elem 的方式尝试转换 acc 并调用

you have to try and transform acc in the way that emulates this remove elem and call

filterAcc(p, <transformed acc>)

在涉及递归的函数式编程中，最好在超类中定义整个方法（在您的情况下 TweetSet ），并依赖p attern匹配ADT成员而不是多态 - 这种方式不会优化递归。

In functional programming involving recursion it is a good idea to define the entire method in the superclass (in your case TweetSet) and rely on pattern matching by ADT members instead of polymorphism - that way there will be no issues with optimizing recursion.

Upd：有一个不错的 blog post ：//stackoverflow.com/questions/17319412/how-does-tailrec-work>这个问题

Upd: There's a nice blog post explaining tail recursion, as specified in an answer to this question

这篇关于@tailrec错误 - “针对超类型的递归调用”的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！