Robert Greayer wrote:

Isn't tying the knot (in the way 'fib' does) straightforward with closures a la Python/Ruby/Smalltalk (without mutation)? Even in a syntactically clumsy language like Java, a tying-the-knot implementation equivalent to the canonical Haskell one is not difficult, e.g.

static L fibs = new L() { public int head() { return 1; } public L tail() { return new L() { public int head() { return 1; } public L tail() { return new L() { public int head() { return fibs.head() + fibs.tail().head(); } public L tail() { return zip(fibs.tail(), fibs.tail().tail()); } }; } }; } };

Given a definition of list L and zip...

interface L { int head(); L tail(); } static L zip(final L l0, final L l1) { return new L() { public int head() { return l0.head() + l1.head(); } public L tail() { return zip(l0.tail(), l1.tail()); } }; }

Are you sure there's not a super-linear time complexity hidden in there? Unless Java compilers are clever enough to memoize this kind of code, I think each subsequent call to the head() will just recurse all the way down to the bottom an exponentially increasing number of times. To simulate laziness, I think you would need to actually store fibs *as data* somewhere, and you'd presumably need to simulate the process of replacing a thunk with its value on its first evaluation. In python, for example: class value: def __init__(self, *value): self.value = value def __call__(self): return self.value class thunk: def __init__(self, susp): self.susp = susp def __call__(self): try: return self.result except: self.result = self.susp() del self.susp return self.result def tail(xs): x,r = xs() return r def zipWithPlus(xs,ys): x,xr = xs() y,yr = ys() return x+y, thunk(lambda: zipWithPlus(xr,yr)) fibs = value(0, value(1, thunk(lambda: zipWithPlus(fibs, tail(fibs))))) def fibgen(): g = fibs while True: x,g = g() yield x Needless to say: I prefer the Haskell!

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