OCaml中

Question

使用倍清单的要求，对价值的回报指数我写了指数的递归版本如下

let index list value = 
    let rec counter num = function 
    | [] -> -1 
    | h::t -> 
     if h == value 
      then num 
     else (counter (num + 1)) t 
    in counter 0 list;; 

它的工作原理，但随后我们的教授说，我们应该用一个尾递归版本为了不在服务器上超时，所以我使用fold编写了一个新的索引函数，但我似乎无法弄清楚为什么如果它找不到该元素，它将返回一个大于列表长度的数字，甚至尽管我希望它返回-1。

let index2 list value = fold (fun i v -> 
    if i > (length list) then -1 
    else if v == value then i       
    else i+1) 0 list;; 

这里是我的版本倍，以及：

let rec fold f a l = match l with 
    [] -> a 
    | (h::t) -> fold f (f a h) t;; 

Answer 1

你的折叠功能对列表中的每个元素调用一次。所以你永远不会看到i的值大于(length list - 1)。

作为一个方面的评论，它是相当低效（二次复杂度），以保持计算列表的长度。最好在开始时计算一次。

作为另一方的评论，您几乎从不想使用==运算符。改为使用=运算符。

Answer 2

编辑

为什么你重新定义fold而不是使用List.fold_left？

您的索引的第一个版本已经是尾递归，但可以通过提高它的风格：使用

• option类型而不是返回-1，如果没有找到;
• 直接调用索引而不是计数函数;
• 使用=（结构）比较器而不是==（物理）;
• 在模式匹配中使用警卫而不是if语句。

所以

let index list value = 
    let rec index' list value i = match list with 
    | [] -> None 
    | h :: _ when h = value -> Some i 
    | _ :: t -> index' t value (succ i) 
    in index' list value 0 

而且前面已经说了，index2不工作，因为你永远也做不到的元素，其索引大于列表的长度更大，所以你只要有更换i > (length list)i = (length list) - 1使其工作。

但index2比index效率较低，因为index一旦元素被发现，而index2总是每次评估列表中的每个元素和列表的长度比较计数器停止。