I'm not sure, maybe it's just the overhead of having so many function calls and Set accesses? My guess is that the Haskell one could be made quite a bit more efficient if you used a low-level mutable array.

To add another benchmarking data point, I have a simple sieve of Eratosthenes written in Nim using an array that can generate 10,000 primes in less than a millisecond.