# F# Humor (kinda)

So I was bored, didn’t know what to do, started solving problems on codewars (shut up!).

There was this little problem there, where they are asking you to compute $\frac{\sum_{i=1}^n i!}{n!}$, for potentially large n’s with $10^{-6}$ precision.

It’s easy to see that this needs to be refactored (no need to actually compute factorials), and the solution I found most “fsharpy” and beautiful (and not mine) was:

let going n =
{ n .. -1 .. 2 }
|> Seq.map double
|> Seq.scan (/) 1.
|> Seq.sum


This works. Here is my less elegant solution:

let going n =
let rec sumBack (acc : double) n (cur : double) =
if n = 0 || cur < 1e-6 then Math.Round(acc, 6)
else
sumBack (acc + cur) (n - 1) (cur / double n)
sumBack  0. n 1.


Kinda ugh, but what I found humorous and instructive (things humorous usually are) was that falling for the language beauty and power is not always conducive to performance. Since we have the $10^{-6}$ constraint, it’s not necessary to scan the entire sequence {n..2}, we can start backwards and terminate as soon as the constraint is met. Thus, for very large n, we’ll only need to perform 1 division. So as the sum converges to 1, performance of the second solution converges to O(1), and, since it’s tail recursion, we aren’t actually using any stack, our memory usage is always O(1), which is more than we can say for the first solution. But I still love it more than my own for purely aesthetical reasons.

## One thought on “F# Humor (kinda)”

1. hedgehogface says:

You can do a functional version that terminates when the constraint is met.

let going n =
{ n .. -1 .. 2 }
|> Seq.map double
|> Seq.scan (/) 1.
|> Seq.takeWhile (fun x -> x > 1e-6)
|> Seq.sum
|> (fun x -> Math.Round(x,6))

As the sequence is never materialised the memory usage should not be as high as you think.

This site uses Akismet to reduce spam. Learn how your comment data is processed.