FP homework. Is it possible to define a function using nested pattern matching instead of a helper function?

Question

I am solving Programming for the Harvard CS 51 programming course at ocaml. The problem is to define a function that can compress a list of characters into a list of pairs, where each pair contains a series of consecutive randomnesses of the character in the list and the character itself, that is, after applying this function to the list ['a', 'a'; 'a'; 'a'; 'a'; 'b'; 'b'; 'b'; 'c'; 'd'; 'd'; 'd'; 'd'] we should get a list [(5, 'a'); (3, 'b'); (1, 'c'); (4, 'd')]. I came up with a function that uses a helper function to solve this problem:

let to_run_length (lst : char list) : (int*char) list = let rec go is lst1 = match lst1 with | [] -> [(i,s)] | (x::xs) when s <> x -> (i,s) :: go 0 x lst1 | (x::xs) -> go (i + 1) s xs in match lst with | x :: xs -> go 0 x lst | [] -> [] 

My question is: is it possible to define a recursive function to_run_length with nested pattern matching without defining a go helper function. How, in this case, can we save the state of the counter of past elements?

Answer 1

The way you implemented to_run_length is correct, readable, and efficient. This is a good decision. (nitpick only: indent after in is wrong)

If you want to avoid an intermediate function, you should instead use the information present in the return from the recursive call. This can be described in a slightly more abstract way:

• the length of the empty list is the empty list
• the path length in the list x::xs is equal to
  • if the encoding of length xs starts with x , then ...
  • if not, then (x,1) :: enter the length xs

(I intentionally do not provide source code so that you can work with the details, but unfortunately there is not much to hide with such relatively simple functions.)

Food for thought. You usually come across such methods when considering recursive and non-tail recursive functions (what I did is like turning the tail-rec function in the form of non-tail-rec). In this particular case, your original function was not recursive. A function is tail recursive when the argument / result flows only “drop” the recursive calls (you return them, rather than reusing them to create a larger result). In my function, the stream of arguments / results only "raises" recursive calls (calls have the least information, and all the logic in the code is done by checking the results). In your implementation, threads go both down (integer counter) and up (encoded result).

Edit: as requested by the source poster, here is my solution:

 let rec run_length = function | [] -> [] | x::xs -> match run_length xs with | (n,y)::ys when x = y -> (n+1,x)::ys | res -> (1,x)::res 

Answer 2

I do not think it is a good idea to write this function. The current solution is in order.

But if you still want to do this, you can use one of two approaches.

1) Without changing the arguments of your function. You can define some mutable toplevel values ​​that will contain the batteries that are now used in your helper function.

2) You can add an argument to your function to store some data. You can find some examples when googling for a continuation style.

Happy hack!

PS I still want to emphasize that your current solution is in order, and you do not need to improve it!