尝试在 Ocaml 中的列表列表中检查键值对

Question

我试图查看列表列表中是否存在某个名称，如果存在，我将返回与该名称关联的值。我将值（字符串、整数、布尔值）绑定到字符串并将它们存储在由整个列表中的每个列表表示的环境中。

let rec lookup key envlist = 
  match envlist with
  | [] -> None
  | hd::tl -> lookupaux key hd
in

let rec lookupaux name curenvlist = 
  match curenvlist with
  | [] -> None
  | (n,v)::t -> 
    if n = name then Some v 
    else lookupaux name t

我知道这是无效的，但这是我到目前为止所想到的。任何帮助都是极好的。另外，我尝试先阅读整个顶行，然后阅读下一行，依此类推。

Answer 1

迭代逻辑很好，但我不明白需要两个函数吗？ 在OCaml的List模块中，有一些功能可以帮助您。例如，OCaml List 模块中的一些函数可能会对您有所帮助，因为

OCaml 4.10.0

您可以使用

find_map

:

let lookup searched_key envlist = 
  List.find_map (fun (key, value) ->
     if key = searched_key then Some value else None
  ) envlist

或者我们使用

find_opt

，虽然不那么直接，但优点是停留时间更长（

OCaml 4.05

）：

let lookup searched_key envlist = 
  (* First, get an option *)
  List.find_opt (fun (key, _) -> key = searched_key) envlist
  (* Now, using Option, you can fetch only the value 
     https://ocaml.org/api/Option.html#VALmap (since 4.08) *)
  |> Option.map snd

（当然，如果您使用旧的 OCaml 版本，您可以手动解构结果选项，以便不依赖于模块选项）。

另一方面，如果您确实想构建手动递归，显然也可以通过遵循与您提出的方案接近的方案来实现：

let rec lookup searched_key envlist = 
   match envlist with 
   | [] -> None
   | (key, value) :: tail ->
       if key = searched_key then Some value 
       else lookup searched_key tail

您还可以使用

when

（防护）在模式级别设置条件：

let rec lookup searched_key envlist = 
   match envlist with 
   | [] -> None
   | (key, value) :: _  when key = searched_key -> Some value
   | _ :: tail -> lookup searched_key tail

但是如果你看一下代码，你可能会很恼火，因为你必须通过递归重复你正在寻找的键......即使它在函数执行时是恒定的？因此，我们可以使用函数内部的辅助函数，以避免每次都必须传递密钥。

let lookup searched_key = 
   let rec aux = function
   | [] -> None
   | (key, value) :: _  when key = searched_key -> Some value
   | _ :: tail -> aux y tail
   in aux (* [aux] will return a function that take a list *)

编辑：

我错过了一点，你必须在列表列表中找到一个键，现在，我明白为什么你需要两个函数。 这是与您的建议非常接近的内容。

let lookup searched_key = 
   let rec find_value = function
     | [] -> None
     | (key, value) :: _  when key = searched_key -> Some value
     | _ :: tail -> find_value y tail
   in 
   let rec aux = function 
     | [] -> None 
     | x :: xs -> begin 
        (* begin/end or parenthesis are mandatory for 
           nested pattern matching *)
        match find_value x with 
        | None -> (* if we don't find the key, we continue on the tail*)
           aux xs
        | Some x -> Some x
     end
     in aux 

我认为你的程序犯的唯一错误是它没有检查列表中是否找到了值。所以它遍历列表，甚至找到了键。当你发现某些东西（或没有）时，你只需要处理这个案件。就像我的代码一样。

第二次编辑 使用

f = function ...

的形式可能会不清楚，所以这里是一个没有快捷方式的版本：

let lookup searched_key envlist = 
   let rec find_value list = 
     match list with
     | [] -> None
     | (key, value) :: _  when key = searched_key -> Some value
     | _ :: tail -> find_value y tail
   in 
   let rec aux envlist = 
     match envlist with
     | [] -> None 
     | x :: xs -> begin 
        (* begin/end or parenthesis are mandatory for 
           nested pattern matching *)
        match find_value x with 
        | None -> (* if we don't find the key, we continue on the tail*)
           aux xs
        | Some x -> Some x
     end
     in aux envlist