ocaml constructing module (super beginner)

Question

I'm new to module programming using ocaml. I made a dictionary module such as

module type DICT =
  sig
    type key
    type 'a dict
    ...
    val lookup : 'a dict -> key -> 'a option
    ...
  end


module DictList : DICT with type key = string =
  struct
    type key = string
    type 'a dict = (key * 'a) list

    ...
    **let rec lookup d k =
        match d with
        | [] as dict -> None
        | (key, value)::tl as dict -> if( key = k ) then (key, value)
                                      else lookup tl k**
    ...
  end

lookup d k searches the key k in the dictionary d. If the key is found, it returns the item, otherwise, it returns None. However, I got a error which says

Error: This expression has type 'a * 'b but an expression was expected of type 'c list

at lookup function. What is the problem and how can I fix it?

avysk avysk · Accepted Answer · 2017-03-05T09:49:03

You have two problems here (and none of them give the error you claim you're getting).

1st problem: your lookup function doesn't have consistent type

One branch returns None so the type should be 'a option. Another branch returns (key, value) so the type should be 'a * 'b.

How to fix? Change (key, value) to Some (key, value).

Unfortunately, there is also

2nd problem: your lookup function does not correspond to its definition in module type.

If you look at your definition of DICT, you'll see that lookup is 'a dict -> key -> 'a option.

Now, in your definition of DictList module key is string, so lookup should be 'a dict -> string -> 'a option, where a is the type of values you are storing in your dictionary. It means that you cannot return Some (key, value), as then lookup will have signature 'a dict -> string -> (string * 'a) option. Return just Some value.

So, your definition should look like

module DictList : DICT with type key = string =
    struct
    type key = string
    type 'a dict = (key * 'a) list
    let rec lookup d k =
        match d with
        | [] -> None
        | (key, value)::tl -> if (key = k) then Some value else lookup tl k
    end

ocaml constructing module (super beginner)

2 Answers