list - 如何编写一个函数来获取列表中最小 int 的位置？

Question

原型(prototype)必须是:

listMinPos(lst)

我可以使用两个参数(列表和索引)编写相同的内容，但我什至无法想象仅使用列表参数如何实现。

必须满足以下条件:

只有 1 个参数(列表)。

没有外部库。

函数应该是递归的(函数内部没有'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)

(正如 Pascal Cuoq 注意到的，还有一个 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