f# - 纯模式匹配

Question

我正在构建一个函数，用于计算某个字符在字符串中 nth 位置之后出现的次数。

countCh ("aaabbbccc", 3, 'b')
val it: int = 2

在 C 中，我会使用带有 while 循环的累加器。但我正在尝试学习 F# 功能面，不鼓励使用这种方法。 所以我使用守卫来测试一些条件并构建函数:

let rec countCh (s:string, n:int, ch:char) =
match s, n, ch with
   | (s, n, ch) when n > s.Length -> 0                          //p1
   | (s, n, ch) when n < 0 -> 0                                 //p2
   | (s, n, ch) when s.[n] <> ch -> countCh(s, n + 1, ch)       //p3
   | (s, n, ch) when s.[n] = ch -> 1 + countCh(s, n + 1, ch)    //p4

模式3 和4 的共存是有问题的(恐怕不可能)。即使它编译了，我也无法让它工作。如何在功能上处理此任务？

Answer 1

首先，这些分支的共存是没有问题的。它们彼此不冲突。你为什么认为它有问题？是因为您收到“不完整的模式匹配”编译器警告吗？该警告并没有告诉您分支冲突，它告诉您编译器无法证明这四个分支涵盖了所有可能性。还是您认为这是出于其他原因？如果您希望您的问题得到准确回答，您就必须问得更清楚。

其次，您滥用了模式匹配。看:没有图案!每个分支中的模式都完全相同且微不足道。只有守卫不同。这在 match 中看起来非常违反直觉，但可以用 if..elif 清楚地表达:

let rec countCh (s:string) n ch =
   if n >= s.Length || n < 0 then 0
   elif s.[n] = ch then 1 + countCh s (n + 1) ch
   else countCh s (n + 1) ch

注意 1:看看我是如何使参数柯里化(Currying)的？始终使用 curry 形式，除非有非常充分的理由使用元组。 Curried 参数在调用方使用起来更加方便。

注意 2:您的条件 n > s.Length 不正确:字符串索引从 0 到 s.Length- 1，所以保释条件应该是n >= s.Length。它已在我的代码中得到纠正。

最后，由于这是一个练习，我必须指出递归不是尾递归。查看第二个分支(在我的代码中):它递归调用函数，然后将结果加一。由于您必须对递归调用的结果执行某些操作，因此递归不能是“tail”。这意味着您有可能在很长的输入上出现堆栈溢出。

要使其成为tail 递归，您需要将函数“由内而外”，可以这么说。不是每次调用都返回结果，而是需要将它传递给每次调用(又名“累加器”)，并且只从终端案例返回:

let rec countCh (s:string) n ch countSoFar =
   if n >= s.Length || n < 0 then countSoFar
   elif s.[n] = ch then countCh s (n+1) ch (countSoFar+1)
   else countCh s (n+1) ch countSoFar

// Usage:
countCh "aaaabbbccc" 5 'b' 0

这样，每个递归调用都是“最后”调用(即函数不对结果做任何事情，而是直接将其传递给自己的调用者)。这称为“尾递归”，可以编译为在常量堆栈空间(与线性相反)中工作。