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

Cristiano Paris frodo at theshire.org
Fri Jul 17 06:41:57 EDT 2009


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?

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?

Thank you,

Cristiano


More information about the Haskell-Cafe mailing list