Как написать функцию, чтобы получить позицию наименьшего целого в списке?

Question

Прототип должен быть:

listMinPos(lst)

Я могу написать то же самое, используя два аргумента (список и индекс), но не могу даже представить, как это возможно, используя только аргумент списка.

Должно быть следующее:

1. только 1 аргумент (список).
2. нет внешних библиотек.
3. функция должна быть рекурсивной (без 'let' внутри функции)

Answer 1

У меня есть решение, которое немного обманывает: я возвращаю позицию наименьшего элемента, , но не только . Также возвращается значение наименьшего элемента.

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)

(Как заметил Паскаль Куок, все еще остается один let p, v = .. in ..; его можно заменить на match .. with p, v -> ... См. Комментарии).

Другое решение, которое ослабляет ваше второе ограничение (без внешней библиотеки):

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

Это неэффективно, но я не думаю, что вы можете добиться большего успеха, не передав больше информации.

Редактировать

Я не понял, что это домашнее задание. Существует ли политика против предоставления полного решения домашних заданий?

В любом случае, в этом случае я полагаю, что список ограничений, которые вы дали, не является, как я предполагал, ограничением, способствующим творчеству, и я полагаю, что вы можете их нарушить, если он даст лучшие решения.

Поэтому я предлагаю, используя локальные 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)

И хвост-рекурсивная версия:

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