在OCaml中查找列表中的项目并返回其索引

Question

我写了下面这个函数，用于在给定的列表 "lst" 中查找给定的项 "x"，如果找到则返回其索引，否则返回错误：

exception Failure of string

let rec func x lst c = match lst with
    | [] -> raise(Failure "Not Found")
    | hd::tl -> if (hd=x) then c else func x tl (c+1)


let find x lst = func x lst 0

这个函数完全可以工作，我只是想知道它的内存消耗是多少？也就是说，内存消耗是否取决于列表的长度？还是O（1）？

如果不是O（1），请问有人能告诉我该怎么做才能使其达到O（1）吗？

谢谢。

- Kyle

---

顺便提一下，OCaml有一个专门用于此类情况的异常构造器Not_found。 - gsg

Answer 1

你的函数因为是尾递归的，所以它的空间复杂度是常数级别（O(1)）。你可以在OCaml.org上了解有关尾递归的知识，点击这里。

更新

以下是一个非尾递归的解决方案：

exception Failure of string

let rec find x lst =
    match lst with
    | [] -> raise (Failure "Not Found")
    | h :: t -> if x = h then 0 else 1 + find x t

(我刚刚注意到PatJ已经解释过了，对不起：-）

通常情况下，非尾递归的解决方案更加简洁优雅。这很遗憾，但有时候世界就是这样。

- Jeffrey Scofield

---

谢谢 :) 只是出于好奇，一个执行与我编写的函数相同任务但消耗O(n)空间的函数会是什么样子？没有必要回答，但实际上我想知道，因为即使在阅读了您发送给我的链接后，我也想不到如何做到这一点。 - Kyle

如果函数的递归调用不是在返回之前执行的“最后一个操作”，那么它将是O(n)。例如，如果您没有计数器变量c，而是使用if (hd=x) then 0 else 1+(find x tl)，则每个递归调用都会向堆栈添加一些变量。 - PatJ

谢谢你们两个！有趣的是，昨晚我可能写了你们两个建议的完全相同的函数，但不知何故它就是不起作用。OCamlWin有时候就是这么多问题。 - Kyle