list - 在列表中查找项目并返回其索引 - 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)，有人可以让我知道我该怎么做才能做到这一点吗？

谢谢

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 已经解释过了，抱歉 :-)

通常，非尾递归解决方案更加简洁和优雅。这太糟糕了，但世界有时就是这样。