Converting Haskell Polymorphic Cosine function to F#

Question

I'm trying to convert some Haskell code to F# but I'm having some trouble since Haskell is lazy by default and F# is not. I'm also still learning my way around F#. Below is a polymorphic cosine function in Haskell with pretty good performance. I want to try and keep the same or better performance parameters in F#. I would like to see a F# List version and a F# Seq version since the Seq version would be more like the lazy Haskell but the List version would probably perform better. Thanks for any help.

Efficiency: number of arithmetic operations used proportional to number of terms in series

Space: uses constant space, independent of number of terms

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

Here is my attempt in case you're 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

I have a hard time finding out that you're calculating cosine in radian using Taylor series:

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

Let me describe what you're doing:

1. Create an infinite sequence of x/k where k is an integer starting from 1.

2. Split above sequence into chunks of two and scan by multiplying with a seed of 1 to have a sequence of x²/((2k-1)*(2k)) (with an exception of 1 at the beginning).

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

Because it's likely to be inefficient to split sequences in F# and takeThemTwoByTwo function is not essential, I chose another approach:

1. Create an infinite sequence of - x²/((2k-1)*(2k)) where k is an integer starting from 1.
2. Scan the sequence by multiplying with a seed of 1; we get a sequence of (-1)^k * x^2k/((2k)!).
3. Sum all elements to obtain final result.

Above program is a direct translation of my description, succinct and simple. Computing cosine with numberOfTerms = 200000 iterations takes 0.15 seconds on my machine; I suppose it is efficient enough for your purpose.

Furthermore, a List version should be easy to translate from this one.

UPDATE:

Ok, my fault was to underestimate the polymorphism part of the question. I focused more on the performance part. Here is a polymorphic version (keeping closely to 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 is less powerful than Seq.unfold in @kvb 's answer. I keep it to make things simple because n is in int range anyway.