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

[Max Rabkin]

On Wed, Jul 15, 2009 at 7:33 PM, Cristiano
Paris<cristiano.paris at gmail.com> wrote:
> 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'm not convinced that this is the "same" program as the Haskell version.

No knot is tied in the Python version. To tie the knot, a data
structure must contain or refer to itself. In the python version, the
function which creates the data structure refers to itself, but many
copies of the data structure are created.

> So my considerations are:
>
> 1 - The Fibonacci generator is not an example of TTK at all and then
> it can be translated to Python.

This indicates that you think tying the knot should be impossible in
Python. In my opinion this is not the case. By my definition of tying
the knot, one needs *either* mutable variables or laziness (at least
in simple cases). Since Python has the former, it is possible to tie
the knot in Python.

To me the simplest example of TTK in Python (not possible in Haskell
because it has an infinite type):

x = []
x.append(x)

(If you try to print this list, one gets [[...]] in the standard REPL
and [<Recursion on list with id=173852620>] in ipython)

--Max