Haskell Transformation Polymorphic Cosine Function in F #

Question

I am trying to convert some Haskell code to F #, but I have problems because Haskell is lazy by default and F # is not. I am still involved in F #. Below is a polymorphic cosine function in Haskell with pretty good performance. I want to try to keep the same or better performance options in F #. I would like to see the F # list version and the F # Seq version, as the Seq version will be more like lazy Haskell, but the List version will probably work better. Thanks for any help.

Efficiency: the number of arithmetic operations used in proportion to the number of members in the rows

Space: Uses a constant space independent of the number of members

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

The answer to the panel is good, but not polymorphic. In general, it is much less common to create such definitions in F # than in Haskell (and a bit of pain). Here is one approach:

 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 nx = 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

Here is my attempt if you are too lazy to read:

 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 

It’s hard for me to find out that you calculate cosine in a radin using the Taylor series:

cosine (x) = 1 - x 2/2! + x 4/4! - x 6/6! + ...

Let me describe what you are doing:

• Create an infinite sequence x/k , where k is an integer starting at 1 .

• Divide the sequence above into pieces of two and scan by multiplying seed 1 by the sequence x ² / ((2k-1) * (2k)) (except for 1 at the beginning).

• Divide the new sequence into two blocks again to have differences in the form x ^4k-4 / ((4k-4)!) - x ^4k-2 / ((4k-2)!) And sum them all to get the final result.

Since it is probably ineffective for separating sequences in the F # and takeThemTwoByTwo , it is not significant, I chose a different approach:

• Create an infinite sequence - x ² / ((2k-1) * (2k)), where k is an integer starting at 1 .
• Sequence scan by multiplying by seed 1 ; we get the sequence (-1) ^k * x ^2k / ((2k)!).
• Summarize all the elements to get the final result.

The above program is a direct translation of my description, short and simple. Calculating cosine with numberOfTerms = 200000 iterations takes 0.15 seconds on my machine; I believe this is effective enough for your purpose.

In addition, a List version should be easily translated from this.

UPDATE:

Well, my fault was to underestimate part of the polymorphism of the issue. I focused more on performance. Here is the polymorphic version (supporting the float version):

 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 less efficient than Seq.unfold in Seq.unfold 's answer. I keep it to make everything simple, because n is in the range of int .

Answer 3

As Pad wrote, this is apparently a Taylor expansion of cos (x) around x = 0:

cosine (x) = 1 - x² / 2! + x⁴ / 4! - x⁶ / 6! + ...

So your question is XY: you presented a solution, not a problem. Presenting the problem instead simplifies solving it in different ways.

Let's start by writing a float specific version in F #:

 let cosine nx = let rec loop iqtc = 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 

For example, we can calculate 1M expansion terms x = 0.1:

 cosine 1000000 0.1 

The best way to make this polymorphism in F # is to parameterize the function over the operators it uses and mark it as inline to remove the performance overhead of this parameterization:

 let inline cosine zero one ofInt ( ~-. ) ( +. ) ( *. ) ( /. ) nx = let rec loop iqtc = 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 

Now we can evaluate 1M expressions using a float like this, it is as fast as before:

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

But we can also do single precision float :

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

And the rationality of arbitrary accuracy:

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

And even symbolic:

 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") 

To make this faster, raise the common -x*x subexpression from loop .