编写OCaml函数的正确和顺畅的方法是什么？

Question

我正在学习Jason Hickey的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)

---

那么,我该如何开始考虑生成这个函数和？

在Java或普通编程语言中,它很容易.

因为这里不允许循环,所以我想我应该这样做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

您已经完成了一个经典的语法错误:sum n+1 m f被解析为(sum n) + (1 n f)而不是您期望的.在OCaml中,函数应用程序(空间)比中缀运算符具有更强的优先级.

类型错误来自于sum n(在总和中使用)不是整数的事实.它需要一个参数(m)和一个返回整数的函数.在类型推断过程的这一点上(当错误发生时),OCaml将其表示为'a -> ('a -> int) -> 'b:将一些未知的东西a,一个函数从aint转换为int,并返回一些东西b.

Answer 2

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

所以你需要计算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).因此,以归纳的方式思考,将问题分解成更小的部分,并考虑如何将这些较小的部分的结果放在一起.

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