469 Eric Normand Newsletter

00 Lazy Fibonacci Sequence.md

Lazy Fibonacci Sequence

Ah, the ubiquitous example of recursive functions. Well, this is not your traditional fibonacci sequence exercise.

We all know that the fibonacci sequence is defined as:

(fib 0) ;=> 1
(fib 1) ;=> 1
(fib n) ;=> (+ (fib (dec n)) (fib (dec (dec n))))

And we know we could generate it forward, one element at a time, in a lazy fashion. That is your first task!

(fib-seq) ;=> (1 1 2 3 5 8 13 ....) lazily generated because it's infinite

But we could parameterize some of the things in the definition, like the first and second elements (both 1s), and the operation to apply (+). We should be able to pass them as arguments:

(fib-seq + 1 1) ;=> (1 1 2 3 5 8 13 ....)

That's your second task.

Your third task is more interesting: We don't have to limit ourselves to addition. In fact, we should be able to use any function that takes two arguments of type T and returns a value of T (closure property). Your task is to generate the first 10 elements of the sequence (use take) for each of these combinations:

(fib-seq str "X" "O")
(fib-seq * 1 1)
(fib-seq * 1 2)
(fib-seq * 1 -1)
(fib-seq vector [] [])

Thanks to this site for the problem idea, where it is rated Expert in Java. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://ericnormand.me/newsletter

(defn fib-seq
  ([] (fib-seq + 1 1))
  ([f a b] (iterator-seq (FibIter. f a b))))

with FibIter being

import java.util.Iterator;
import clojure.lang.IFn;

public class FibIter implements Iterator {
    private IFn _f;
    private Object _a;
    private Object _b;
    
    public FibIter(IFn f, Object a, Object b) {
        _f = f;
        _a = a;
        _b = b;
    }

    public Object next() {
        Object x = _a;
        _a = _b;
        _b = _f.invoke(x, _b);
        return x;
    }

    public boolean hasNext() {
        return true;
    }
}

(defn fib-seq
  ([]
   (fib-seq + 1 1))
  ([f a b]
   (cons a (lazy-seq (fib-seq f b (f a b))))))

If the lazy-seq call is around nested fib-seq insead of cons the take 10 works, it overflows on take 11. As I understand the lazy-seq macro does not evaluate the body and we delay the evaluation of (f a b) for one step.

(defn fib-seq
  ([] (fib-seq + 1 1))
  ([op x y]
   (map #(% 0) (iterate (fn [[a b]] [b (op a b)]) [x y]))))

(defn fib-elem
  [op fst snd n]
  (let [part (partial fib-elem op fst snd)]
    (condp = n
      0 fst
      1 snd
      (op (part (dec (dec n))) (part (dec n))))))

(defn fib-seq
  [op fst snd]
  (map (partial fib-elem op fst snd) (range)))

;; solutions/tests
(map #(->> %
           (apply fib-seq)
           (take 7)) [[+ 1 1]
                      [str "x" "o"]
                      [* 1 1]
                      [* 1 2]
                      [* 1 -1]
                      [vector [] []]])
;; => ((1 1 2 3 5 8 13)
;;     ("x" "o" "xo" "oxo" "xooxo" "oxoxooxo" "xooxooxoxooxo")
;;     (1 1 1 1 1 1 1)
;;     (1 2 2 4 8 32 256)
;;     (1 -1 -1 1 -1 -1 1)
;;     ([]
;;      []
;;      [[] []]
;;      [[] [[] []]]
;;      [[[] []] [[] [[] []]]]
;;      [[[] [[] []]] [[[] []] [[] [[] []]]]]
;;      [[[[] []] [[] [[] []]]] [[[] [[] []]] [[[] []] [[] [[] []]]]]]))

(defn fib-seq 
  ([] (fib-seq + 1 1))
  ([f init1 init2]
   (cons init1 
         (lazy-seq (fib-seq f init2 
                            (f init1 init2))))))

(take 10 (fib-seq str "X" "O")) ;;=> ("X" "O" "XO" "OXO"...)
(take 10 (fib-seq * 1 1))  ;;=> (1 1 1 1 1 1 1 1 1 1)
(take 10  (fib-seq * 1 2)) ;;;=> (1 2 2 4 8 32 256 8192 2097152 17179869184)
(take 10 (fib-seq * 1 -1)) ;;=> (1 -1 -1 1 -1 -1 1 -1 -1 1)
(take 10 (fib-seq vector [] [])) ;;=> ([] [] [[] []] [[] [[] []]] ...)

@mchampine

Well dang, I was about to post my solution but it is identical to steffan's except I called the function arg "op" instead of f. Btw, (fib-seq * 1 2) overflows on the 10th value, so I had to use *' (the auto-promote version of *)

I've got a very similar solution too and I had a problem with overflows even when taking only first 9 elements:

(defn fib-seq [op fst snd]
  ;; Note: computing `(op fst snd)` in the let block makes it fail way too early with long overflow
  (let [nxt (op fst snd)]
    (lazy-seq (cons fst (fib-seq op snd nxt)))))

After I removed let and inlined the operation it works ok even with 10 elements:

(defn fib-seq [op fst snd]
  (cons fst (lazy-seq (fib-seq op snd (op fst snd)))))
(take 10 (fib-seq * 1 2))
;; => (1 2 2 4 8 32 256 8192 2097152 17179869184)

See https://github.com/jumarko/clojure-experiments/blob/master/src/clojure_experiments/purely_functional/puzzles/0469_fibseq.clj#L1