将 Haskell 多态余弦函数转换为 F#

Question

我正在尝试将一些 Haskell 代码转换为 F#，但我遇到了一些麻烦，因为 Haskell 默认情况下是惰性的，而 F# 不是。我还在学习 F# 的方法。下面是 Haskell 中的多态余弦函数，具有相当好的性能。我想尝试在 F# 中保持相同或更好的性能参数。我希望看到 F# List 版本和 F# Seq 版本，因为 Seq 版本更像是惰性 Haskell，但 List 版本可能会表现更好。感谢您的任何帮助。

效率：所使用的算术运算数量与级数中的项数成正比

空间：使用恒定空间，与项数无关

takeThemTwoByTwo xs =
    takeWhile (not . null) [take 2 ys | ys <- iterate (drop 2) xs]

products xss = [product xs | xs <- xss]

pairDifferences xs =
    [foldr (-) 0 adjacentPair | adjacentPair <- takeThemTwoByTwo xs]

harmonics x = [x/(fromIntegral k) | k <- [1 ..]]

cosineTerms = scanl (*) 1 . products . takeThemTwoByTwo . harmonics

cosine = foldl (+) 0 . pairDifferences .
    take numberOfTerms . cosineTerms

Answer 1

这是我的尝试，以防您懒惰阅读：

let harmonics x = 
    Seq.initInfinite(fun i -> - x*x/(float ((2*i+1)*(2*i+2))))

let cosineTerms = Seq.scan (*) 1.0 << harmonics

let cosine numberOfTerms = Seq.sum << Seq.take numberOfTerms << cosineTerms

我很难发现您正在使用泰勒级数以弧度计算余弦：

余弦(x) = 1 - x²/2！ + x⁴/4！ - x⁶/6！ +
...

让我描述一下您正在做什么：

1. 创建一个 x/k 的无限序列，其中 k 是从 1 开始的整数。

2. 将上述序列分成两个块，并通过与 1 种子相乘进行扫描，得到 x²/((2k-1)*(2k )) （开头处的 1 除外）。

3. 再次将新序列分成两个块，以 x^4k-4/((4k-4)!) - x^4k-2/((4k-2)!) 并将它们全部相加以获得最终结果。

由于在 F# 中分割序列可能效率低下，而且 takeThemTwoByTwo 函数也不是必需的，因此我选择了另一种方法：

1. 创建一个无限序列 - x²/((2k- 1)*(2k))，其中 k 是从 1 开始的整数。
2. 通过与 1 种子相乘来扫描序列；我们得到一个序列 (-1)^k * x^2k/((2k)!)。
3. 将所有元素相加即可得到最终结果。

上面的程序是我的描述的直接翻译，简洁明了。在我的机器上，使用 numberOfTerms = 200000 迭代计算 cosine 需要 0.15 秒；我认为它对于您的目的来说足够有效。

此外，List 版本应该很容易从这个版本翻译出来。

更新：

好吧，我的错误是低估了问题的多态性部分。我更关注性能部分。这是一个多态版本（与 float 版本密切相关）：

let inline cosine n (x: ^a) = 
    let one: ^a = LanguagePrimitives.GenericOne
    Seq.initInfinite(fun i -> LanguagePrimitives.DivideByInt (- x*x) ((2*i+1)*(2*i+2)))
    |> Seq.scan (*) one
    |> Seq.take n
    |> Seq.sum

Seq.initInfinite 不如 @kvb 中的 Seq.unfold 强大回答。我保留它是为了让事情变得简单，因为 n 无论如何都在 int 范围内。

Answer 2

Pad的回答很好，但不是多态的。一般来说，在 F# 中创建此类定义的情况比在 Haskell 中要少得多（而且有点痛苦）。这是一种方法：

module NumericLiteralG =
    let inline FromZero() = LanguagePrimitives.GenericZero
    let inline FromOne() = LanguagePrimitives.GenericOne    

module ConstrainedOps =
    let inline (~-) (x:^a) : ^a = -x
    let inline (+) (x:^a) (y:^a) : ^a = x + y
    let inline (*) (x:^a) (y:^a) : ^a = x * y
    let inline (/) (x:^a) (y:^a) : ^a = x / y

open ConstrainedOps

let inline cosine n x = 
    let two = 1G + 1G
    Seq.unfold (fun (twoIp1, t) -> Some(t, (twoIp1+two, -t*x*x/(twoIp1*(twoIp1+1G))))) (1G,1G)
    |> Seq.take n
    |> Seq.sum

Answer 3

正如 Pad 所写，这似乎是 cos(x) 关于 x=0 的泰勒级数展开：

余弦(x) = 1 - x²/2！ + x⁴/4！ - x⁶/6！ + ...

所以你的问题是一个XY问题：你提出了一个解决方案而不是提出问题。相反，提出问题可以更容易地以不同的方式解决问题。

让我们首先在 F# 中编写一个 float 特定版本：

let cosine n x =
  let rec loop i q t c =
    if i=n then c else
      loop (i + 1) (q + 10 + 8*i) (-t * x * x / float q) (c + t)
  loop 0 2 1.0 0.0

例如，我们可以计算 x=0.1 展开式的 1M 项：

cosine 1000000 0.1

在 F# 中实现此多态性的最佳方法是将函数参数化为它使用的运算符并将其标记为内联，以消除此参数化的性能开销：

let inline cosine zero one ofInt ( ~-. ) ( +. ) ( *. ) ( /. ) n x =
  let rec loop i q t c =
    if i=n then c else
      loop (i + 1) (q + 10 + 8*i) (-.t *. x *. x /. ofInt q) (c +. t)
  loop 0 2 one zero

现在我们可以使用 float 计算 1M 项，如下所示，速度同样快作为before:

cosine 0.0 1.0 float ( ~- ) (+) (*) (/) 1000000 0.1

但我们也可以做单精度 float:

cosine 0.0f 1.0f float32 ( ~- ) (+) (*) (/) 1000000 0.1f

和任意精度有理数:

cosine 0N 1N BigNum.FromInt (~-) (+) (*) (/) 10 (1N / 10N)

甚至符号:

type Expr =
  | Int of int
  | Var of string
  | Add of Expr * Expr
  | Mul of Expr * Expr
  | Pow of Expr * Expr

  static member (~-) f = Mul(Int -1, f)
  static member (+) (f, g) = Add(f, g)
  static member (*) (f, g) = Mul(f, g)
  static member (/) (f, g) = Mul(f, Pow(g, Int -1))

cosine (Int 0) (Int 1) Int (~-) (+) (*) (/) 3 (Var "x")

为了使它更快，将公共子表达式 -x*x 提升出来的循环。