Packing consecutive repetitions in a list into sublists →
In one of our [earlier posts] we saw how to eliminate consecutive repetitions in a list. Let’s refresh our memory and take a look at the compress
function we saw earlier:
This is a straight forward recursive function. Let’s first rewrite it using auxiliary function.
I think it is pretty straight forward - if we see repetition (x1 = x2)
we ignore the element and call the auxiliary function on the remaining part of the list. (Note that we do not eliminate x2
as we want to retain a copy of each repeating element).
Today, we shall not eliminate, but collect the consecutive repeating elements into sublists. For example, if we have the list [1;1;1;2;2;3;4;5;5;6;1]
we want to make it into this list [[1; 1; 1];[2; 2];[3];[4];[5; 5];[6];[1]]
We will again use recursive calls to auxiliary function, very creatively called aux
. Apart from keeping track of repetitions, we also need to collect them into sublists. So, in this case, as we traverse the input list and process element by element, we will collect the repeating ones in a sublist and collect the ones that are not consecutive repetitions in another (as this will also be a part of our final result). We know that we usually return the accumulator as the result - so in this case, we may want to maintain two accumulators - one cur
to collect the consecutive repeating elements, and another acc
to collect the remaining.
- When we encounter repetitions, we will push the repeating entries into
cur
sublist - When there are no repetitions, we will keep merging
cur
withacc
and eventually returnacc
as the result.
In both the compress
and pack
functions that use auxiliary function, we reverse the result using OCaml List
module’s built-in rev
function.
Food for thought - why is the result getting reversed? If you work out a small example, it would become apparent.
That’s all for today. Enjoy your weekend!