将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

我很难发现你cosine使用泰勒系列计算弧度:

余弦(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. 对所有元素求和以获得最终结果.

以上程序是我的描述的直接翻译,简洁明了.cosine使用numberOfTerms = 200000迭代计算在我的机器上需要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没有Seq.unfold@kvb的回答那么强大.我保持简单,因为无论如何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