Haskell：为什么这个工作 - 一个memoization的例子？

嗨，我从Memoization看下面这个例子：Haskell：为什么这个工作 - 一个memoization的例子？

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)

我只是想知道，为什么这甚至工作，因为对我来说，如果你打电话memoized_fib(n-2)那么你就“创造”一个新的列表，并用它做的事情，在你从它返回后，包含部分结果的列表将会消失？那么memorized_fib(n-1)会不会从中受益呢？

来源

2014-01-05 dorafmon

如果您将定义更改为'memoized_fib n = map fib [0 ..] !!，那么记忆就会打破您考虑的方式！ N'。我不知道害羞，但也许别人可以阐明它。 – hugomg

http://blog.ezyang.com/2011/04/the-haskell-heap/是关于haskell堆的一个很棒的系列，它也可以解释这个（不确定），但即使它不是很好的阅读！ – bennofs

memoized_fib是一个CAF，这是避免创建新的东西的字面常量。没有变数⇒没有东西绑定新东西到⇒没有创建新的东西（简单来说）。

来源

2014-01-05 16:16:53

那么这是否意味着只会有一个'''memized_fib''实例？我如何判断一个函数是否是一个CAF？谢谢:) – dorafmon

是的，只有一个。你检查链接文章中的定义;） –

首先感谢，我的意思是没有进攻，但这里的问题是，我点击进入链接后，我发现我不知道任何关于超级combinator，并点击进入后，我发现我不知道什么是Combinator，然后它被定义为“没有自由变量的函数”，自由变量？从来没有听说过。在学习Haskell之前，大概我错过了最重要的事情，即先学习lambda微积分和范畴论。 – dorafmon

我可以解释missingno的观察，它可以帮助你了解你所看到的行为。了解where子句的用法很重要。

你给出的代码是

memoized_fib = (map fib [0 ..] !!) 
    where fib = ...

这desugars到

memoized_fib = let fib = ... 
       in \n -> map fib [0 ..] !! n

missingno提出以下，这看起来像一个简单的ETA扩张，但它不是！

memoized_fib n = map fib [0 ..] !! n 
    where fib = ...

desugars到

memoized_fib = \n -> let fib = ... 
        in map fib [0 ..] !! n

在前者的情况下，你可以看到，fib结构在后一种情况下fib的memoized_fib调用之间共享而每个时间被重建。

来源

2014-01-05 20:18:52

在第一种情况下，你说'fib'是共享的。为什么分享？你是说'memoized_fib = let fib = ...'在重新调用时不会重新声明'fib'？它重用了先前的“fib”？这是否意味着它等同于在'memoized_fib'函数之外定义'fib'？ – CMCDragonkai

是的，它相当于在'memoized_fib'之外定义'fib'。 –

您显示的代码取决于给定编译器的行为。这里就像汤姆·埃利斯的脱糖建议：

memoized_fib = 
    let fib 0 = 0 
      fib 1 = 1 
      fib n = memoized_fib (n-2) + memoized_fib (n-1) 
    in 
     (map fib [0 ..] !!)

没有保证名单map fib [0..]将被重用，即“共享”。特别是当你像我这样省略类型签名时，将它作为多态定义。

更好地作出这样的名单明确，给它一个名字：

memoized_fib n = 
    let fib 0 = 0 
      fib 1 = 1 
      fib n = g (n-2) + g (n-1) 
      g = (fibs !!) 
      fibs = map fib [0 ..] 
    in 
     g n

这是discussed before。

来源

2014-01-06 14:13:28

Haskell：为什么这个工作 - 一个memoization的例子？

回答

相关问题