Haskell version is naive too.

My laptop runs the original in about 3.07s and my improvements bring it down to 1.20s though I think there's room for improvement.

[EDIT] My improvements were actually not the same algorithm as the original's, with algorithm corrections my version is actually slower!