Приветствую,

Я решаю задачи Project Euler на Haskell. Обычно время выполнения задач (при использовании одинаковых алгоритмов)
получаются не намного медленнее чем на C.

Однако с задачей 145 здесь не получилось.
На языке С она решается прямым перебором за меньше минуты. На Haskell же получить результат хотя-бы за пол-часа не вышло.

Код на С:

const int lim = 1000000000;

bool isNumberOk ( int *digits, int digLen ) {
    int *ptr1 = digits;
    int *ptr2 = digits+digLen-1;
    bool carry = false;
    
    if (digits[0] == 0) {
    return false;
    }
    
    for( ; digLen; --digLen ) {
        int tmp = *ptr1++ + *ptr2--;
        if (carry) {
            tmp++;
        }
        carry = tmp >= 10;
        if (tmp % 2 == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int digits[10];
    int cntr = 0;
    for( int i=1; i<lim; ++i ) {
        int j=0;
        int tmp = i;
        for( ;tmp; ++j ) { 
            digits[j] = tmp % 10; 
            tmp /= 10;
        }
        if (isNumberOk(digits,j) ) {
            cntr += 1;
        }    
    }
    printf( "%d\n", cntr );
    return 0;
}

Код на Haskell:

digits :: Int -> [Int]
digits 0 = [0]
digits n = digits' n

digits' 0 = []
digits' n = dg : (digits' rest)
    where
        (rest, dg) = n `divMod` 10

addLists [] [] c = []
addLists (h1:t1) (h2:t2) c = r1 : (addLists t1 t2 c1)
    where
        r1 = h1+h2+c
        c1 = if r1 >= 10 then 1 else 0
        
isOk :: [Int] -> Bool
isOk nDgts
    | head nDgts == 0 || head revN == 0            = False
    | otherwise                                 = all odd $ addLists nDgts revN 0
    where 
        revN = reverse nDgts


makeDgts2 n = tail $ map (dropWhile (==0)) $ makeDgts n 
makeDgts 0 = [[]] 
makeDgts n = [ x:y | x <- [0..9], y <- makeDgts (n-1) ]

prb cndExp = length $ filter isOk  cnds
    where
        cnds = makeDgts2 cndExp

prb2 cands = length $ filter isOk $ map digits cands

problem = prb 8

cands = [1..10^9]
-- problem = prb2 cands

Вопросы: Почему тормозит haskell решение? Что с ним можно сделать с целью ускорения (но оставив алгоритм прямого перебора)?

Александр.

P.S. Да, я знаю, что можно поменять алгоритм. Да, я видел оптимизированный алгоритм на haskell.org.