Loop through first n elements of array in OCaml

Question

I have the following function in OCaml which sums the first c elements in an array passed as an argument:

let rec sum_array c a =
    if c < 0 then 0
    else a.(c) + sum_array (c - 1) a;;

I happen to know what the array a is in advanced, so I'd like to set this. I tried:

fun c -> let int_array = [| 1 ; 2 ; 3 ; 4 ; 5 |] in
    let rec sum_array c =
        if c < 0 then 0
        else int_array.(c) + sum_array (c - 1);;

But OCaml complains with an ambiguous 'Error: Syntax error', which is super helpful.

1. How can I fix this function definition? How can I specify that I want the value of sum_array returned?
2. How can I get OCaml to report more helpful error messages?

Answer 1

This answer may seem a little lengthy, but that's only because I see from your error certain lack of understanding in some basic notions of OCaml. This may be a good chance to clear things up a little.

Scope and Sequencing in OCaml

You may or may not already understand this topic already. I still have to elaborate on this a little since they are the basis of what follows.

Think of how you would test your code:

let rec sum_array c a =
    if c < 0 then 0
    else a.(c) + sum_array (c - 1) a
in
sum_array 2 [| 1 ; 2 ; 3 ; 4 ; 5 |]         ;;

I assume you are familiar with ordinary programming languages. To put it in a Java way:

//Java version
int a = 1;
int b = 1;
int c = a + b;

Would be translated into OCaml code of:

(* OCaml version *)
let a = 1 in
let b = 1 in
let c = a + b in
c       ;;

They are not all that different. At first glance, OCaml's way of representing sequencing (that is ;) seems tedious. But as your journey of functional programming goes on, you will understand the importance of such an mechanism more.

Faulty Logic

As the result shows:

let rec sum_array c a =
    if c < 0 then 0
    else a.(c) + sum_array (c - 1) a
in
sum_array 2 [| 1 ; 2 ; 3 ; 4 ; 5 |] ;;
(* - : int = 6   *)

The logic you did here is a little faulty. Your function added one more element than necessary. The fix is simple:

let rec sum_array c a =
    if c = 0 then 0
    else a.(c - 1) + sum_array (c - 1) a
in
sum_array 2 [| 1 ; 2 ; 3 ; 4 ; 5 |] ;;
(* - : int = 3  *)

And it works right now. The function now sums up the first n elements of the array.

How to Store [| 1 ; 2 ; 3 ; 4 ; 5 |] into the Function so that it only takes the argument n ?

I assume this is what you mean by saying : I happen to know the array a in advance.

And here is simple codes to do that with very little change:

let rec sum_array c =
let a = [| 1 ; 2 ; 3 ; 4 ; 5 |] in
    if c = 0 then 0
    else a.(c - 1) + sum_array (c - 1)          ;;

Then you can run it just like this:

sum_array 3;;
(* - : int = 6   *)

See the little change here is just use another let ... in to hardcode the definition of a inside the function definition. This is exactly how one would do the same thing in java.

All being said, What is wrong with Your Own Code?

Your code:

fun c -> let int_array = [| 1 ; 2 ; 3 ; 4 ; 5 |] in
    let rec sum_array c =
        if c < 0 then 0
        else int_array.(c) + sum_array (c - 1);;

fails for two reasons:

• Shadowing: It looks like that this function takes c as argument, but actually it does nothing with c after it's passed in. That's because you have another same name argument c for your function sum_array (which is a helper function for the outer overall function), and this argument shadowed the binding, or definition of the outmost argumet c.
• Scope: within the definition of this big function, you defined int_array and sum_array. But they are both local names, and you did not return anything. Recall that the return value for a function is the value of the entire expression on the right side of the arrow. And what is that value in this case? Nothing, other than the definitions of a few local variables, which expires as soon as the function ends.

This is the right code:

fun arg -> let int_array = [| 1 ; 2 ; 3 ; 4 ; 5 |] in
        let rec sum_array c =
            if c < 0 then 0
            else int_array.(c) + sum_array (c - 1)
        in sum_array arg

But there is another problem, this function above, is a function. That means it's a value. And if you don't bind a value to a variable right now, you either use it right now, or you lose track of it. So the better thing to do here is:

let sum_first_n = 
fun arg -> let int_array = [| 1 ; 2 ; 3 ; 4 ; 5 |] in
        let rec sum_array c =
            if c < 0 then 0
            else int_array.(c) + sum_array (c - 1)
        in sum_array arg        ;;

And now you can call it like any other function.

Of course I am still using your faulty logic in this code. Fixing that, we have:

let sum_first_n = 
fun arg -> let int_array = [| 1 ; 2 ; 3 ; 4 ; 5 |] in
        let rec sum_array c =
            if c = 1 then int_array.(0)
            else int_array.(c - 1) + sum_array (c - 1)
        in sum_array arg        ;;

sum_first_n 3;;
(* - : int = 6        *)

And now everything works right.

How to do it More Functionally ?

What if you are given an argument of a List rather than an array? How would you do it without mutation?

This is good practice to help you get quicker on track of OCaml.

Here is the code:

let rec sum_array c l = match c,l with
    | _, [] | 0, _ -> 0
    | (_, hd::tl) -> hd + sum_array (c-1) tl
in sum_array 4 [1;2;3;4;5;6]        ;;

Answer 2

The error message appears at the ;; because a let without in is only permissible as the outermost statement. To make your expression evaluate, you need to add in sum_array c:

fun c -> let int_array = [| 1 ; 2 ; 3 ; 4 ; 5 |] in
    let rec sum_array c =
        if c < 0 then 0
        else int_array.(c) + sum_array (c - 1)
    in sum_array c;;
- : int -> int = <fun>

This can be simplified by dropping the abstraction on c:

let int_array = [| 1 ; 2 ; 3 ; 4 ; 5 |] in
    let rec sum_array c =
        if c < 0 then 0
        else int_array.(c) + sum_array (c - 1)
    in sum_array;;

In both cases, sum_array is not bound on the top level. Either you bind it with another let sum_array =..., you pull the binding of int_array inside of the definition of sum_array(like @Jeffrey Scofield proposed), or you bind int_array on the top level before you define sum_array:

let int_array = [| 1 ; 2 ; 3 ; 4 ; 5 |]

let rec sum_array c =
        if c < 0 then 0
        else int_array.(c) + sum_array (c - 1)
;;

Answer 3

In some sense your problem is that you're adding fun c -> ... in the wrong place.

Say you had a function like this:

let f count =
    (count + 72 - 1) / 72

If you imagine that the hard-coded value 72 is something you would like to pre-calculate, you can rewrite the function as follows:

let f =
    let line_length = 72 in
    fun count -> (count + line_length - 1) / line_length

Your code is placing the array before the body of the function, but it should be inside it, between the let and a new inner function definition.

Your case is particularly tricky because your function is recursive. So you can't switch over to the fun c -> ... form. Instead you can retain the original let-based definition locally. For the contrived example, it would look like this:

let f =
    let line_length = 72 in
    let inner_f count =
        (count + line_length - 1) / line_length
    in
    inner_f

(As a side comment, your code sums the first c+1 elements of the array, not the first c elements.)