Я пытаюсь реализовать простой алгоритм dp в Haskell (это для проблемы гипотезы Коллатца из Project Euler); вот эквивалент С++:
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')
(Я думаю, что здесь я просто переопределяю монаду состояния, но пока не обращайте на это внимания.) Код, вызывающийsolve, пытается найти наибольшее значение, которое он может дать для параметра, не превышающего 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 проходит через всю карту mem'', делая временную сложность алгоритма квадратичной, а не n*log(n).
Каков правильный способ реализовать это? Я застрял, потому что не могу понять, как сделать все вычисления строгими, и я не совсем уверен, какая часть вычислений приводит к переполнению стека, но я подозреваю, что это карта. Я мог бы использовать, например, массивы, но я хочу понять, что я здесь делаю неправильно.
