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!!!

Your question is unclear. First, by definition, "the entire original list minus fst nonterm" does not contain nonterm, i.e. the head of the list: even in the first two cases you pass (at best, assuming there's no duplicate in rules) the tail of the list to your recursive call. Second, traversing a list basically means taking the tail of the list until you end up with the empty list. As suggested, it is possible to add an extra parameter to add_rules that will remain constant through the successive calls, but you should explain a bit more the context in which you want to use add_rules — Virgile
Why would you want to access the heads anyway? The purpose of recursive functions is to break a big problem into smaller ones. Also, I'm pretty sure that using List.fold would help you make your code easier to read and write. — Richard-Degenne
(List.remove_assoc (fst nonterm) rules) is the same as lst so in all 3 cases you pass the same to the recursion. — Goswin von Brederlow

ivg ivg · Accepted Answer · 2018-10-05T12:33:07

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).

How to traverse a list without losing elements

1 Answers