Minimum of a list

Hello everyone
This does not work I do not know why

let min_list2 lst =
let a = List.nth lst in
let b =List.hd lst in
List.fold_left min a b;;
let c=min_list2 [1;2];;
print_int c;;

the error was

Error: This expression has type 'a but an expression was expected of type
(int → 'a) list
The type variable 'a occurs inside (int → 'a) list

Thank you for your help

1 Like

Hi, and welcome :slight_smile:

It would help if you:

  • format your code so it easier to read (at least with spaces around the =s, but ideally also with each assignment on a separate line
  • state what you expect to happen
  • report what error messages or unexpected result leads you to conclude it’s not working

This will help us help you :slight_smile:

As you write up the report of the error messages, spend some time thinking about what the messages say, and see if you can figure out how it applies to your code. It might help you figure out what is going wrong. But you can at least explain what you think is happening and which parts you don’t understand.


Thanks for cleaning up your question some, @otaku_for_ever.

If I enter your declarations at the top-level one at a time, I get an error at the first one:

# let min_list2 lst =
    let a = List.nth lst in
    let b = List.hd lst in
    List.fold_left min a b;;
Line 4, characters 25-26:
Error: This expression has type 'a but an expression was expected of type
         (int -> 'a) list
       The type variable 'a occurs inside (int -> 'a) list

Note that this provides critical information that you’ve omitted in your question. First, it tells us which declaration is having trouble (the first one). Second, it tells us which line and character it’s having trouble with (namely line 4, characters 25-26): this is the b in List.fold_left min a b;;.

What problem is it encountering? Well, according to the error message, it’s expecting the b to have type (int -> 'a) list, that is, to be a list of functions from int to values of type 'a (whatever type 'a turns out to be). But instead it’s finding b to have just type 'a. Why?

Study the type of List.fold_left:

# List.fold_left;;
- : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

And then, thinking algebraically, try to determine the types of the values you are applying this function to. To do that, try evaluating the sub-expressions in your code, using different dummy data in place of lst, and see if they have the types and values that you expect. E.g.,

# List.nth;;
- : 'a list -> int -> 'a = <fun>
# let a = List.nth [1;2;3];;
val a : int -> int = <fun>
# List.hd;;
- : 'a list -> 'a = <fun>
# let b = List.hd [1;2;3];;
val b : int = 1

Are you expecting a to be a function? It’s ending up as a function because you’re partially applying List.nth. Is that what you intended?

Here’s a correct implementation of a function to find the minimum value in a list:

# let min_list lst = List.fold_left min (List.hd lst) ( lst);;
val min_list : 'a list -> 'a = <fun>

Compare it with yours, and see if you can figure out where things are going wonky.

Please feel free to add followup questions, and, once you’ve figured out why your code isn’t working, it would be great if you’d post here explaining what you’ve figured out! :slight_smile:


Thank you the problem was In List.nth lst

let a = List.nth [2;1];;

val a : int → int =

which needs an other int argument

a 1;;

  • : int = 1
1 Like
BatList.min l


Hey it does not work

open BatList
print_int (BatList.min [ 10 ; 5 ; 7 ; 8 ; 12 ]);;

# #require "batteries";;
# BatList.min [ 10 ; 5 ; 7 ; 8 ; 12 ];;
- : int = 5
1 Like

I am rather disappointed that BatList.min is 'a list -> 'a with an exception and not the more obvious 'a list -> 'a option and doesn’t support adding a comparator so comparison is always using polymorphic < & >.

Base has List.min_elt : 'a t -> compare:('a -> 'a -> int) -> 'a option which is a much more sensible signature, since it signals that there is a fairly obvious case where there is no minimum as well as allowing a custom comparator like

Yes, batteries usually exposes rather simple interfaces.
We also have this, in case you are interested:

   val BatList.min_max ?cmp:('a -> 'a -> int) -> 'a list -> 'a * 'a             

Alternative implementations are also provided by the Exceptionless module :
But min is not provided in this module unfortunately. I guess it could be worth to add it ?

1 Like

Is there something I’m missing here? Why would I need it to throw or return an 'a option when the impl could be List.fold_left (min:int -> _) max_int ? If I encountered an empty list I’ll just get back max_int which is concrete and a valid value to test against… right?

Oh it’s meant to be polymorphic

It could still be polymorphic and avoid evaluating to an option by throwing an exception, but where do you get the init argument to supply to your fold if the list is empty?

For some reason I misread your question. Sorry!

The function being partial (whether by raising an exception or returning an option) is orthogonal to it being polymorphic.

I’d argue that supplying a default value as a fallback in case of an empty list is less general, and less generally useful, than representing the partial function. This is because, given a partial function that fails on the empty list you can trivially transform the failure into supplying your desired default value when appropriate, but it’s often the case that there isn’t a suitable default value when the list is empty, and instead you just need to take a different course of action in the code. In those cases, it would be cumbersome to determine whether you’d actually obtained the minimum value of the list or just gotten your default back. Whenever your function returned the default value you supplied and you wanted to be sure you’d actually gotten a value from the list, you’d have to check whether the list was empty, which could mean traversing the entire list twice.

Sure you can implement it like this but your choice of max_int is essentially arbitrary. If I ask the max function for the maximum of an int list and get 4611686018427387903 which is very much a correct value for a maximum I would assume this is the maximum. One could declare that the function returns max_int when there is no maximum, but then every caller has to know this frankly rather unusual behaviour, or risk being wrong, e.g. determining suddenly a giant maximum of an empty list.

Worse yet, you have no way of determining whether the list was empty or whether the list contained max_int so to be correct you’d have to traverse the list again to see if List.mem is true for max_int. Forget that and your program is subtly wrong now.

In general I feel it is rather dangerous to have valid-looking sentinel values, like in C where it is pretty common for functions to return -1, which is still a valid input to other functions that might want to consume integers. Especially since this is rarely if ever needed in OCaml where one can often wrap the return value in an ADT of some sort to prevent the sentinel to be mistaken for the real value. Such an trivial ADT could be 'a option, for more complex return values it can make sense to use more complicated ADTs or return polymorphic variants.


pull requests and new contributors are always welcome!

1 Like

Sure, why not. This shouldn’t take much time, I’ll do it soonish