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

Я пытаюсь реализовать простой алгоритм dp на Haskell (это для задачи гипотезы Коллатца из 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')

(Я думаю, что здесь я просто переопределяю монаду состояния, но пока не обращайте на это внимания. )Код, вызывающий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).

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