4

我正在学习Jason Hickey 的 Objective Caml 简介。

在我学习了第 3 章之后，我似乎明白了letand是如何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？

4

3 回答 3

6

你犯了一个经典的语法错误：sum n+1 m f被解析为(sum n) + (1 n f)而不是你所期望的。在 OCaml 中，函数应用程序（空间）的优先级高于中缀运算符。

类型错误来自以下事实sum n：（您在总和中使用）不是整数。它需要一个参数 ( m) 和一个返回整数的函数。在类型推断过程的这一点上（发生错误时），OCaml 将其表示为'a -> ('a -> int) -> 'b：接受一些未知的东西a，一个函数 from ato int，并返回一些东西b。

于 2012-12-04T15:23:46.183 回答
6

我希望这将帮助您从递归而不是循环的角度思考（让我们暂时忽略尾递归）。

所以你需要计算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). 因此，进行归纳思考，将问题分解成更小的部分，并思考如何将这些小部分的结果组合在一起。

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

于 2012-12-04T16:29:21.797 回答
1

'a就像Java中的泛型类型。例如： let test a = 1 它的类型是'a -> int 无论你的参数是什么类型，这个函数都会返回 1。

错误是您需要在此处放置括号 (sum (n+1) m f)

Ocaml 将其视为额外的参数，因此它会产生与您预期不同的类型。加上括号可以确保你有正确数量的参数。当您有很多代码时，调试是一个微妙的问题。因此，在类似情况下使用括号可以为您节省大量时间。:)

于 2012-12-04T15:33:34.720 回答