functional-programming - 编写 OCaml 函数的正确且流畅的方法是什么？

Question

我正在学习 Jason Hickey's Introduction to Objective Caml 。

学了第3章之后，我似乎明白了let和fun是如何工作的。但是，我仍然无法编写自己的 fun 。

这是我面临的一个示例问题 。
Write a function sum that, given two integer bounds n and m and a function
f, computes a summation (no for loop allowed). i.e., sum n m f = f(n) + f(n+1) + ... + f(m)
那么，我应该如何开始考虑生成这个函数 sum 呢？

在 Java 或普通的编程语言中，这很容易。

因为这里不允许 for 循环，所以我想我应该用 let rec 的方式来做？

像这样的东西:
let rec sum n m f = fun i -> ....
我需要一个 i 作为游标？

无论如何，我无法继续思考。

谁能为我指出一条产生 OCaml 乐趣的道路？

这是我的最终解决方案:
let rec sum n m f = if n <= m then (f n)+(sum n+1 m f) else 0;;
但当然，这是错误的。错误是 Error: This expression has type 'a -> ('a -> int) -> 'b
but an expression was expected of type int
为什么？什么是'a？

Answer 1

我希望这会帮助你从递归而不是循环的角度思考(让我们暂时忽略尾递归)。

所以你需要计算 f(n) + f(n+1) + ... f(m) 。它可能会帮助您以 归纳 方式思考这个问题。也就是说，假设您知道如何计算 f(n+1) + ... + f(m) ，那么您需要做什么才能计算出原始结果？好吧，您只需将 f(n) 添加到后者，对吗？这正是您的代码所说的:

let rec sum n m f =
  if n = m then
    f m
  else
    f n + sum (n + 1) m f;; (* here's the inductive step *)

您可以看到我如何将 f(n) 添加到 f(n+1) + .... + f(m) 的结果中。因此，归纳思考，将问题分解为更小的部分，并考虑如何将这些小部分的结果放在一起。

希望我没有让事情变得更困惑。