1

我最近开始使用 F# 并实现了一个非常基本的递归函数，它代表了埃拉托色尼筛法。我想出了以下工作代码：

static member internal SieveOfEratosthenesRecursive sequence accumulator =
    match sequence with
    | [] -> accumulator
    | head::tail -> let rest = tail |> List.filter(fun number -> number % head <> 0L)
                    let newAccumulator = head::accumulator
                    Prime.SieveOfEratosthenesRecursive rest newAccumulator

这个函数并不是真正的内存效率，所以我试图消除变量“rest”和“newAccumulator”。我想出了以下代码

static member internal SieveOfEratosthenesRecursive sequence accumulator =
    match sequence with
    | [] -> accumulator
    | head::tail -> tail    |> List.filter(fun number -> number % head <> 0L) 
                            |> Prime.SieveOfEratosthenesRecursive (head::accumulator)

据我了解，我读过的教程 Prime.SieveOfEratosthenesRecursive 将被调用，过滤后的尾部作为第一个参数，由head::accumulator组成的列表作为第二个参数。但是，当我尝试使用减少的变量使用来运行代码时，程序会陷入无限循环。为什么会发生这种情况，我做错了什么？

4

2 回答 2

1

据我了解，我已阅读 Prime.SieveOfEratosthenesRecursive 的教程将被调用，过滤后tail的参数为第一个参数，列表由head::accumulator第二个参数组成。

你有这个倒退。

在第一个版本中，您将通过restthen newAccumulator；在第二个版本中，您实际上是通过newAccumulatorthen rest。即，您已经转换了论点。

Prime.SieveOfEratosthenesRecursive (head::accumulator)是一个部分函数应用程序，您将在其中应用(head::accumulator)作为第一个参数 ( sequence)。此部分函数应用程序产生一个一元函数（期望accumulator），您将（通过|>）传递给该函数，该函数在您的代码的第一个版本中被调用rest。

更改SieveOfEratosthenesRecursive的参数顺序是最简单的解决方案，但我也会考虑类似以下惯用语：

static member internal SieveOfEratosthenesRecursive sequence accumulator =
    match sequence with
    | [] -> accumulator
    | head::tail ->
        tail
        |> List.filter(fun number -> number % head <> 0L) 
        |> Prime.SieveOfEratosthenesRecursive <| (head::accumulator)

或者

static member internal SieveOfEratosthenesRecursive sequence accumulator =
    let inline flipzip a b = b, a
    match sequence with
    | [] -> accumulator
    | head::tail ->
        tail
        |> List.filter(fun number -> number % head <> 0L) 
        |> flipzip (head::accumulator)
        ||> Prime.SieveOfEratosthenesRecursive

FWIW，在这里消除rest和newAccumulator命名变量不会对您的内存使用产生丝毫影响。

于 2012-06-07T21:53:58.127 回答
1

第二个函数中的最后一次调用相当于：

Prime.SieveOfEratosthenesRecursive newAccumulator rest

您可以在其中切换两个参数的位置。由于newAccumulator每次递归调用后都会变大，因此您永远不会达到空列表的基本情况。

经验法则是将最频繁变化的参数放在最后：

let rec sieve acc xs =
    match xs with
    | [] -> acc
    | x::xs' -> xs' |> List.filter (fun y -> y % x <> 0L) 
                    |> sieve (x::acc)

上面的函数可以使用function关键字来缩短：

let rec sieve acc = function
    | [] -> acc
    | x::xs' -> xs' |> List.filter (fun y -> y % x <> 0L) 
                    |> sieve (x::acc)

使用 pipe ( |>) 运算符只会使函数更具可读性，它根本不会影响内存使用。

于 2012-06-07T22:06:16.323 回答