列出参数的折叠顺序

Question

嗨，我正在尝试理解以下代码。此代码的目的是计算素因数出现的次数。factors函数只找到给定数字的素因数。

let smallArray = Array.Parallel.init 5 factors;;
let checkMap key map =
match Map.tryFind key map with
| Some i -> i
| None -> 0
let incr map (key:int) = Map.add key ((checkMap key map) + 1) map
Array.fold (List.fold incr) Map.empty smallArray;; 

我卡住的地方是代码的最后一行。我不知道它是先做Array.fold还是List.fold，但我的猜测是List.fold。下一步是然后将函数incr应用于小数组并将其放入空映射中，但该函数incr接受 2 个参数，据我所知，我们只给它一个映射？有人可以解释一下吗？

Answer 1

我们首先总结一下这里涉及的函数类型：

List.fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State
Array.fold : ('State -> 'T -> 'State) -> 'State -> 'T [] -> 'State
incr : Map<int, int> -> int -> Map<int, int>

从其类型中可以看出，List.fold接受与incr形状相同的函数，接受两个参数并返回与其第一个参数相同类型的值。然后，将incr应用于List.fold将生成具有以下类型的部分应用的函数，然后再替换推断类型：

(List.fold incr) : 'State -> 'T list -> 'State

在将'State和'T替换为可以从incr应用程序中推断出的类型后，我们得到：

(List.fold incr) : Map<int, int> -> int list -> Map<int, int>

这又与incr具有相同的形状，唯一的区别是incr的第二个int参数在这里是一个int list。由于Array.fold具有与List.fold相同的基本形状，因此我们可以像使用上述incr相同的方式使用(List.fold incr)作为Array.fold的第一个参数。

Array.fold (List.fold incr)，如果部分应用，将产生以下类型：

(Array.fold (List.fold incr)) : Map<int, int> -> int list [] -> Map<int, int>

然后将Map.empty和smallArray分别作为初始值和集合应用于最后一个参数，以便：

• Array.fold可折叠smallArray，(List.fold incr)
• List.fold incr依次折叠在每int list上smallArray
• incr将其结果累积在源自传递给Array.fold的初始Map.empty值的Map<int, int>中。