递归, 守卫表达式, 模式¶

递归 (Recursion)¶

函数式编程不存在类似 for 的循环语句, 因为这类循环通常需要可变变量, 但函数式编程不存在可变变量.
因此函数式编程使用递归而非迭代.

下面实现阶乘函数 factorial:

factorial n =
  if n <= 1 then
    1
  else
    n + factorial(n - 1)

近似的命令式代码如下:

fn factorial(n: u32) -> u32 {
    if n <= 1 {
        1
    } else {
        n * factorial(n - 1)
    }
}

even' 0 = True
even' n = odd' (n - 1)

odd' 0 = False
odd' n = even' (n - 1)

even' 0 = True
even' 1 = False
even' n = even' (n - 2)

factorial n
  | n <= 1    = 1
  | otherwise = n * fac(n - 1)

其中 otherwise 是 True 的同义词:

ghci> otherwise
True

如果之前的表达式都为 False, 最后的 otherwise 可以用于处理其他剩余情况.
类似于命令式编程语言里 switch 语句中的 default, 或者 Rust 语言 match 语句中的 _ 表达式.

is_zero 0 = True
is_zero _ = False

模式匹配将从上向下寻找第一个匹配的模式, 所以下面的 is_zero 函数将永远返回 False:

is_zero _ = False
is_zero 0 = True

factorial 0 = 1
factorial 1 = 1
factorial n = n * factorial (n - 1)

与上面的实现方法相比, 由于该 factorial 函数实现缺少对 n 为负数情况的处理, 但 n 为负数时将导致无限循环.
与 if 和守卫表达式相比, 模式匹配只能匹配具体的值, 无法编写表达式.

函数 drop' 用于 "丢弃" 列表中的前 n 个元素, 并返回剩余元素:

drop' 0 xs = xs
drop' n [] = []
drop' n (_:xs) = drop' (n - 1) xs

函数 maximum' 用于求列表中的最大值:

maximum' [] = error "Cannot be called on an empty list"
maximum' [x] = x
maximum' (x:xs) = if x > maximum' xs then x else maximum' xs

上述代码中的 (x:y:xs) 模式匹配只能在编译时决定从列表中提取元素的数量.
如果需要在运行时指定可以借助 take 和 drop 函数来实现:

group n [] = []
group n xs =
  let
    first = take n xs
    rest  = drop n xs
  in
    first : group n rest