Recursive Factorial Function in F# with Memoization

Question

I'm just learning F# and I hacked together this function that works, but I don't fully understand what's going on, could someone explain it please?

open System.Collections.Generic

let factorials = Dictionary<int, int>()
factorials.Add(1, 1)

let rec factorial n =
    if n <= 1 then 1
    else
        match factorials.TryGetValue(n) with
        | true, _  -> n * factorial(n-1)
        | false, _ -> 
            factorials.Add(n, n * factorial(n-1))
            n * factorial(n-1)     

let a = factorial 9

My question is:

1. Why do I need to call n * factorial (n-1) at the end of the false match?
2. Why do I need an expression after the -> in the true match?

Answer 1

// Access the library containing the Dictionary module
open System.Collections.Generic

// Crate a key value,pair named factorials, e.g. table, to hold the
// the factorial number n and it's result.
let factorials = Dictionary<int, int>()

// Add an initial entry into the factorials table for the 
// value for one and the result of the factorial of one, being one.
factorials.Add(1, 1)

// Define a recursive function for factorial
// taking one integer parameter
let rec factorial n =
    // If the parameter is less than or equal to one
    // then return one
    if n <= 1 then 1
    // If the parameter is greater than one then
    else
        // look up the result of the factorial in the factorials table.
        // Use TryGetValue when looking up value to avoid errors when
        // there is no matching key for the value.
        // There is a problem here with the way TryGetValue is used.
        // It should be used as
        //   let mutable factresult
        //   factorials.TryGetValue(n,factresult)
        // The problem causes the result of TryGetValue(n) to be
        // the tuple (bool * int) instead of bool with the 
        // value part updating the mutable factresult.
        // Next the patterns for the match are true,_ and false, _ 
        // which match the tuple of the TryGetValue(n)
        // but the _ means to toss out the value it matches
        // because it doesn't have a name, 
        // so the whole use of the factorials table is not needed.
        match factorials.TryGetValue(n) with
        // If there is an entry in the factorials table then take this action.
        // Take n and multiply it by the factorial of n-1.
        // As an example for 5 this becomes 5 * 4 * 3 * 2 * 1
        // Take the result of n * factorial(n-1) and push it on to the stack
        // as the result of the function. 
        | true, _  -> n * factorial(n-1)
        // If there is no entry in the factorials table then
        // calculate the result of the factorial of n, i.e. n * factorial(n-1))
        // and add it to the factorials table.
        // Take the result of n * factorial(n-1) and push it on to the stack
        // as the result of the function. 
        | false, _ -> 
            factorials.Add(n, n * factorial(n-1))
            n * factorial(n-1)     

let a = factorial 9

A better solution.

EDIT

1.Why do I need to call n * factorial (n-1) at the end of the false match?

I take it you are coming from an imperative background and most likely C# because of your use of the Dictionary. Functional code is not imperative code. When coding in a functional language one must think in functions. Functions end by placing their result onto the stack and for all of the ways of exiting a function except by exception must end with the same type signature

So for this match function

   match factorials.TryGetValue(n) with
    | true, _  -> n * factorial(n-1)
    | false, _ -> 
        factorials.Add(n, n * factorial(n-1))
        n * factorial(n-1)

the function has two ways of ending. One via true and one via false. So both of these branches exit with an int from the last function in each branch.

i.e.

n * factorial(n-1)

2.Why do I need an expression after the -> in the true match?

A match statement takes the result of the match, e.g. factorials.TryGetValue(n) and matches againt the possible patterns. Since the signature of this match is (bool * int), you have matched all of the patterns with (true,) and (false,). Now for each match pattern you must have code that details what is to be done. The -> separates the pattern from the code that details what is to be done. Think of the match and the patterns as a switch statement. You are required to have some action for each switch option.

Answer 2

Addressing the comments:

A more common version of the true match would be

|true,result -> result 

you need the bit after the -> to actually return a value.

In the false match, you need to actually compute the factorial, by calculating

n * factorial(n-1)

In fact, a better version of the false case would be

 |false, _ -> 
     let r = n * factorial(n-1)
     factorials.Add(n,r)
     r