What is the correct and smooth way to write a OCaml function?

Question

I am learning Jason Hickey's Introduction to Objective Caml.

After I learned Chapter 3, I seem to understand how the let and fun work. But still, I have troubles to write my own fun.

---

Here is an example problem I am facing.

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)

---

So, how should I start to think about producing this function sum?

In Java or normal programming language, it is easy.

Since here for loop is not allowed, so I guess I should do it in let rec way?

Something like this:

let rec sum n m f = fun i -> ....

I need an i to be a cursor?

Whatever, I can't continue to think out.

Can anyone point a road for me to produce a OCaml fun?

---

This is my final solution:

let rec sum n m f = if n <= m then (f n)+(sum n+1 m f) else 0;;

but of course, it is wrong. The error is Error: This expression has type 'a -> ('a -> int) -> 'b but an expression was expected of type int

Why? and what is 'a?

Answer 1

I'm hoping this will help you to think in terms of recursion and not with loops (let's leave out tail recursion for a moment).

So you need to calculate f(n) + f(n+1) + ... f(m). It might help you to think of this problem in an inductive fashion. That is, assume you know how to calculate f(n+1) + ... + f(m), then what do you need to do in order to calculate the original result? well, you simply add f(n) to the latter, right? That is exactly what your code has to say:

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 *)

You can see how I have added f(n) to the result of f(n+1) + .... + f(m). So, think inductively, break down the problem into smaller pieces and think about how you can put the results of those smaller pieces together.

Hope I didn't make things more confusing.