lazy-seq

;; The following defines a lazy-seq of all positive numbers.  Note that 
;; the lazy-seq allows us to make a recursive call in a safe way because
;; the call does not happen immediately but instead creates a closure.

user=> (defn positive-numbers 
	([] (positive-numbers 1))
	([n] (lazy-seq (cons n (positive-numbers (inc n))))))
#'user/positive-numbers

user=> (take 5 (positive-numbers))
(1 2 3 4 5)

;; A lazy-seq of Fibonacci numbers (fn = fn-1 + fn-2)
;; The producer function takes exactly two parameters
;; (because we need the last 2 elements to produce a new one)
user=> (defn fib 
         ([]
           (fib 1 1))
         ([a b]
           (lazy-seq (cons a (fib b (+ a b))))))

user=> (take 5 (fib))
(1 1 2 3 5)

;; Another realization
;;    1 2 3 5 8 ... Fibonacci numbers start from the 2nd position
;; +  1 1 2 3 5 ... Fibonacci numbers start from the 1st position
;; =  2 3 5 8 13 ... Fibonacci numbers start from the 3rd position
user=> (def fib
         (cons 1
           (lazy-seq (cons 1 (map + (rest fib) fib)))))

user=> (take 5 fib)
(1 1 2 3 5)

;; It might be easier to think about the producer function as a function
;; that, given element n, produces element n+1 via a recursive call to 
;; itself, wrapped with lazy-seq to delay its execution
;; We might also provide no-argument version of the function that calls 
;; itself for the first element(s) of the sequence being generated.
;; => variant of fibonaci with a no-arg version and using cons first:
(defn sum-last-2 
   ([] (sum-last-2 1 2)) 
   ([n m] (cons n (lazy-seq (sum-last-2 m (+ n m))))))

user=> (take 6 (sum-last-2))
(1 2 3 5 8 13)

;; An example combining lazy sequences with higher order functions
;; Generate prime numbers using trial division.
;; Note that the starting set of sieved numbers should be
;; the set of integers starting with 2 i.e., (iterate inc 2) 
(defn sieve [s]
  (cons (first s)
        (lazy-seq (sieve (filter #(not= 0 (mod % (first s)))
                                 (rest s))))))

user=> (take 20 (sieve (iterate inc 2)))
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)


Sadly (nth (sieve (iterate inc 2)) 10000) results in StackOverflowError ;(

;; Other examples on this page are little too eager to produce the head of collection
;; right away. lazy-seq was introduced to make it possible to postpone any computation
;; until data is needed.
;; While it is not relevant for these simple examples, it could be important
;; for real apps where producing each element is expensive.

;; Here is a demonstration.
;; Let's define a function that prints mysqr when it's called
(defn mysqr [n]
  (println "mysqr")
  (* n n))
;; => #'user/mysqr

;; Now function squares that is adopted from positive-numbers example above
;; Note that lazy-seq is inside of cons
(defn squares
  ([n] (cons (mysqr n) (lazy-seq (squares (inc n))))))
;; => #'user/squares

(def sqrs (squares 1))
;; => mysqr  <-- NOTE THAT mysqr WAS CALLED WHEN WE SIMPLY REQUESTED COLLECTION
;; => #'user/sqrs

(take 1 sqrs)
;; => (1) <-- HERE WE ARE GETTING FIRST ELEMENT THAT WAS CALCULATED BEFORE

;; Now let's redefine 'squares' by wrapping its entire body in lazy-seq:
(defn squares
  ([n] (lazy-seq (cons (mysqr n) (squares (inc n))))))
;; => #'user/squares

;; And when we request the collection:
(def sqrs (squares 1))
;; => #'user/sqrs
;; NOTE THAT mysqr WAS NOT CALLED HERE

(take 1 sqrs)
;; => mysqr <- AND HERE mysqr IS CALLED WHEN FIRST ELEMENT IS ACTUALLY REQUESTED
;; => (1)

;; Compare recursive functions and lazy sequences
;; generate (some) valid parenthesis combinations.
;; (Side note: Everything this generates are valid combinations, but this
;;   doesn't generate all possible valid combinations.) 
;; valid paren combinations for 1 paren - ()
;; valid paren combinations for 2 paren - ()(),(())
;; valid paren combinations for 3 paren - ()()(),()(()),(())(),(()()),((()))

;; given ith item, generate (i+1)th item
(defn next-parens
    [xs]
    (set (mapcat (juxt
                  #(str "()" %)
                  #(str % "()")
                  #(str "(" % ")"))
                 xs)))

;; recursive function to get n paren combinations
;; combinations are recursively calculated on the stack
(defn parens-nth-item
    [n]
    (if (= 0 n)
      #{""}
      (next-parens (parens-nth-item (dec n)))))
user=> (parens-nth-item 3)
#{"(()())" "((()))" "()()()" "()(())" "(())()"}

;; lazy function to get sequence of paren combinations
;; combinations are lazily calculated on the heap
(defn parens-sequence
    [xs]
    (lazy-seq (cons xs (parens-sequence (next-parens xs)))))

user=> (take 3 (parens-sequence #{""}))
(#{"()"} #{"(())" "()()"} #{"(()())" "((()))" "()()()" "()(())" "(())()"})

; Create a finite-length lazy seq
(defn finite-lazy-builder [values]
  (lazy-seq
    ; We need the when-let so the lazy-seq will terminate
    (when-let [ss (seq values)]
      (cons (first values)
            (finite-lazy-builder (next values))))))

(println (finite-lazy-builder [1 2 3 4 5] ))
;=> (1 2 3 4 5)

;;generate a seq by multiplying the first n numbers starting from 1
;;1*1
;;1*2
;;2*3
;;6*4 .....

(defn multiplen
  ([]
   (multiplen 1 1))
  ([total x]
   (let [new-total (* total x)]
     (lazy-seq
      (cons new-total (multiplen new-total (inc x)))))))

;;take the first 5 elements 
(take 5 (multiplen))
;;(1 2 6 24 120)

;;Another realization of factorials
(def factorials
  (lazy-seq
    (cons 1 (map * (iterate inc 2) factorials))))

(take 5 factorials)
;;(1 2 6 24 120)

;; From the "Making Clojure Lazier" docs,
;; here's an example using a step function.

(defn filter
  "Returns a lazy sequence of the items in coll for which
  (pred item) returns true. pred must be free of side-effects."
  [pred coll]
  (let [step (fn [p c]
                 (when-let [s (seq c)]
                   (if (p (first s))
                     (cons (first s) (filter p (rest s)))
                     (recur p (rest s)))))]
    (lazy-seq (step pred coll))))