帮我解释一下这个 F# 递归示例程序

Question

let rec aggregateList (f:int->int->int) init list = 
    match list with
    | [] -> init
    | hd::tl -> 
        let rem = aggregateList f init tl
        f rem hd

let add a b = a + b
let mul a b = a * b

//to use in F# Interactive:
//aggregateList add 0 [1..5];;

从 Thomas Petricek 的“现实世界的函数式编程”中得到这个例子，

我不明白该模式匹配的第二个分支：f rem hd。 有人可以帮助我吗？

Answer 1

让我们首先分解一下aggregateList 函数声明。该函数采用三个参数：

1. 一个名为 f 的函数，它采用两个 int 并返回第三个 int。
2. 开始聚合的初始值。
3. 值列表。

然后，该函数将与提供给它的列表进行以下两种可能性之一的匹配：

1. 列表为空，在这种情况下，它返回 init 的值。
2. 列表不为空，在这种情况下，它将获取第一项并将其分配给 hd （或 head），并将列表的其余部分分配给 tl （或尾巴）。然后它执行递归调用aggregateList f init tl。当返回时，它获取结果并将其分配给rem。然后它在 rem 和 hd 上调用 f。

正如其他人指出的那样，这与 的作用相同基本 F# 库中的 List.foldback 函数。

当然，要小心地正确选择 init 值，因为如果执行 aggregateList mul 0 somelist;; 你只会得到 0 no无论您提供什么清单。

Answer 2

它调用函数 f（参数之一），给出递归调用的结果和下一项。

rem 是余数，或者在本例中是余数值的结果。

hd 是下一项，如 | 中所示。 hd::tl -> 模式匹配的一部分。

实际上，这个聚合函数采用一个函数、一个起点和一个列表。表示示例行的一种方法是：

(1 + (2 + (3 + (4 + (5 + 0)))))

Answer 3

只是为了好玩，让我们做一些 printf 风格的调试：

> aggregateList (fun acc x -> printf "%i " x; acc + x) 0 [1..10];;
10 9 8 7 6 5 4 3 2 1 val it : int = 55

看起来该函数相当于 List.foldBack （或其他语言中的 fold_right） ：它从右到左遍历列表中的每个项目并调用它们的函数 f 。

让我们用几种不同的方式重写该函数：

// functional version
let rec foldBack f seed = function
    | [] -> seed
    | x::xs -> let res = foldBack f seed xs in f res x

// imperative version
let foldBack f seed xs =
    let mutable result = seed
    for x in List.rev xs do
        result <- f result x
    result

// C# equivalent
public static U FoldBack<T, U>(Func<T, U> f, U seed, IEnumerable<T> xs) {
    foreach(T x in xs.Reverse())
        seed = f(seed, x);
    return seed;
}

您可以像这样使用该函数：

let sum = foldBack (+) 0 [1..10] // returns 55
let sumOfSquares = foldBack (fun acc x -> acc + x * x) 0 [1..10];; // 385

---

我不明白第二个分支
该模式匹配：f rem hd。可以
有人帮助我吗？

那么，让我们从我们已经了解的 F# 函数开始：

• f 是一个类型为 int ->; 的函数。整数-> int。您传递函数就像传递任何其他变量（例如整数或字符串）一样。
• 您可以通过传递以空格分隔的参数列表来调用函数。 f rem hd 使用两个参数调用函数 f：rem 和 hd。
• 函数中计算的最后一个表达式被视为函数的返回值。

那么回到原来的函数：

let rec aggregateList (f:int->int->int) init list = 
    match list with
    | [] -> init
    | hd::tl -> 
        let rem = aggregateList f init tl   // 1
        f rem hd                            // 2

在第 1 行中，我们使用 tl 反复调用 aggregateList。由于列表变得越来越小，我们最终会遇到 nil 情况，它返回 init。

在第 2 行中，f rem hd 是函数的返回值。然而，由于我们在到达列表末尾时递归了堆栈，因此当我们沿着堆栈跟踪向上走时，我们将针对每个元素（按从右到左的顺序）调用此函数。

给定 aggregateList (+) 0 [1..10]，nil 情况返回 0，因此我们调用：

• 返回值 = f rem hd = f 0 10 = 0 + 10 = 10
• 返回值 = f rem hd = f 10 9 = 9 + 10 = 19
• 返回值 = f rem hd = f 19 8 = 19 + 8 = 27
• 返回值 = f rem hd = f 27 7 = 27 + 7 = 34
• 返回值 = f rem hd = f 34 6 = 34 + 6 = 40
• 返回值 = f rem hd = f 40 5 = 40 + 5 = 45
• 返回值 = f rem hd = f 45 4 = 45 + 4 = 49
• >返回值 = f rem hd = f 49 3 = 49 + 3 = 52
• 返回值 = f rem hd = f 52 2 = 52 + 2 = 54
• 返回值< /em> = f rem hd = f 54 1 = 54 + 1 = 55

列表中没有更多项目，因此整个函数返回 55。

正如您可以想象的，对于长度为 n 的列表，aggregateList 中的嵌套调用的计算方式如下：

f (f (f (f (f (f (f (f init) hd_n) hd_n-1) hd_n-2) hd_n-3) ... hd ₂) 高清₁) 高清₀