F #의 재귀 적 요인 함수 (Memoization)

Question

방금 ​​F #을 배웠고 작동하는이 함수를 해킹했지만 실제로 어떤 일이 일어나는지 완전히 이해하지 못합니다. 누군가 설명해 주시겠습니까?

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 

내 질문은 :

1. 이유는 거짓 일치의 끝에서 n * factorial (n-1)를 호출해야합니까?
2. -> 이후에 표현식이 필요한 이유는 무엇입니까?

Answer 1

코멘트를 주소 :

이

진정한 일치의 일반적인 버전이 실제로 값을 반환 할 -> 후 비트를 필요로

|true,result -> result 

될 것이다. 거짓 경기에서

, 당신은 실제로 사실

n * factorial(n-1) 

을 계산하여, 계승을 계산할 필요가 거짓 케이스의 더 나은 버전은

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

Answer 2

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

더 좋은 것 solution.

편집

1.Why 내가 거짓 경기 끝에 * 계승 (N-1)를 호출 N해야합니까?

나는 사전을 사용했기 때문에 긴급한 배경에서오고 C# 일 가능성이 높습니다. 기능 코드는 명령형 코드가 아닙니다. 함수 언어로 코딩 할 때 함수에서 생각해야합니다. 기능이 일치 기능

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

함수가 두 가지 방법이 있습니다에 대한

그래서 동일한 유형의 서명으로 끝나야합니다 스택에 예외 제외 기능을 종료의 방법 모두를 위해 자신의 결과를 배치하여 종료 끝내기. 진실을 통해 하나, 거짓을 통해 하나. 따라서이 두 분기는 각 분기의 마지막 함수에서 int로 종료됩니다. 실제 경기에서> -

즉

n * factorial(n-1) 

2.Why 난 후 식을해야합니까?

일치 문은 일치 결과를 취합니다. factorials.TryGetValue(n)과 가능한 패턴을 다시 일치시킵니다. 이 일치의 서명은 (bool * int)이므로 (true, ) 및 (false,)의 모든 패턴을 일치 시켰습니다. 이제 각 일치 패턴에 대해 수행 할 작업을 자세히 설명하는 코드가 있어야합니다. ->는 수행 할 작업을 자세히 설명하는 코드와 패턴을 구분합니다.일치와 패턴을 switch 문으로 생각하십시오. 각 스위치 옵션에 대해 몇 가지 조치를 취해야합니다.