How to write a function to get the position of the smallest int in a list?

Question

The prototype must be:

listMinPos(lst)

I'm able to write the same using two arguments, (list and index), but am not able to even think how it can be possible using only the list argument.

The following must hold:

1. only 1 argument (the list).
2. no external libraries.
3. function should be recursive (no 'let' inside the function)

Answer 1

I have a solution that cheats slightly : I return the position of the smallest element, but not only. The value of the smallest element is also returned.

let rec min_pos = function
  | [] -> invalid_arg "min_pos"
  | [x] -> (0, x)
  | hd::tl ->
    let p, v = min_pos tl in
    if hd < v then (0, hd) else (p + 1, v)

(As Pascal Cuoq noticed, there is still one let p, v = .. in .. remaining; it can be replaced by match .. with p, v -> ... See comments).

Another solution that relax your second constraint (no external library) :

let rec min_pos = function
  | [] -> invalid_arg "min_pos"
  | [x] -> 0
  | hd::tl ->
    let p = min_pos tl in
    if hd < List.nth tl p then 0 else p + 1

It's inefficient but I don't think you can do much better without passing more information.

Edit

I didn't understand this was a homework. Is there a policy against giving complete solution to homework questions ?

Anyway, in this case I suppose that the list of restriction you gave is not, as I supposed, a creativity-forcing constraint, and I suppose that you can break them if it gives better solutions.

I therefore propose, using local let :

let min_pos li =
  let rec min_pos = function
    | [] -> invalid_arg "min_pos"
    | [x] -> (0, x)
    | hd::tl ->
      let p, v = min_pos tl in
      if hd < v then (0, hd) else (p + 1, v)
  in fst (min_pos li)

And a tail-recursive version :

let min_pos li =
  let rec min_pos mini mpos cur_pos = function
    | [] -> mpos
    | hd::tl ->
      if hd < mini
      then min_pos hd cur_pos (cur_pos + 1) tl
      else min_pos mini mpos (cur_pos + 1) tl
  in match li with
     | [] -> invalid_arg "min_pos"
     | hd::tl -> min_pos hd 0 1 tl