Programación dinámica con Data.Map en Haskell?

Question

Estoy tratando de implementar un algoritmo dp simple en Haskell (esto es para el problema de conjeturas Collatz del Proyecto Euler); aquí es el C++ equivalente:

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

Así que el código que he escrito en Haskell terminó pareciéndose a esto:

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') 

(creo que sólo estoy reimplementar una mónada estado aquí, pero nunca importa que por el momento) el código que llama a resolver los intentos para encontrar el valor más grande que puede dar para un parámetro, como máximo, 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] 

el código como está escrito anterior falla con un desbordamiento de pila. Esto es de esperar, lo entiendo, porque construye un gran golpe no evaluado. Así que traté de usar

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

dentro de foldl ', y calcula la respuesta correcta para K = 1e5. Pero esto falla para K = 1e6 (desbordamiento de pila en 12 segundos). Luego traté de usar

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

en la última línea de resolver, pero esto no hizo ninguna diferencia (todavía desbordamiento de la pila). A continuación, he intentado usar

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

Esto es extremadamente lento, presumiblemente porque deepseq paseos por todo el mapa mem '', lo que hace tiempo la complejidad del algoritmo cuadrática en lugar de n * log (n).

¿Cuál es la forma correcta de implementar esto? Estoy atascado porque no puedo descifrar cómo hacer que todo el cálculo sea estricto, y no estoy seguro de qué parte de la computación da el desbordamiento de la pila, pero sospecho que es el mapa. Podría usar, por ejemplo, arreglos, pero quiero entender lo que estoy haciendo mal aquí.

Answer 1

El desbordamiento de pila no desaparecerá mientras utilice un tipo de entero con signo de 32 bits. Para algunos valores iniciales, la cadena deja el rango de 32 bits e ingresa un bucle infinito de números negativos. Use Integer o Int64 o Word64.