3
\$\begingroup\$

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?

\$\endgroup\$

2 Answers 2

Reset to default
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Dec 17, 2024 at 4:32
1
\$\begingroup\$

From a purely style standpoint, I can't help but think that your code would be improved by using a conditional guard.

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)

Becomes:

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

From the standpoint of decomposing the problem using your approach, which as noted has some memory allocation implications, I think a lot of what you're doing should be factored out into a function that "takes" an element from an rle list.

This function would give us the top element and the remainder of the list, and wrap the whole thing in an option type to handle reaching the end of the list. (Exceptions would also be a valid approach to indicating this.)

let rec take = function
  | [] -> None
  | One e :: t -> Some (e, t)
  | Many (c, _) :: t when c <= 0 -> take t
  | Many (c, e) :: t -> Some (e, Many (c - 1, e) :: t)

Now, we can implement decode in terms of this.

let rec decode lst =
  match take lst with
  | None -> []
  | Some (e, t) -> e :: decode t

Of course, if we want this to be tail-recursive we can use an accumulator, as you've done.

let decode lst =
  let rec aux acc lst =
    match take lst with
    | None -> acc
    | Some (e, t) -> aux (e :: acc) t
  in
  lst |> aux [] |> List.rev
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.