Damien Katz

You can have cycles in data structures, no problem:

  ones = [1 : ones]

That is an infinite list of ones -- a cyclic data structure. (This is in a purely functional language that I am writing.)

What makes you think you can't? You do have to define the whole thing "all at once", but that's not too hard if you use the right model.

Typically, one would expect that in an assignment the right-hand-side is evaluated in the "parent" environment, allowing one to increment a counter with something like this:

  x = x + 1

But in a purely functional language, you don't have assignment, you have definition. So, in my language at least, the above will fail (if you actually try to use the value... lazy evaluation, you know), because it will loop forever adding ones, trying to compute the value of x.

So what I did was have the right-hand-side evaluate in the "child" environment, the one in which the left-hand-side is defined. This doesn't conflict in any way with being "purely functional".

Having said all that... I know the feeling! :-)

Not true if you have lazy evaluation, I'd say.

See http://www.haskell.org/hawiki/TyingTheKnot

And while my language does have lazy evaluation (why would you go purely functional and not have it??), I don't think it's actually a prerequisite. My first example with the ones... you don't need lazy evaluation for that. You do for more interesting examples (infinite list of primes or something), but those aren't cyclic. In fact, it's precisely the cyclic data structures that don't have to be defined lazily. :)

I still maintain that the trick is "defining all at once", whether lazily or not.