Instantly share code, notes, and snippets.

# ericnormand/00 Lazy Fibonacci Sequence.md

Last active May 24, 2022 05:05
Show Gist options
• Save ericnormand/377523537b6f13e34b19cdd56ab48de8 to your computer and use it in GitHub Desktop.

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 `1`s), 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 ....)`

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.

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

(defn fib-seq-10 [& args]
(take 10 (apply fib-seq args)))```

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 *)

### jonasseglare commented May 20, 2022

```(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;
}
}```

### nbardiuk commented May 20, 2022

```(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.

### miner commented May 20, 2022

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

### zugnush commented May 21, 2022

```(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)
;;     ([]
;;      []
;;      [[] []]
;;      [[] [[] []]]
;;      [[[] []] [[] [[] []]]]
;;      [[[] [[] []]] [[[] []] [[] [[] []]]]]
;;      [[[[] []] [[] [[] []]]] [[[] [[] []]] [[[] []] [[] [[] []]]]]]))```

### KingCode commented May 23, 2022

```(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 [] [])) ;;=> ([] [] [[] []] [[] [[] []]] ...)```

### jumarko commented May 24, 2022

@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)
``````