OCaml, Understanding error message

1
votes
let rec smallest l =
    match l with
    | [] -> raise Not_found
    | [a] -> (fun x -> if x > 0 then x else raise Not_found) a
    | h::b::t -> 
        if h > b then smallest h::t
        else smallest b::t`

This function is suppose to take an int list and return the smallest int if there is a positive integer in the list or raise the exception Not_found if there is no positive integer in the list.

When I try this out, I get the following error with smallest h::t found in the third matching pattern underlined:

Error: This expression has type 'a list but an expression was expected of type int

Can someone explain to me what I am doing wrong?

2
exceptiontypeserror-handlingpattern-matchingocaml

2 Answers

3
votes

smallest h::t is equivalent to (smallest h)::t. That is, it applies smallest to the argument h and then prepends it to the list t. This makes OCaml complain that you're producing a list when you're supposed to produce a single integer. What you want is smallest (h::t).

This function is suppose to take an int list and return the smallest int if there is a positive integer in the list or raise the exception Not_found if there is no positive integer in the list.

Even with the above fix, that's not what the function will do. Instead it will find the largest element in the list if there is at least one positive element. That's because you always pick the larger element in your if. If you switch it around, so that it always takes the smaller element, it will fail whenever there's at least one non-positive element in the list.

One way to fix that would be to only pick an element as the new head of the list if it is positive and smaller than the current head or it is positive and the current head is negative.

However another, perhaps cleaner, way to get a function matching your description would be to first define a function that takes the smallest element out of any non-empty list (ignoring whether it's positive or not) and then defining another function that calls the first function after filtering the list to only include the positive elements. Like this:

let smallest_positive xs = smallest (List.filter (fun x -> x > 0) xs)

PS: This isn't related to your problem, but the following expression looks quite strange:

(fun x -> if x > 0 then x else raise Not_found) a

There is usually very little reason in OCaml to create a function only to immediately apply it - that's just a more complicated way to write a let expression and in this case you don't even need the let. In other words, the above is equivalent to:

let x = a in
if x > 0 then x else raise Not_found

Which in turn is equivalent to:

if a > 0 then a else raise Not_found
0
votes

After some more thought, I was able to answer my own question.

let rec smallest l =
    match l with
    | [] -> raise Not_found
    | [a] -> (fun x -> if x > 0 then x else raise Not_found) a
    | h::b::t -> 
        if h < b && h > 0
            then smallest (h::t)
            else smallest (b::t)`