F# 中的递归序列

Question

假设我想计算一个整数的阶乘。在 F# 中一个简单的方法是：

let rec fact (n: bigint) =
    match n with
    | x when x = 0I -> 1I
    | _ -> n * fact (n-1I)

但是，如果我的程序需要动态编程，我如何在使用记忆化的同时支持函数式编程？

我的一个想法是制作一系列惰性元素，但我运行遇到了问题。假设以下代码在 F# 中是可接受的（但不是）：

let rec facts = 
    seq {
        yield 1I
        for i in 1I..900I do 
            yield lazy (i * (facts |> Seq.item ((i-1I) |> int)))
    }

在 F# 中有类似这个想法的东西吗？（注意：我知道我可以使用 .NET 词典，但不是调用“.Add()”方法命令式风格？）

另外，有什么方法可以用一个函数来概括它吗？例如，我可以创建一个长度为 collatz function 的序列，该序列由函数定义：

let rec collatz n i = 
    if n = 0 || n = 1 then (i+1)
    elif n % 2 = 0 then collatz (n/2) (i+1) 
    else collatz (3*n+1) (i+1)

Answer 1

如果您想懒惰地做，这是一个不错的方法：

let factorials =
    Seq.initInfinite (fun n -> bigint n + 1I)
    |> Seq.scan ((*)) 1I
    |> Seq.cache

Seq.cache 意味着您不会重复计算已经枚举的元素。

然后您可以使用特定数量的阶乘，例如Seq.take n，或使用 Seq.item n.

获取特定阶乘

Answer 2

起初，我在你的例子中看不出你的意思 "dynamic programming"。

使用记忆并不意味着某些东西不是 "functional" 或破坏不变性。重要的重点不在于如何实施。重要的是它的行为方式。一个使用的函数一个可变的记忆仍然被认为是纯的，只要它表现得像一个纯的 function/immutable 功能。因此，在调用者不可见的有限范围内使用可变变量仍然是认为是纯的。如果实现很重要，我们也可以将尾递归视为不是纯粹的，因为编译器将其转换为一个在引擎盖下具有可变变量的循环。那里还存在一些 List.xyz 使用变异并将事物转换为可变变量的函数只是因为速度。这些功能仍然被认为是 pure/immutable 因为它们仍然表现得像纯函数。

序列本身已经是惰性的。仅当您请求这些元素时，它才会计算所有元素。所以创建一个 returns 惰性元素的序列对我来说没有多大意义。

如果你想加快计算速度，有多种方法可以做到。即使在递归中版本你可以使用传递给下一个函数调用的累加器。而不是做深递归。

let fact n =
    let rec loop acc x =
        if   x = n 
        then acc * x
        else loop (acc*x) (x+1I)
    loop 1I 1I

整体与

相同

let fact' n =
    let mutable acc = 1I
    let mutable x   = 1I
    while x <= n do
        acc <- acc * x
        x   <- x + 1I
    acc

只要你正在学习函数式编程，最好习惯第一个版本并学习了解循环和递归如何相互关联。但除了学习，没有理由让你总是应该强迫自己总是写第一个版本。最后你应该多用你考虑的可读且更容易理解。不是某物是否使用可变变量作为实现。

最后没有人真正关心具体的实现。我们应该将函数视为黑盒。所以只要一个函数的行为就像一个纯函数，一切都很好。

上面使用了累加器，所以你不需要再次重复调用一个函数来获取一个值。所以你也不需要内部可变缓存。如果你真的有一个缓慢的递归版本并且想加速它缓存你可以使用类似的东西。

let fact x =
    let rec fact x =
        match x with
        | x when x = 1I -> 1I
        | x             -> (fact (x-1I)) * x

    let cache = System.Collections.Generic.Dictionary<bigint,bigint>()
    match cache.TryGetValue x with
    | false,_ -> 
        let value = fact x
        cache.Add(x,value)
        value
    | true,value ->
        value

但这可能会比带有累加器的版本慢。如果你想缓存对 fact 的调用，甚至跨多个 fact 在整个应用程序中调用，那么您需要一个外部缓存。您可以在事实之外创建字典并使用为此的私有变量。但是您也可以使用带有闭包的函数，并使整个过程本身通用。

let memoize (f:'a -> 'b) =
    let cache = System.Collections.Generic.Dictionary<'a,'b>()
    fun x ->
        match cache.TryGetValue x with
        | false,_ ->
            let value = f x
            cache.Add(x,value)
            value
        | true,value ->
            value

let rec fact x =
    match x with
    | x when x = 1I -> 1I
    | x             -> (fact (x-1I)) * x

所以现在你可以使用类似的东西了。

let fact = memoize fact
printfn "%A" (fact 100I)
printfn "%A" (fact 100I)

并从所有其他接受 1 个参数的函数中创建一个记忆函数

请注意，记忆不会自动加快一切。如果你实际上使用了 memoize 函数没有任何东西可以加速，它甚至会因为没有记忆而变慢。您可以添加 printfn "Cache Hit" 到 memoize 函数内的 | true,value -> 分支。连续调用 fact 100I 两次只会产生一个 "Cache Hit" 行。

问题在于算法的工作原理。它从 100I 开始，下降到 0I。所以计算 100 我问 99I的缓存，它不存在，所以它尝试计算98I并询问缓存。那也不存在所以它下降到 1I。它总是询问缓存，从未找到结果并计算所需的值。所以你永远不会得到 "Cache Hit" 并且你有询问缓存的额外工作。真正受益于缓存你需要改变事实本身，所以它从 1I 开始到 100I。当前版本甚至会抛出 Whosebug 对于大输入，即使有 memoize 功能。

只有第二次调用从缓存中受益，这就是为什么调用 fact 100I 两次只会打印一次 "Cache Hit" 的原因。

这只是一个例子，很容易让 caching/memoization 的行为出错。一般来说，你应该尝试编写一个函数，使其尾递归并使用累加器代替。不要尝试编写期望的函数记忆以正常工作。

我会选择带累加器的解决方案。如果您分析了您的应用程序并且发现这仍然很慢并且您的应用程序存在瓶颈，缓存 fact 会有所帮助，那么您也可以只缓存结果 facts 直接。像这样的东西。您可以为此使用 dict 或地图。

let factCache = [1I..100I] |> List.map (fun x -> x,fact x) |> dict
let factCache = [1I..100I] |> List.map (fun x -> x,fact x) |> Map.ofList

F# 中的递归序列

Recursive Sequences in F#

recursion

dynamic

f#

functional-programming

memoization