Trying to check for a key,value pair in a list of lists in Ocaml

Question

I am trying to see if a name exists in a list of lists, and if it does i will return the value associated with the name. I am binding values(strings, ints, bools) to a string and storing them in an environment which is represented by each list in the overall list.

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

i know that this is invalid, but this is what i have come up with so far. any help would be awesome. also, I am trying to read the whole top row first, then the next row and so on.

Answer 1

The iteration logic is good, but I don't understand the need for two functions? In the List module of OCaml, there are functions that could help you. For example, there are some functions in the OCaml List module that might help you, for example, since OCaml 4.10.0 you can use find_map:

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

Or we use find_opt which is less direct but has the merit of being around longer (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

(Of course, you can manually deconstruct your resulted option in order to not depend on the module Option, if you use an older OCaml's version).

On the other hand, if you really want to build the manual recursion, it is also, obviously possible, by following a scheme close to the one you have proposed:

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

You can also use when (guards) for having the condition at the pattern level:

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

But if you look at the code, you may be annoyed that you have to repeat through the recursion the key you are looking for... even though it is constant at the execution of the function? So we can use an auxiliary function, internal to our function, to avoid having to pass the key each time.

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 *)

EDIT:

I had missed the point that you have to find a key in a list of lists and now, I understand why did you need two function. Here is something pretty close of your suggestion.

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 

I think the only mistake your program made was that it didn't check that a value had been found in the list. So it iterate through the list, even the key was found. You just has to treat the case when you find something (or not). Like in my code.

Second edit Using the form f = function ... can be unclear so here is a version without shortcuts:

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