Comparing run-length decoding algorithms

Question

I'm working on Ocaml.org 99 problems, and I solved the run-length decode one.

Here is the solution given by the site:

let decode l =
 let rec many acc n x = 
 if n = 0 then acc else many (x :: acc) (n-1) x in
 let rec aux acc = function
 | [] -> acc
 | One x :: t -> aux (x :: acc) t
 | Many (n,x) :: t -> aux (many acc n x) t in
 aux [] (List.rev l);;

And here is mine:

let decode l =
 let rec aux acc = function
 | [] -> acc
 | One elem :: t -> aux (elem :: acc) t
 | Many(cnt, elem) :: t -> if cnt > 0 then aux (elem::acc) (Many(cnt - 1, elem) :: t) else aux acc t in
 List.rev (aux [] l);;

Test:

type 'a rld =
 | One of 'a 
 | Many of int * 'a;;
(* result expected : ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"] *)
decode [Many (4,"a"); One "b"; Many (2,"c"); Many (2,"a"); One "d"; Many (4,"e")];;

Could my solution become more optimal?

Answer 1

Elegance is a matter of taste, so you'll probably get different answers for that point. Personally, I find your solution easier to understand: it makes good use of the algebra defined through the rld type.

From an efficiency standpoint, your algorithm creates as Many values as the repetition count in the original one. That means that your algorithm will generate memory allocation. It will also have to match it again as many times through recursion, so there's a computational extra load as well. The solution proposed by the site is more efficient in that regard: it only allocates the necessary values to construct the resulting list, and only matches once each element of the input list.

• Chris: Also, by reversing the list of rld values, List.rev is being called on a smaller list, which is going to save at least a small amount of work.