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:

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

This is a simple memoized version of the factorial function. — John Palmer, Dec 11 '13 at 23:50

score 1 · Accepted Answer · answered Dec 11 '13 at 23:54

1

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

answered Dec 11 '13 at 23:54

John Palmer

25,356
3
48
67

TryGetValue returns a boolean (only one value obviously), so what is the second element after the true and false (result in your answer)? Also, why can't I just have "factorials.Add(n, n * factorial(n-1))" after the "->" in the false match? – reggaeguitar Dec 12 '13 at 00:00
1

`Trygetvalue` actually returns a value as well - see here http://msdn.microsoft.com/en-us/library/bb347013(v=vs.110).aspx . This is the reason your version needed the `_`. You can have your version, but that does the recursive call twice which is wasteful. – John Palmer Dec 12 '13 at 00:02
1

`TryGetValue` has an out parameter, which F# gets as the second element. – Jeffrey Sax Dec 12 '13 at 00:02

score 1 · Answer 2 · edited May 23 '17 at 12:11

// 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.

Thanks for the detailed explanation. The answer that you linked to does not include memoization, which is the whole point of this exercise though. P.S. I am coming from C# land which is why I'm trying to learn F# and functional programming, thanks for the advice — reggaeguitar, Dec 12 '13 at 01:14
Where did you mention memorization in the question or title? — Guy Coder, Dec 12 '13 at 01:18
How would you write a factorial function with memoization? The function doesn't have to return the value of the max input, even better would be to return the dictionary (or similar data structure) with the factorials up to the input? — reggaeguitar, Dec 12 '13 at 01:41

Recursive Factorial Function in F# with Memoization

2 Answers2