List.assoc using List.find

Question

I want to implement the List.assoc function using List.find, this is what I have tried:

let rec assoc lista x = match lista with
  | [] -> raise Not_found
  | (a,b)::l -> try (List.find (fun x -> a = x) lista)
            b
        with Not_found -> assoc l x;;

but it gives me this error:

This expression has type ('a * 'b) list but an expression was expected of type 'a list The type variable 'a occurs inside 'a * 'b

I don't know if this is something expected to happen or if I'm doing something wrong. I also tried this as an alternative:

let assoc lista x = match lista with
    | [] -> raise Not_found
    | (a,b)::l -> match List.split lista with 
        | (l1,l2) -> let ind = find l1 (List.find (fun s -> compare a x = 0))
        in List.nth l2 ind;;

where find is a function that returns the index of the element requested:

let rec find lst x =
    match lst with
    | [] -> raise Not_found
    | h :: t -> if x = h then 0 else 1 + find t x;;

with this code the problem is that the function should have type ('a * 'b) list -> 'a -> 'b, but instead it's (('a list -> 'a) * 'b) list -> ('a list -> 'a) -> 'b, so when I try

assoc [(1,a);(2,b);(3,c)] 2;; 

I get:

This expression has type int but an expression was expected of type 'a list -> 'a (refering to the first element of the pair inside the list)

I don't understand why I don't get the expected function type.

Answer 1

First off, a quick suggestion on making your assoc function more idiomatic OCaml: have it take the list as the last argument. This is very common in the standard library's List module.

Secondly, why are you attempting to implement this in terms of find? It's much easier without.

let rec assoc x lista =
  match lista with
  | [] -> raise Not_found
  | (a, b) :: xs -> if a = x then b else assoc x xs

Something like this is simpler and substantially more efficient with the way lists work in OCaml.

Having the list as the last argument, even means we can write this more tersely.

let rec assoc x =
  function
  | [] -> raise Not_found
  | (a, b) :: xs -> if a = x then b else assoc x xs

As to your question, OCaml infers the types of functions from how they're used.

find l1 (List.find (fun s -> compare a x = 0))

We know l1 is an int list. So we must be trying to find it in an int list list. So:

List.find (fun s -> compare a x = 0)

Must return an int list list. It's a mess. Try rethinking your function and you'll end up with something much easier to reason about.