Programmazione dinamica con Data.Map in Haskell?

Question

Sto cercando di implementare un semplice algoritmo di dp in Haskell (questo è per il problema di congettura di Collatz da Project Euler); qui è l'equivalente C++:

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

Così il codice che ho scritto in Haskell ha finito per assomigliare a questo:

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

(penso che sto solo reimplementare una monade stato qui, ma mai presente che per il momento) il codice che chiama risolvere cerca di trovare il valore più grande che può dare per un parametro al massimo 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] 

il codice, come scritto sopra non riesce con un overflow dello stack. Questo è prevedibile, lo capisco, perché costruisce un thunk non molto grande e non valutato. Così ho provato a usare

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

all'interno di foldl ', e calcola la risposta giusta per K = 1e5. Ma questo fallisce per K = 1e6 (overflow dello stack in 12 secondi). Poi ho provato a usare

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

nell'ultima riga di risoluzione, ma questo non ha fatto differenza (stack overflow ancora). Poi ho provato ad utilizzare

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

Questo è estremamente lento, presumibilmente perché deepseq passeggiate attraverso l'intera mappa mem '', rendendo il tempo la complessità dell'algoritmo quadratica al posto di n * log (n).

Qual è il modo corretto di implementarlo? Sono bloccato perché non riesco a capire come rendere rigoroso l'intero calcolo, e non sono del tutto sicuro quale parte del calcolo superi lo stack, ma sospetto che sia la mappa. Potrei usare, ad esempio, gli array, ma voglio capire cosa sto facendo male qui.

Answer 1

L'overflow dello stack non scompare quando si utilizza un tipo intero con segno a 32 bit. Per alcuni valori iniziali, la catena lascia intervallo a 32 bit e inserisce un ciclo infinito di numeri negativi. Utilizzare Integer o Int64 o Word64.