title: How to understand clojure's lazy-seq
body: <p>I'm trying to understand clojure's <code>lazy-seq</code> operator, and the concept of lazy evaluation in general. I know the basic idea behind the concept: Evaluation of an expression is delayed until the value is needed. </p>
  
  <p>In general, this is achievable in two ways:</p>
  
  <ul>
  <li>at compile time using macros or special forms;</li>
  <li>at runtime using lambda functions</li>
  </ul>
  
  <p>With lazy evaluation techniques, it is possible to construct infinite data structures that are evaluated as consumed. These infinite sequences utilizes lambdas, closures and recursion. In clojure, these infinite data structures are generated using <code>lazy-seq</code> and <code>cons</code> forms.</p>
  
  <p>I want to understand how <code>lazy-seq</code> does it's magic. I know it is actually a macro. Consider the following example.</p>
  
  <pre><code>(defn rep [n]
    (lazy-seq (cons n (rep n))))
  </code></pre>
  
  <p>Here, the <code>rep</code> function returns a lazily-evaluated sequence of type <code>LazySeq</code>, which now can be transformed and consumed (thus evaluated) using the sequence API. This API provides functions <code>take</code>, <code>map</code>, <code>filter</code> and <code>reduce</code>.</p>
  
  <p>In the expanded form, we can see how lambda is utilized to store the recipe for the cell without evaluating it immediately.</p>
  
  <pre><code>(defn rep [n]
    (new clojure.lang.LazySeq (fn* [] (cons n (rep n))))) 
  </code></pre>
  
  <ul>
  <li>But <em>how does the sequence API actually work with <code>LazySeq</code></em>?</li>
  <li><em>What actually happens in the following expression</em>?</li>
  </ul>
  
  <p><code>(reduce + (take 3 (map inc (rep 5))))</code></p>
  
  <ul>
  <li><em>How is the intermediate operation <code>map</code> applied to the sequence</em>,</li>
  <li><em>how does <code>take</code> limit the sequence</em> and</li>
  <li><em>how does terminal operation <code>reduce</code> evaluate the sequence</em>?</li>
  </ul>
  
  <p>Also, <em>how do these functions work with either a <code>Vector</code> or a <code>LazySeq</code></em>? </p>
  
  <p>Also, <em>is it possible to generate nested infinite data structures</em>?: list containing lists, containing lists, containing lists... going infinitely wide and deep, evaluated as consumed with the sequence API?</p>
  
  <p>And last question, <em>is there any practical difference between this</em></p>
  
  <pre><code>(defn rep [n]
    (lazy-seq (cons n (rep n))))
  </code></pre>
  
  <p><em>and this</em>?</p>
  
  <pre><code>(defn rep [n]
    (cons n (lazy-seq (rep n))))
  </code></pre>