Ok, I made some changes, and it does the first part in a 0.1s now, and the second part in 7s. However the code looks very much like an imperative language now. There is a loop over a list inside which we do things, and use the State Monad to change things.
The result is still slower than Python and less readable now.