Styjun

I'm doing a recursive propositional calculator but I have a problem using a dictionary, I'm using pair list like a dictionary and my own function lookup to search for a value in the dictionary.

Now lookup returns an alpha type, but in my main function (calcPrep) the match must return a bool, I don't see a problem whit the syntaxis, at the end that alpha type can be a bool...

If I change

| '('::variable::')'::_ -> lookup (variable, dictionary)

to

| '('::variable::')'::_ -> true

the match works, but obviously, I didn't get the value of the variable.

I'm thinking of use maps as a dictionary instead pair list, but it's more complex to me...

Here is my code until now

let rec lookup x l = 
 match l with
 | [] -> raise Not_found
 | (key, value)::rest -> 
 if key = x then 
 value
 else 
 lookup x rest

let rec calcPrep charList dictionary=
 let n = List.length charList in
 match charList with
 | '('::variable::')'::_ -> lookup (variable, dictionary)
 | '('::'!'::_ -> not (calcPrep(sublist 2 (n-1) charList) dictionary)
 | _ ->
 let pos = getPositionOperator charList 0 0 in
 let operator = (List.nth charList pos) in 
 match operator with
 | '&' -> (calcPrep (sublist 1 (pos - 1) charList) dictionary) && (calcPrep (sublist (pos + 1) (n - 2) charList) dictionary)
 | '|' -> (calcPrep (sublist 1 (pos - 1) charList) dictionary) && (calcPrep (sublist (pos + 1) (n - 2) charList) dictionary)
 | _ -> failwith ("Incorrect operator: " ^ String.make 1 (List.nth charList (pos - 1)))

First of all, alpha, aka 'a, doesn't mean "anything", it is a type variable that should be considered in a context. For example, in the type of a function,

val find: ('k,'a) list -> 'k -> 'a

we have two type variables 'k and 'a, with the 'k denoting the type of keys, and 'a denoting the type of values. Therefore, when you apply this function to some list, e.g., find [1, "one"; 2, "two"] the 'k variable will be instantiated to int and 'a to string, and the type of this expression will be int -> string.

Second, a function that checks whether a particular key or element is present in a container is usually called mem. It could be easily implemented via the find function, that search for the element, e.g.,

let mem ls k = try ignore (find ls k); false with Not_found -> true

This function will have type ('k,'a) list -> 'k -> bool.

In the modern OCaml, it is prefered to use a more explicit 'a option type as the return type of the find function, instead of throwing an exception, since the former appears in the type of the function and is harder to miss. So if you have a find function returning 'a option, then the implementation will look like this

let mem ls ks = match find ls k with None -> false | Some _ -> true