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!