將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

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 2

這裏是我的嘗試如果你是懶惰閱讀：

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：

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版本應該很容易翻譯。

UPDATE：

好了，我的錯，是低估了問題的多態性一部分。我更關注性能部分。這裏是一個多態的版本（保持密切的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 3

作爲墊寫，這似乎是COS的泰勒級數展開（X）約X = 0：

餘弦（x）= 1 - X 2/2！ + x 4/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＃中的這種多態是爲了將函數參數化爲它使用的運算符，並將其標記爲inline以便消除此參數化的性能開銷：

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方面：

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

但是，我們也可以做單精度float：

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

和任意-precision rational：

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出loop。