The responses you got on IRC don't necessarily represent Haskell best practice (or even good practice). Most people probably have better things to do than translate random toy programs from C++.

Certain highly stateful algorithms may be difficult to translate into Haskell, in the same way that certain highly structural or lazy algorithms may be difficult to translate to C++.

I'm curious if your time complexity analyses are accurate, given that you (admittedly) did not understand the faster algorithm. You could be getting tripped up by laziness.

In general, I've found that most production Haskell code is quite fast, in both big-O and absolute terms.