Need to match a tuple from a list in OCaml

Question

I need to create a function rec assoc (d,k,l) that takes a triple (d,k,l) where l is a list of key-value pairs [(k1,v1);(k2,v2);...] and finds the first ki that equals k. If such a ki is found, then vi is returned. Otherwise, the default value d is returned. it needs to be tail recursive

here is the function that I made:

let rec assoc (d,k,l)  = match l with
  |[]-> d
  |(a,b)::t ->  
  if (a==k) then b
  else assoc(d,k,t)
;;

my logic here is take the head of the list l and if the first part of the tuple in the list matches k, I return the second part of the tuple. If not then i want to call the function again on the tail of the list so it checks each element. If the entire list is traversed down to the empty list without finding a match, I want to return d. For some reason, it always returns d no matter what list I give it. What could be the reason for that.

heres some sample output it should give:

# assoc (-1,"jeff",[("sorin",85);("jeff",23);("moose",44)]);;
- : int = 23
# assoc (-1,"bob",[("sorin",85);("jeff",23);("moose",44)("margaret",99)]);;
- : int = -1

mine returns -1 for both

Normally, an OCaml programmer would not pass all the arguments in a tuple like you have. As in, let rec assoc d k = function. — nlucaroni

Jeffrey Scofield Jeffrey Scofield · Accepted Answer · 2015-01-25T05:51:31

Don't use == for comparisons. It's a special-purpose "physical equality". Use = for comparisons.

(Other than this your code looks excellent.)

Comparison operators are defined in the Pervasives module. Here are the descriptions of = (the normal equality comparison) and == (the physical equality comparison):

e1 = e2 tests for structural equality of e1 and e2. Mutable structures (e.g. references and arrays) are equal if and only if their current contents are structurally equal, even if the two mutable objects are not the same physical object. Equality between functional values raises Invalid_argument. Equality between cyclic data structures may not terminate.

e1 == e2 tests for physical equality of e1 and e2. On mutable types such as references, arrays, byte sequences, records with mutable fields and objects with mutable instance variables, e1 == e2 is true if and only if physical modification of e1 also affects e2. On non-mutable types, the behavior of ( == ) is implementation-dependent; however, it is guaranteed that e1 == e2 implies compare e1 e2 = 0.

Generally speaking, you shouldn't use == in your code unless you want the specific (weak) equality test described here. Or, just don't use it :-)

Need to match a tuple from a list in OCaml

1 Answers