Haskell'de Data.Map ile dinamik programlama?

Question

Haskell'de basit bir dp algoritması uygulamaya çalışıyorum (bu, Project Euler'dan Collatz varsayım problemi içindir);

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

Yani Haskell yazdı kodu şöyle bakıyor sona erdi:

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

(Ben sadece burada bir devlet monad reimplementing olduğumu düşünüyorum, ama asla burada eşdeğer C++ olduğunu şimdilik bu zihin) en K = 1E6 bir parametre için verebilir büyük değeri bulmak için çalışır çözmek çağıran kod:.

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

yukarıda yazıldığı gibi kod yığın taşması ile başarısız olur. Bu beklenen bir şeydi, anladım, çünkü çok büyük bir değersiz küçücük bir şey inşa ediyor. Bu yüzden 'foldl içeride

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

kullanarak denedim ve K = 1E5 için doğru cevabı hesaplar. Ancak bu, K = 1e6 (12 saniyede yığın taşması) için başarısız olur. Daha sonra, son çözüm hattında

kullanmayı denedim, ancak bu fark yaratmadı (yığın taşması hala devam ediyor). Sonra bu deepseq yerine n * log (n) algoritmanın zaman karmaşıklığı kuadratik hale Mem '' tüm harita üzerinden yürür muhtemelen çünkü son derece yavaş

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

kullanarak çalıştı.

Bunu uygulamak için doğru yol nedir? Takılıyorum çünkü tüm hesaplamayı nasıl katı hale getireceğimi anlayamıyorum ve hesaplamaların hangi kısmının yığının taşmasını sağladığından emin değilim, ancak haritanın olduğundan şüpheleniyorum. Diziler kullanabilirdim, ama burada ne yapıyorum anlamak istiyorum.

Answer 1

32 bit imzalı bir tamsayı türü kullanırken yığın taşması gitmeyecek. Bazı başlangıç ​​değerleri için, zincir 32-bit aralığı bırakır ve sonsuz sayıda negatif sayıya girer. Integer veya Int64 veya Word64 kullanın.