OCaml recursive function that repeats the values of an array

Learning
1

I have to solve this exercise in OCaml : Write a recursive function that repeats the values of a list, for exemple repeat [3;2;4;5] should give [3;2;2;4;4;4;5;5;5;5]

I think that I should use match with and concatenate but I really have no idea how to start this exercise…

I would be very grateful for your help !

2

Is it “repeat n times list member number n-1” for all list members?

Repeat 1 time member number 0 which is 3
etc.

3

It seems like you want to repeat the nth element (n+1) times (remember indexes start at 0).

I think that I should use match with and concatenate

Not bad intution, if you were to use an imperative approach that could work.

I got it to work like this:

utop # let repeat ls =
         (* `helper` will just repeat `l` n times *)
         let rec helper acc n l = 
             if n = 0 
             then acc 
             else helper (l @ acc) (n-1) l in
         (* `mapi` to know the position of the element, `flatten` 
             build a single list out of many *)
         List.flatten @@ List.mapi (fun i x -> helper [] (i+1) [x]) ls ;;
val repeat : 'a list -> 'a list = <fun>

utop # repeat [3;2;4;5] ;;
- : int list = [3; 2; 2; 4; 4; 4; 5; 5; 5; 5]

This builds a list of lists and then flattens it. Not the best code but seems to work like you want it to :smiley:

Have fun with OCaml!

2 Likes
4

Besides the recursive approach, there’s also a really fun way to do it with some standard library list functions ( https://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html ) and the following technique:

  • For a given list, map each element to a list of n + 1 elements, where n is the zero-based index of the element
  • Flatten the resulting list of lists of ints, into a list of ints.

I actually could have sworn there was a List.flat_map, which allowed doing this in an even more succinct way, but it looks like it’s not in the published library yet.

2 Likes
5 
let repeat_values l =
  List.mapi (fun i v -> List.init (i + 1) (fun _ -> v)) l
  |> List.concat

for a standard library quick solution. If you want a more efficient solution, you should probably write your own recursive function, a kind of custom List.fold_left.

1 Like
6

I found a solution !
let rec inter l = match l with |[]->[] |p::q->p::q@(inter q) ;; (* # inter [1;2;3;4];; - : int list = [1; 2; 3; 4; 2; 3; 4; 3; 4; 4] *)
Then I just sorted this list and It works

7

What about using Preformatted text (</> or Crt+Shift+c) to improve code readability?
Example:

let rec inter l = 
match l with 
  | []->[] 
  | p :: q -> p :: q @ ( inter q )

What if the elements can’t be sorted after application of the function inter because they are not sorted in the input value?
Example:

List.sort compare (inter [3;2;4;5])
- : int list = [2; 2; 3; 4; 4; 4; 5; 5; 5; 5]
1 Like
8

If you use Base, there’s List.concat_mapi:

let repeat l =
  List.concat_mapi l ~f:(fun i ele ->
    List.init (i + 1) ~f:(fun _ -> ele))
1 Like