title: How to create a lazy-seq generating, anonymous recursive function in Clojure?
body: <p><strong>Edit</strong>: 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?</p>
  
  <p>I am looking for an easy way to define recursive functions in a <code>let</code> form without resorting to <code>letfn</code>. 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 <code>let</code> and <code>letfn</code> statements. </p>
  
  <p>I wanted to write the recursive functions that generate lazy sequences like this (using the Fibonacci sequence as an example):</p>
  
  <pre><code>(let [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
    (take 10 fibs))
  </code></pre>
  
  <p>But it seems in clojure that <code>fibs</code> cannot use it's own symbol during binding. The obvious way around it is using <code>letfn</code></p>
  
  <pre><code>(letfn [(fibo [] (lazy-cat [0 1] (map + (fibo) (rest (fibo)))))]
    (take 10 (fibo)))
  </code></pre>
  
  <p>But as I said earlier this leads to a lot of cumbersome nesting and alternating <code>let</code> and <code>letfn</code>. </p>
  
  <p>To do this without <code>letfn</code> and using just <code>let</code>, I started by writing something that uses what I think is the U-combinator (just heard of the concept today):</p>
  
  <pre><code>(let [fibs (fn [fi] (lazy-cat [0 1] (map + (fi fi) (rest (fi fi)))))]
    (take 10 (fibs fibs)))
  </code></pre>
  
  <p>But how to get rid of the redundance of <code>(fi fi)</code>? </p>
  
  <p>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.</p>
  
  <pre><code>(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))
  </code></pre>
  
  <p>What is this <code>Q</code> combinator called that I am using to define a recursive sequence? It looks like the Y combinator with no arguments <code>x</code>. Is it the same?</p>
  
  <pre><code>(defn Y [r] 
    ((fn [f] (f f)) 
     (fn [y] (r (fn [x] ((y y) x))))))
  </code></pre>
  
  <p>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...</p>