Matthew Brecknell matthew at brecknell.net
Thu Jul 16 01:27:40 EDT 2009

```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 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 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!

```