List Replication

Hi there! The idea of this problem is just to read some numbers from stdin and replicate them, but using lists. The input would be like this:

3 // # of repetitions
1 // first number ...
2
3
4 // end of input, last number

Then the output would be a list with each number repeated the amount of times given. For the case above, it would show “1” three times, “2” three times and so on, each element on a different line. I was given the IO functions by HackerRank and filled the function to create the new list. The result is below.

(* This function was given by HackerRank *)
let rec read_lines () =
    try let line = read_line () in
        int_of_string (line) :: read_lines()
    with
        End_of_file -> []

(* I filled this function *)
let f n arr =
  let rec repeat value n =
    if n > 0 then
      value::(repeat value (n-1))
    else [] in
  let rec r n arr =
    match arr with
    | [] -> []
    | hd::tl -> (repeat hd n) @ (r n tl) in
  r n arr

(* This function was given by HackerRank *)
let () =
    let n::arr = read_lines() in
    let ans = f n arr in
    List.iter (
      fun x -> print_int x;
      print_newline ()) ans;;

This was not hard. Nevertheless, when I write code like this, I think that solutions with arrays would be much more efficient. There are multiple cases of memory allocations in that code, but it could have been done only once in the function $f(n, arr)$. Why? If you have a list of $m$ elements and you want to repeat each $n$ times, you just allocate memory for an array of size $m\cdot n$ and then fill the repeated elements, using a simple loop.

The way function $f$ is written does not use loops, being basically functional, avoiding imperative patterns. This has a positive side: it is easier to reason about the code. The downside I already mentioned. Which pattern to use depends on what is the main concern and how big the inputs will be.

Thanks for reading!