[Haskell-cafe] Python vs Haskell in tying the knot

[Thomas Davie]

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
> version?

That's correct

> 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.

Bob