什么是编写OCaml函数的正确流畅方式？

Question

我正在学习Jason Hickey's Introduction to Objective Caml。在学完第三章后，我似乎理解了let和fun的工作原理，但是我仍然有困难编写自己的fun。

---

以下是我面临的一个例子问题。

编写一个函数sum，给定两个整数边界n和m以及一个函数f，计算一个求和（不允许使用for循环）。即，sum n m f = f(n) + f(n+1) + ... + f(m)

---

那么，我应该如何开始考虑编写这个函数sum呢？

在Java或其他普通的编程语言中很容易实现。

由于不允许使用for循环，所以我猜我应该用let rec的方式来实现？

像这样：

let rec sum n m f = fun 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 是什么？

- Jackson Tale

---

请注意，如果您使用OCaml进行编程，永远不要再考虑循环：即使循环也是“let rec”表达式的语法糖。 - Kristopher Micinski

@KristopherMicinski，所以OCaml总是更喜欢使用rec吗？ - Jackson Tale

是的，这是进行任何递归的函数式方法。在OCaml的情况下，最好使用尾递归函数，它们不会建立堆栈帧。除非您真正理解循环只是语法糖并且您有充分的理由选择它们而不是递归，否则请不要再使用循环。 - Kristopher Micinski

@KristopherMicinski 我的解决方案不是尾递归的，对吧？ - Jackson Tale

http://goto.ucsd.edu/~rjhala/cse130/static/tailrecursion.pdf - Kristopher Micinski

@KristopherMicinski let rec sum1 n m f = sum2 n m 0 and sum2 n m s = if n <= m then sum2 (n+1) m (s+f n) else s;; 这个函数是尾递归吗？ - Jackson Tale

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)的结果中。因此，归纳思考，将问题分解为较小的部分，并考虑如何将这些较小部分的结果组合在一起。

希望我没有让事情更加混乱。

- Asiri Rathnayake

---

这段程序相关的内容是：let rec sum1 n m f = sum2 n m 0 and sum2 n m s = if n <= m then sum2 (n+1) m (s+f n) else s;; 这个程序是否是尾递归？ - Jackson Tale

是的，这个想法是使用一个累加器来跟踪到目前为止计算出的总和。因此，在计算过程中，您正在累加总和... 因此在结束时，您可以简单地返回累加值。这避免了操作返回子问题结果的需要（即，您可以立即返回子问题的结果）。 - Asiri Rathnayake

Answer 2

您犯了一个典型的语法错误：sum n+1 m f被解析为(sum n) + (1 n f)，而不是您期望的样子。在OCaml中，函数应用（空格）比中缀运算符具有更强的优先级。

类型错误源于sum n（您在求和中使用）不是整数。它需要一个额外的参数（m）和一个返回整数的函数。在类型推断过程的这一点上（当错误发生时），OCaml将其表示为'a -> ('a -> int) -> 'b：需要一些未知的东西a，一个从a到int的函数，并返回一些东西b。

- gasche

---

是的，谢谢，我已经更正为 sum(n+1) m f，现在它可以正常工作了。但是你能告诉我如何思考生成一个 fun 吗？这个逻辑与其他简单的编程语言非常不同。 - Jackson Tale

@JacksonTale 这不是通过评论来说明的，而是需要成为一个有经验的函数式程序员，并强制自己通过一些实例来工作。 - Kristopher Micinski

Answer 3

'a 就像 Java 中的泛型类型。例如： let test a = 1 它的类型是 'a -> int。 无论您的参数类型如何，此函数都将返回 1。

错误在于您需要在这里加上括号 (sum (n+1) m f)

Ocaml 认为这是多余的参数，因此结果与您预期的不同。加上括号可以确保您有正确数量的参数。当您有大量代码需要调试时，这是一个微妙的问题。因此，在类似情况下使用括号可以节省您很多时间。 :)

- clouddreams