2018-04-10

To be fair with Haskell

Fairy Tales

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.

Note

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

No comments:

Post a Comment