斯卡拉遞歸計算給定謂詞的元素

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