Почему этот простой алгоритм на haskell такой медленный?

Внимание спойлер: это связано с Проблемой 14 из Project Euler.

Следующему коду требуется около 15 с для выполнения. У меня есть нерекурсивное решение на Java, которое выполняется за 1с. Я думаю, что смогу приблизить этот код к этому.

import Data.List

collatz a 1  = a
collatz a x
  | even x    = collatz (a + 1) (x `div` 2)
  | otherwise = collatz (a + 1) (3 * x + 1)

main = do
  print ((foldl1' max) . map (collatz 1) $ [1..1000000])

Я провел профилирование с помощью +RHS -p и заметил, что выделенная память велика и растет по мере роста входных данных. Для n = 100,000 выделяется 1gb(!), для n = 1,000,000 выделяется 13gb(!!!).

Но опять же, -sstderr показывает, что хотя было выделено много байт, общее использование памяти составило 1мб, а производительность была 95%+, так что, возможно, 13гб - это красная строка.

Я могу придумать несколько вариантов:

1. Что-то не так строго, как нужно. Я уже обнаружил. foldl1', но, возможно, мне нужно сделать больше? Можно ли пометить collatz как строгий (имеет ли это вообще смысл?

2. collatz не оптимизирует tail-call. Я думаю, что это должно быть так, но не не знаю способа подтвердить.

3. Компилятор не делает некоторых оптимизаций, которые, как я думаю, он должен делать - напр. только два результата collatz должны быть в памяти в любой момент времени (max и current)

Есть предложения?

Это практически дубликат Почему это выражение на Haskell такое медленное?, хотя я отмечу, что быстрое решение на Java не должно выполнять мемоизацию. Есть ли способы ускорить это, не прибегая к ней?

Для справки, вот мой вывод профилирования:

  Wed Dec 28 09:33 2011 Time and Allocation Profiling Report  (Final)

     scratch +RTS -p -hc -RTS

  total time  =        5.12 secs   (256 ticks @ 20 ms)
  total alloc = 13,229,705,716 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

collatz                        Main                  99.6   99.4


                                                                                               individual    inherited
COST CENTRE              MODULE                                               no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN                                                   1           0   0.0    0.0   100.0  100.0
 CAF                     Main                                                 208          10   0.0    0.0   100.0  100.0
  collatz                Main                                                 215           1   0.0    0.0     0.0    0.0
  main                   Main                                                 214           1   0.4    0.6   100.0  100.0
   collatz               Main                                                 216           0  99.6   99.4    99.6   99.4
 CAF                     GHC.IO.Handle.FD                                     145           2   0.0    0.0     0.0    0.0
 CAF                     System.Posix.Internals                               144           1   0.0    0.0     0.0    0.0
 CAF                     GHC.Conc                                             128           1   0.0    0.0     0.0    0.0
 CAF                     GHC.IO.Handle.Internals                              119           1   0.0    0.0     0.0    0.0
 CAF                     GHC.IO.Encoding.Iconv                                113           5   0.0    0.0     0.0    0.0

И -sstderr:

./scratch +RTS -sstderr 
525
  21,085,474,908 bytes allocated in the heap
      87,799,504 bytes copied during GC
           9,420 bytes maximum residency (1 sample(s))          
          12,824 bytes maximum slop               
               1 MB total memory in use (0 MB lost due to fragmentation)  

  Generation 0: 40219 collections,     0 parallel,  0.40s,  0.51s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time   35.38s  ( 36.37s elapsed)
  GC    time    0.40s  (  0.51s elapsed)
  RP    time    0.00s  (  0.00s elapsed)  PROF  time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   35.79s  ( 36.88s elapsed)  %GC time       1.1%  (1.4% elapsed)  Alloc rate    595,897,095 bytes per MUT second

  Productivity  98.9% of total user, 95.9% of total elapsed

И решение на Java (не мое, взято с форумов Project Euler с удаленной мемоизацией):

public class Collatz {
  public int getChainLength( int n )
  {
    long num = n;
    int count = 1;
    while( num > 1 )
    {
      num = ( num%2 == 0 ) ? num >> 1 : 3*num+1;
      count++;
    }
    return count;
  }

  public static void main(String[] args) {
    Collatz obj = new Collatz();
    long tic = System.currentTimeMillis();
    int max = 0, len = 0, index = 0;
    for( int i = 3; i < 1000000; i++ )
    {
      len = obj.getChainLength(i);
      if( len > max )
      {
        max = len;
        index = i;
      }
    }
    long toc = System.currentTimeMillis();
    System.out.println(toc-tic);
    System.out.println( "Index: " + index + ", length = " + max );
  }
}