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

[Matthew Brecknell]

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!