[Haskell-cafe] Python vs Haskell in tying the knot
tom.davie at gmail.com
Fri Jul 17 06:46:34 EDT 2009
On 17 Jul 2009, at 12:41, Cristiano Paris wrote:
> Thank you all for your answers and sorry for the delay I'm writing
> this message but before replying, I wanted to be sure to understand
> your arguments!
> Now, I'm starting to get into this "tying the knot" thing and
> understand why the Haskell version of fib ties the knot while my
> Python version does not. It seems all related to the thunk thing, i.e.
> in the Haskell version the subsequent calls to fib are not actual
> calls because they all refers to the same thunk, which is evaluated
> "on demand".
> Now, to confirm my hypothesis, I wrote a slight different version of
> fib, like follows:
> fib' n = 1:1:(fib' n) `plus` (tail $ fib' n) where plus = zipWith (+)
> i.e. I inserted a fictious argument n in the definition of fib'.
> Now, if I try "take 30 $ fib' 100", it takes significntly longer than
> "take 30 fib": specifically, the latter is instantaneous, while the
> former takes about 5 seconds to complete on my MacBook Pro. Is this an
> evidence that the "tying the knot" process is going on in the first
> More, I've read that a fully lazy language would memoize all functions
> by default: in this case, even fib' would have been tying the knot.
> But this is not the case of Haskell. Am I wrong?
Memoization is not a feature of lazyness. If you can do it in such a
way that you don't waste significant amount of RAM, then it may be a
nice optimisation, and an alternative evaluation strategy, but it
would not be lazy.
More information about the Haskell-Cafe