How to traverse a list without losing elements

Question

so i have a function:

let rec add_rules start rules prod =
  match rules with
  | [] -> prod
  | nonterm::lst -> 
      if fst nonterm = start then 
        add_rules start (List.remove_assoc (fst nonterm) rules) (nonterm::prod)
      else if check_sym (fst nonterm) prod then 
        add_rules start (List.remove_assoc (fst nonterm) rules) (nonterm::prod)
      else 
        add_rules start lst prod

and it takes an element called start, a list of pairs called rules where (x,[y]) and x is an element and y is a list, and an empty list prod.

without getting too much into detail about the specifics of this function, i basically want it to traverse the list of pairs (rules) and add certain elements to the empty list prod.

problem: in the first two if/else if statements, my code successfully removes the pair corresponding to (fst nonterm) and passes in the entire original list (minus (fst nonterm)) back to the recursive function. however, in the last else statement, i recursively traverse through the list by calling the tail of the original rules list, passing that in to the function, and therefore ending up unable to ever access those heads ever again.

is there any way i can avoid this? or is there any way i can traverse the list without getting rid of the head each time?

thank you in advance!!!

Answer 1

Yes, you need to introduce an extra parameter for that, as @coredump has suggested. So you will end up with an accumulator prod that will contain the result, that you're building, a queue of rules to be processed that reduces in size with each step of recursion (currently named rules in your version) and the rules that will contain all the rules (modulo those that you explicitly delete).