Привет.

Решаю задачки на projecteuler.
Возникла проблема с решение задачи 14 на haskell-е (на С++ я её решил без проблем).

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Алгоритм решение прост. Бежим по всем числам от 1 до 10^6 и параллельно заполняем таблицу
(число, длина последовательности). Если в процессе вычисления какой-то последовательности
встретилось число из таблицы, тогда берем длину для него.

Вот код. Работает при nnn = 10000.
При nnn = 1000000 думает очень долго.

module Main
    where

import Array

-- Верхний предел для поиска
nnn ::  Int
nnn = 1000000

-- Опредение функции f
f ::  Integer -> Integer
f 1               = 1
f n | even n      = n `div` 2
    | otherwise   = 3 * n + 1

-- Создаем список [(число, длина последовательности)]
seqlen ::  [(Int, Int)]
seqlen = assocs $ seqlen' (array (1, nnn) $ (1,1):[(a, 0) | a <- [2..nnn]]) [2..(toInteger nnn)]
        where
            seqlen' a [] = a
            seqlen' a (x:xs) = seqlen' na xs
                              where na = accum seq a $ snd $ test a x
            test a x | x > toInteger nnn  = (n + 1, l)
                     | elem == 0          = (n + 1, (fromInteger x, fromInteger n + 1):l)
                     | otherwise          = (toInteger elem, [])
               where (n, l) = test a (f x)
                     elem   = a ! (fromInteger x)


-- Возвращает (число, длина последовательности)
maxseq ::  (Int, Int)
maxseq = foldr (\x y-> if (snd x) > (snd y) then x else y ) (1,1) seqlen 

main ::  IO ()
main = do
         putStrLn (show maxseq)

Можно ускорить?
Заменить везде Integer на Int не получается (некоторые члены последовательности не влезают).

Компилятор GHC 6.4.2.