Tail Recursive map f#

Question

I want to write a tail recursive function to multiply all the values in a list by 2 in F#. I know there is a bunch of ways to do this but i want to know if this is even a viable method. This is purely for educational purposes. I realize that there is a built in function to do this for me.

 let multiply m =
    let rec innerfunct ax = function
    | [] -> printfn "%A" m
    | (car::cdr) -> (car <- car*2 innerfunct cdr);
  innerfunct m;;



let mutable a = 1::3::4::[]
multiply a

I get two errors with this though i doubt they are the only problems.

This value is not mutable on my second matching condition

and

This expression is a function value, i.e. is missing arguments. Its type is 'a list -> unit. for when i call length a.

I am fairly new to F# and realize im probably not calling the function properly but i cant figure out why. This is mostly a learning experience for me so the explanation is more important than just fixing the code. The syntax is clearly off, but can i map *2 to a list just by doing the equivalent of

car = car*2 and then calling the inner function on the cdr of the list.

Answer 1

There are a number of issues that I can't easily explain without showing intermediate code, so I'll try to walk through a commented refactoring:

First, we'll go down the mutable path:

1. As F# lists are immutable and so are primitive ints, we need a way to mutate that thing inside the list:

   let mutable a = [ref 1; ref 3; ref 4]
   

2. Getting rid of the superfluous ax and arranging the cases a bit, we can make use of these reference cells:

   let multiply m =
       let rec innerfunct = function
       | [] -> printfn "%A" m
       | car :: cdr ->
           car := !car*2
           innerfunct cdr
       innerfunct m
   

3. We see, that multiply only calls its inner function, so we end up with the first solution:

   let rec multiply m =
       match m with
       | [] -> printfn "%A" m
       | car :: cdr ->
           car := !car*2
           multiply cdr
   

   ^{This is really only for it's own purpose. If you want mutability, use arrays and traditional for-loops.}

Then, we go up the immutable path:

1. As we learnt in the mutable world, the first error is due to car not being mutable. It is just a primitive int out of an immutable list. Living in an immutable world means we can only create something new out of our input. What we want is to construct a new list, having car*2 as head and then the result of the recursive call to innerfunct. As usual, all branches of a function need to return some thing of the same type:

   let multiply m =
       let rec innerfunct = function
       | [] ->
           printfn "%A" m
           []
       | car :: cdr -> 
           car*2 :: innerfunct cdr
       innerfunct m
   

2. Knowing m is immutable, we can get rid of the printfn. If needed, we can put it outside of the function, anywhere we have access to the list. It will always print the same.

3. We finish by also making the reference to the list immutable and obtain a second (intermediate) solution:

   let multiply m =
       let rec innerfunct = function
       | [] -> []
       | car :: cdr -> car*2 :: innerfunct cdr
       innerfunct m
   
   let a = [1; 3; 4]
   printfn "%A" a
   let multiplied = multiply a
   printfn "%A" multiplied
   

4. It might be nice to also multiply by different values (the function is called multiply after all and not double). Also, now that innerfunct is so small, we can make the names match the small scope (the smaller the scope, the shorter the names):

   let multiply m xs =
       let rec inner = function
       | [] -> []
       | x :: tail -> x*m :: inner tail
       inner xs
   

   Note that I put the factor first and the list last. This is similar to other List functions and allows to create pre-customized functions by using partial application:

   let double = multiply 2
   let doubled = double a
   

5. All that's left now is to make multiply tail-recursive:

   let multiply m xs =
       let rec inner acc = function
       | [] -> acc
       | x :: tail -> inner (x*m :: acc) tail
       inner [] xs |> List.rev
   

So we end up having (for educational purposes) a hard-coded version of let multiply' m = List.map ((*) m)