斯卡拉递归计算给定谓词的元素

Question

我有这个迭代函数来计算列表中布尔值的数量。

def countBoolIter[A](test: A=>Boolean, a: List[A]) = { 
    var count = 0 
    for(elem <- a){ 
     if(test(elem)) count += 1 
    } 
    count 
} 

传入的第一个参数是isBool功能：

def isBool(i: Any) = i match { 
    case _: Boolean => true 
    case _ => false 
} 

调用函数如下：

countBoolIter(isBool, List(1, true, 3, true, false, "hi")) 
// Output: 3 

现在，我试着将它转换成尾递归功能如下：

def countBoolRec[A](test: A=>Boolean, a: List[A], acc: Int = 0): Int = a match { 
    case Nil => acc 
    case h :: t if(test(h)) => countBoolRec(test, a, acc+1) 
    case h :: t => countBoolRec(test, a, acc) 
} 

但是，我得到一个运行时错误，因为函数不返回任何东西;没有错误抛出。我认为它陷入了一个无限循环，这就是为什么没有返回。

问题：我应该如何解决我尝试的递归实现？

Answer 1

有一个在功能countBoolRec一个错误：

@tailrec 
    def countBoolRec[A](test: A=>Boolean, a: List[A], acc: Int = 0): Int = a match { 
     case Nil => acc 
     case h :: t if(test(h)) => countBoolRec(test, t, acc+1) 
     case h :: t => countBoolRec(test, t, acc) 
    } 

在递归调用，使用T作为参数和没有再次。如果没有，基本上，你处于无限循环。

此外，最好使用@tailrec注释来确保实现是“尾递归”。

Answer 2

您反复使用与输入相同的列表进行递归。

考虑其中a.head通过该测试的情况下：

countBoolRec（测试中，a，0） countBoolRec（测试中，a，1） countBoolRec（测试中，a，2） ...和等

@scala.annotation.tailrec // Not that your original code wasn't tail-recursive, but it's a generally good practice to mark code that isn't tail recursive with this annotation 
def countBoolRec[A](test: A=>Boolean, a: List[A], acc: Int = 0): Int = a match { 
    case Nil => acc 
    case h :: t if (test(h)) => countBoolRec(test, t, acc + 1) 
    case h :: t => countBoolRec(test, t, acc) 
} 

虽然你可能也无妨写：

(0 /: a) { (acc, v) => acc + (if (test(v)) 1 else 0) }