How to create a lazy-seq generating, anonymous recursive function in Clojure?

Question

Edit: I discovered a partial answer to my own question in the process of writing this, but I think it can easily be improved upon so I will post it anyway. Maybe there's a better solution out there?

I am looking for an easy way to define recursive functions in a let form without resorting to letfn. This is probably an unreasonable request, but the reason I am looking for this technique is because I have a mix of data and recursive functions that depend on each other in a way requires a lot of nested let and letfn statements.

I wanted to write the recursive functions that generate lazy sequences like this (using the Fibonacci sequence as an example):

(let [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  (take 10 fibs))

But it seems in clojure that fibs cannot use it's own symbol during binding. The obvious way around it is using letfn

(letfn [(fibo [] (lazy-cat [0 1] (map + (fibo) (rest (fibo)))))]
  (take 10 (fibo)))

But as I said earlier this leads to a lot of cumbersome nesting and alternating let and letfn.

To do this without letfn and using just let, I started by writing something that uses what I think is the U-combinator (just heard of the concept today):

(let [fibs (fn [fi] (lazy-cat [0 1] (map + (fi fi) (rest (fi fi)))))]
  (take 10 (fibs fibs)))

But how to get rid of the redundance of (fi fi)?

It was at this point when I discovered the answer to my own question after an hour of struggling and incrementally adding bits to the combinator Q.

(let [Q (fn [r] ((fn [f] (f f)) (fn [y] (r (fn [] (y y))))))
      fibs (Q (fn [fi] (lazy-cat [0 1] (map + (fi) (rest (fi))))))]
  (take 10 fibs))

What is this Q combinator called that I am using to define a recursive sequence? It looks like the Y combinator with no arguments x. Is it the same?

(defn Y [r] 
  ((fn [f] (f f)) 
   (fn [y] (r (fn [x] ((y y) x))))))

Is there another function in clojure.core or clojure.contrib that provides the functionality of Y or Q? I can't imagine what I just did was idiomatic...

Answer 1

letrec

I have written a letrec macro for Clojure recently, here's a Gist of it. It acts like Scheme's letrec (if you happen to know that), meaning that it's a cross between let and letfn: you can bind a set of names to mutually recursive values, without the need for those values to be functions (lazy sequences are ok too), as long as it is possible to evaluate the head of each item without referring to the others (that's Haskell -- or perhaps type-theoretic -- parlance; "head" here might stand e.g. for the lazy sequence object itself, with -- crucially! -- no forcing involved).

You can use it to write things like

(letrec [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  fibs)

which is normally only possible at top level. See the Gist for more examples.

As pointed out in the question text, the above could be replaced with

(letfn [(fibs [] (lazy-cat [0 1] (map + (fibs) (rest (fibs)))))]
  (fibs))

for the same result in exponential time; the letrec version has linear complexity (as does a top-level (def fibs (lazy-cat [0 1] (map + fibs (rest fibs)))) form).

iterate

Self-recursive seqs can often be constructed with iterate -- namely when a fixed range of look-behind suffices to compute any given element. See clojure.contrib.lazy-seqs for an example of how to compute fibs with iterate.

clojure.contrib.seq

c.c.seq provides an interesting function called rec-seq, enabling things like

(take 10 (cseq/rec-seq fibs (map + fibs (rest fibs))))

It has the limitation of only allowing one to construct a single self-recursive sequence, but it might be possible to lift from it's source some implementation ideas enabling more diverse scenarios. If a single self-recursive sequence not defined at top level is what you're after, this has to be the idiomatic solution.

combinators

As for combinators such as those displayed in the question text, it is important to note that they are hampered by the lack of TCO (tail call optimisation) on the JVM (and thus in Clojure, which elects to use the JVM's calling conventions directly for top performance).

top level

There's also the option of putting the mutually recursive "things" at top level, possibly in their own namespace. This doesn't work so great if those "things" need to be parameterised somehow, but namespaces can be created dynamically if need be (see clojure.contrib.with-ns for implementation ideas).

final comments

I'll readily admit that the letrec thing is far from idiomatic Clojure and I'd avoid using it in production code if anything else would do (and since there's always the top level option...). However, it is (IMO!) nice to play with and it appears to work well enough. I'm personally interested in finding out how much can be accomplished without letrec and to what degree a letrec macro makes things easier / cleaner... I haven't formed an opinion on that yet. So, here it is. Once again, for the single self-recursive seq case, iterate or contrib might be the best way to go.

Answer 2

fn takes an optional name argument with that name bound to the function in its body. Using this feature, you could write fibs as:

(def fibs ((fn generator [a b] (lazy-seq (cons a (generator b (+ a b))))) 0 1))