Project Euler #14 (Longest Collatz Sequence) in Haskell
The main reason why this is slow is that every update to your array is making a new copy of it. The version you linked to on the wiki avoids this problem by using a boxed array instead, which allows you to define the array in one go and let lazy evaluation take care of evaluating the elements in an appropriate order and modifying the array behind the scenes.

A boxed array is less memory efficient since it's basically an array of pointers to individually-allocated integers, but for the size of this problem it's not too bad. If you want to use an unboxed array for improved space efficiency, you would probably want to use a mutable one in the ST monad instead. There's an example of how how to do that in an old answer of mine on Stack Overflow.



Regarding your second attempt:

First off, let's get this code to compile.


Since the else branch of this if is returning a statement in the ST monad, so must the then branch. A quick fix is to add return:

v &lt;- if n' &gt; n then return 0 else (readArray seqLengths n')
                    ^^^^^^

And there shouldn't be a $ when passing the comparison function
to maximumBy here:

main = print $ fst $ maximumBy  (comparing snd) $ assocs $ getCollatzSequenceLengthUpto 1000000
                               ^



With those small changes, it compiles and it runs in about 4 seconds on my netbook. Not too bad! 

However, it's a bit messy, let's see if we can fix that. First of all, let's reduce that ball of nested if's.


We can get rid of the outermost if by using a separate equation for when n' is 1:

compute l s 1  = return (l+1, reverse s)

The two branches of the innermost if are almost the same. We can move the if inside to the only place they differ. Also do out &lt;- compute ...; return out is the same as just compute ...:

compute l s n' = do
    v &lt;- if n' &gt; n then return 0 else readArray seqLengths n'
    if v &gt; 0
        then return (l+v, reverse s)
        else compute (l+1) (n':s) (if even n' then n' `div` 2 else (3*n'+1))



Here is the full working code after these adjustments. I still think the way
you're using a list to deal with the updates is somewhat complicated, but I think fixing that in a satisfactory way would require more substantial changes to your algorithm, so I've left it the way it is.

import Control.Monad (forM_)
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Data.Int (Int64)
import Data.List (maximumBy)
import Data.Ord (comparing)

getCollatzSequenceLengthUpto :: Int64 -&gt; (UArray Int64 Int64)
getCollatzSequenceLengthUpto n = runSTUArray $ do
    seqLengths &lt;- newArray (1,n) 0
    forM_ [1..n] $ \i -&gt; do
        let compute l s 1  = return (l+1, reverse s)
            compute l s n' = do
                v &lt;- if n' &gt; n then return 0 else readArray seqLengths n'
                if v &gt; 0
                    then return (l+v, reverse s)
                    else compute (l+1) (n':s) (if even n' then n' `div` 2 else (3*n'+1))
        (l, u) &lt;- compute 0 [] i
        forM_ (filter (\(n',_) -&gt; n' &lt;= n) $ zip u [l,l-1..]) $ \(ix, e) -&gt; do
            writeArray seqLengths ix e 
    return seqLengths

main = print $ fst $ maximumBy (comparing snd) $ assocs $ getCollatzSequenceLengthUpto 1000000