OCaml function to return a list of tuples whose last element matches a predicate

Question

I am trying to write a function in OCaml that takes a predicate, a list of tuples, and the empty list and returns a list of tuples in that original list whose last member satisfies the predicate.

What I have so far is:

let rec find_tuples p l l1 = 
match l with
| [] -> []
| (n,s,f) :: t -> if p f then ((n,s,f) :: l1) else find_tuples p t l1

But this only returns the first tuple matching the predicate. What do I change to get it to return all the tuples that match?

Answer 1

You need to keep going down your list even when you've found your first matching tuple. In fact, we can agree you should traverse the whole list until you get to []:

let rec find_tuples p l l1 =
match l with
| [] -> failwith "we're here after a traversal or l1 is empty"
| ( (_,_,f) as e) :: t ->
  if p f
  then find_tuples p t (e::l1)
  else find_tuples p t l1

Of course, that failwith I left you is not the right answer. We need it to be [] if no traversal was done and l1 if there was a recursive call. Wait, l1 works in both cases!
So that failwith should be replaced by l1.

In those cases, l1 is usually called an accumulator variable.

Answer 2

Think about the case after then. Why would you be so sure you only need to add one extra tuple to l1 at that point. Maybe there are some more in the tail.

Answer 3

let rec find_tuples p l l1 = 
match l with
| [] -> []
| (n,s,f) :: t -> if p f then find_tuples p t ((n,s,f) :: l1) else find_tuples p t l1

When the condition is true, don't forget to recall the function on the tail of l.

Edit : an another solution is to use List.filter

let find_tuples p l = List.filter (fun (n,s,f) -> p f) l