Skip to content

Instantly share code, notes, and snippets.

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

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

@jonasseglare
Copy link

(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
Copy link

(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
Copy link

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
Copy link

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
Copy link

(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
Copy link

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)

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment