In Java 8, functional style and efficiency I have shown how bad Haskell performs at the silly task I was using as test.
But there's a detail which makes the test unfair: the problem with the given code is that the factorial function I've written isn't tail recursive.
That is, it isn't a recursive function which can be turned into an iterative function. It is an actual recursion, and we know recursion is bad (except when it isn't, but this isn't the case).
To be fair with Haskell, we need to rewrite the factorial function so that it is tail recursive.
tfact :: Double -> Double -> Double tfact n acc | n == 0.0 = acc | n == 1.0 = acc | n > 1.0 = tfact (n - 1.0) (acc * n) dfact :: Double -> Double dfact n = tfact n 1.0
Running this (with the same test bed we've already used) gives 420 ms (average on 20 runs). Still slow, but a lot less slower than the real recursive version.
The real function
tfact uses an accumulator, and
dfact is some sort of interface just to allow the caller to write
dfact 5.0 instead of
tfact 5.0 1.0.
There's a more elegant way to write it, like this:
dfact :: Double -> Double dfact n = tfact n 1.0 where tfact :: Double -> Double -> Double tfact m acc | m == 0.0 = acc | m == 1.0 = acc | m > 1.0 = tfact (m - 1.0) (acc * m)
The type signature for
tfact is needed because otherwise type inference gets in the way of making the code a little more efficient (the risk is that somewhere it considers an
Integer, which is an expensive arbitrary precision number).
The average on 20 runs is more or less the same (425 ms on 20 runs).
Post a Comment