如何在OCaml中返回for循环的索引？

Question

let find_free_next heap start = 
  for i = start to ((Array.length heap)-1) do
     match heap.(i) with 
     Hdr (Free (h), g)  ->
        i
  done

一旦找到匹配,我怎样才能将循环的索引作为整数返回？

Answer 1

如果您想坚持命令式样式,可以使用异常退出循环:

exception Found of int

let find_free_next heap start = 
  try
    for i = start to Array.length heap - 1 do
       match heap.(i) with 
       | Hdr (Free (h), g)  -> raise (Found i)
       | _ -> () (* If it is not what you are seeking *)
    done;
    raise Not_found   
  with
  | Found n -> n

但一般来说,正如ppl已经写过的那样,在OCaml中更喜欢功能风格:

let find_free_next heap start =
  let len = Array.length heap in
  let rec find i =
    if i >= len then None
    else 
      match heap.(i) with
      | Hdr (Free h, g) -> Some i
      | _ -> find (i+1)
  in
  find start

在这个例子中,两个版本之间没有太大的区别,但是必须谨慎使用异常来退出循环/递归.你可以很容易地用它们引入控制流错误,它们有时很难调试.

顺便说一句,你可以使用Array.unsafe_get heap i来加速你的数组访问,因为你可以确定我总是在上面例子的数组的有效范围内.(哦,我们需要开始> = 0另外检查.)

Answer 2

Asumu Takikawa是对的,forOCaml中的循环不会返回结果.在惯用的OCaml中,您应该使用递归.理想情况下,会有一个像List.find数组一样的标准函数.有一个函数BatArray.findi中包含OCaml的电池,做你仿佛想.

Answer 3

更简单,更高效(根本没有分配):

let rec find_free_next heap start =
  if start = Array.length heap then raise Not_found;
  match heap.(i) with
  | Hdr (Free h, g) -> i
  | _ -> find_free_start heap (i+1)

或者,以命令式:

let exit = Exit
let find_free_next heap start =
  let pos = ref (-1) in
  try
    for i = start to Array.length heap - 1 do
      match heap.(i) with
      | Hdr (Free h, g) -> pos := i; raise exit
      | _ -> ()
    done;
    raise Not_found
  with Exit -> !pos

(注意raise exit不分配只因为预先计算的例外).