Динамическое программирование с помощью Data.Map в Haskell?

Question

Я пытаюсь реализовать простой алгоритм dp в Haskell (это для проблемы гипотезы Collatz из Project Euler); здесь является эквивалентом C++:

map<int,int> a; 
int solve(int x) { 
    if (a.find(x) != a.end()) return a[x]; 
    return a[x] = 1 + /* recursive call */; 
} 

Так код, который я написал в Haskell не закончился выглядеть так:

solve :: (Memo, Int) -> (Memo, Int) 
solve (mem, x) = 
case Map.lookup x mem of 
    Just l -> (mem, l) 
    Nothing -> let (mem', l') = {- recursive call -} 
       mem'' = Map.insert x (1+l') mem' 
      in (mem'', 1+l') 

(я думаю, что я просто реализовав государственную монады здесь, но никогда виду, что на данный момент) код, который требует решения пытается найти наибольшее значение, которое он может дать для параметра в большинстве K = 1E6:.

foldl' 
(\(mem,ss) k -> 
    let (mem',x') = solve (mem, k) 
    in (mem', (x', k):ss)) 
(Map.singleton 1 1, [(1,1)]) [2..100000] 

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

x' `seq` (mem', (x',k):ss) 

внутри foldl ', и он вычисляет правильный ответ для K = 1e5. Но это не удается для K = 1e6 (переполнение стека за 12 секунд). Затем я попытался использовать

mem'' `seq` l' `seq` (mem'', 1+l') 

в последней строке решения, но это не имело значения (переполнение стека все еще). Тогда я попытался с помощью

mem'' `deepseq` l' `seq` (mem'', 1+l') 

Это крайне медленно, по-видимому, потому что deepseq прогулки по всей карте ает «», что делает временную сложность этого алгоритма квадратичной вместо п * журнал (п).

Каков правильный способ реализации этого? Я застрял, потому что не могу понять, как сделать все вычисления строгими, и я не совсем уверен, какая часть вычислений дает переполнение стека, но я подозреваю, что это карта. Я мог бы использовать, например, массивы, но я хочу понять, что я делаю неправильно здесь.

Answer 1

Переполнение стека не исчезнет, ​​когда вы используете 32-разрядный целочисленный тип со знаком. Для некоторых начальных значений цепочка покидает 32-битный диапазон и вводит бесконечный цикл отрицательных чисел. Используйте Integer или Int64 или Word64.