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

[Cristiano Paris]

Hi,

as pointed out in this list, it seems that a "tying the knot" example
would be the one better explaining the power of Haskell's
lazy-by-default approach against Python+Iterator's approach to
laziness.

So, in these days I'm trying to grasp the meaning of this "tying the
knot" concept which seems to be quite hard to understand for me (at
least as much as Monads and Delimited Continuations were).
Specifically, I was looking for a very basic example of TTK and came
up with this implementation of Fibonacci (again!) which might possibly
be a TTK-flavored way for generation:

fib = 1:1:fib `plus` (tail fib) where plus = zipWith (+)

Of course, this was something I already encountered when exploring the
Y-combinator. Anyhow, I tried to translate this implementation to
Python using Iterators and this is what I wrote:

def fib():
  yield 1
  yield 1

  p = plus(fib(),tail(fib()))

  while True:
    yield p.next()

def plus(x,y):
  while True:
    yield x.next() + y.next()

print take(5,fib())

I've omitted the implementation for tail() and take() for brevity.
Apart from the iterator machinery, this is an direct translation of
the Haskell's fib implementation. More, it's quite modular because fib
lives by itself and is composed with take to get the final result. The
only caveat in the Python code is that it maintains an O(n^2)
Iterator's states, thus making it a very poor implementation.

So my considerations are:

1 - The Fibonacci generator is not an example of TTK at all and then
it can be translated to Python.
2 - The Fibonacci generator is a too simple example of TTK, easy to be
translated to Python.
3 - The O(n^2) state caveat is THE point making the difference between
Haskell and Python, for which Haksell is much more efficient that
Python while remaining very expressive and idiomatic (but that may not
be the case for other TTK examples).

I'm trying to implement myself the doubly linked list example from the
Wikipage, which is "certified" to be a TTK example, but I'd like to
have your comments on this.

Thank you.

Cristiano