Home > Back-end >  Why is this nested recursive call in a match pattern not working?
Why is this nested recursive call in a match pattern not working?

Time:03-23

I wrote a simple function to replicate every element in a list a given amount of times.

    let rec replicate l n = 
        let rec f l n acc = 
            match l with 
            |[]->acc
            |x::xs->f xs n (let rec h e n acc = if n = 0 then acc else h e (n-1) (e::acc) in h x n acc) 
        in List.rev (f l n [])

This is working as Im calling f and set its accumulator to the result of the helper method h

But why is the following method not working?

let rec replicate l n = 
    let rec f l n acc = 
        match l with 
        |[]->acc
        |x::xs->(let rec h e n acc = if n = 0 
        then f xs n acc else h e (n-1) (e::acc) 
        in h x n acc) 
    in f l n [];;

Here I'm calling the outer function f in case n=0.

Here are the results for the same call with the two functions:

  1. replicate ["a"; "b"; "c"] 3;;
  • : string list = ["a"; "a"; "a"; "b"; "b"; "b"; "c"; "c"; "c"]
  1. replicate ["a"; "b"; "c"] 3;;
  • : string list = ["a"; "a"; "a"]

CodePudding user response:

In the second line of

let rec h e n acc = 
  if n = 0 then f xs n acc
  else h e (n-1) (e::acc) 
in h x n acc

you are calling f xs n acc with n=0 and not the initial value of n.

As a general advice, it is better to not nest recursive function definitions. Indeed, this limits the complexity of your function control flow. For instance, with

let rec repeated_append n x l =
  if n = 0 then l
  else repeated_append (n-1) x (x::l)

let replicate n l = 
  let rec replicate_aux n acc l = 
    match l with 
    | [] -> List.rev acc
    | x::xs-> replicate_aux n (repeated_append n x acc) xs
  in
  replicate_aux n [] l

I am guaranteed that the recursive functions repeated_append and replicate_append only call themselves in their body. In particular, there is no possibility of h calling replicate or f which makes the function easier to read.

  • Related