哈斯克尔如何存档记忆

我试图从项目欧拉解决＃15，这是我的第一个解决方案进口Data.List模块哈斯克尔如何存档记忆

type Location = (Int,Int) 

boardX = 20 
boardY = 20 

stepBack :: Location -> [Location] 
stepBack (x,y) = [(x-1,y), (x,y-1)] 

legalStep :: Location -> Bool 
legalStep (x,y) = x >= 0 && y >= 0 

iteractStep :: Int -> [[Location]] 
iteractStep 0 = [[(boardX, boardY)]] 
iteractStep n = [x:y|y <- iteractStep (n-1), x<- stepBack (head y),  legalStep x] 

main :: IO() 
main = putStrLn $ show $ length $ iteractStep (boardX + boardY)

这是很慢的，我觉得有这么多子问题重新计算的，我试图记住子问题的答案，然后我发现这个例子：

memoized_fib :: Int -> Integer 
    memoized_fib = (map fib [0 ..] !!) 
    where fib 0 = 0 
      fib 1 = 1 
      fib n = memoized_fib (n-2) + memoized_fib (n-1)

我尝试在ghci中，我发现它实际上记住子问题的结果，我不明白这是如何代码可以记忆结果，它看起来像

map fib [0 ..]

是全局的，但我认为它是方法范围（只存在于每个方法调用），为什么它可以记忆结果？

来源

2017-02-08 wei li

[Haskell中的Memoization？]（http://stackoverflow.com/questions/3208258/memoization-in-haskell） –

memoized_fib可以工作，因为它最初只是在map fib [0..]（这是懒惰，按需呼叫）中创建了thunk。在随后的调用中，将计算列表中的更多fib值，并且同时每个调用通过索引到列表（!!）来查找fib值。

没有列表每次调用fib会作出另外两个呼叫fib这又将使两个电话等。在算法方面这改变距离O fib（N^2）到O（N）。

没有看过项目欧拉问题，我建议你先尝试另一个数据结构。在你的情况下，你应该尝试vector或者array。这些都比你当前使用的列表快得多，而且实际上它是一个链表。

您也可以通过将您的董事会表示更改为board :: [Int]获得一点点。我们直觉地认为电路板具有两个维度，但是它很容易实现为列表而不是列表。（这个我记得在PAIP的一章中）

对于其他问题请记住containers和unordered-containers。

来源

2017-02-08 03:53:44 Mikkel

得到它，memoized_fib就像fibs = 1：1：zipWith（+）fibs（尾纤），最终结果是一个列表。我有另一个问题，我只使用列表中的fmap和头部操作，为什么向量快于列表？ –

对于'头'我不认为它会产生很大的差异。 AFAIK一个向量在内存中保持元素相邻，其中链接列表具有元素之间的指针，所以任何遍历的例如'vector'上的'fmap'应该快得多。 – Mikkel

刚刚在[Haskell学校]（https://www.schoolofhaskell.com/user/commercial/content/vector#efficiency）中找到了列表和向量之间效率差异的一个很好的解释， – Mikkel

哈斯克尔如何存档记忆

回答

相关问题