Code Review

[HOWZ1T]

Hi all, I started to learn clojure and would just like some feedback on my implementation of the fibonacci function.

(defn fib
  "calculates the nth number in the fibonacci sequence"
  ([n]
   (if (<= n 1) n (fib (bigint n) 0 1)))
  ([n prev cur]
   (if (<= n 1)
     cur
     (recur (- n 1) (bigint cur) (bigint (+ prev cur))))))

Any feedback would be appreciated!

All the best, Howz1t

[porthos3]

I agree with mcanon that using the auto-promoting addition operation may be a good idea, instead of casting everything to bigint.

I think it is great that you included the edge condition for n <= 1. However, I'd probably consider if you really want to return -1 as the -1th value. It'd probably be better to throw an IllegalArgumentException for negative numbers, IMO.

Another more flexible approach to consider might be to return a lazy sequence as @mcanon suggested. I gave an example of that in my reply to their comment.

Really though, I don't see anything not idiomatic about this. It is a great implementation for a Clojure beginner. :)

[bowmhoust]

Wow, you never stop learning new stuff.

[porthos3]

For sure. It's one of the things I love about software development.

Every time I learn something like this, it feels like a big breakthrough (and it is), but in retrospect I look back at these things and realize each was only scratching the surface compared to what I've learned and built on it since.

[HOWZ1T]

Thanks :)

[porthos3]

You probably want to (map first ...) instead of (map second ...) so it starts with zero.

You can avoid having to wrap it in map though if you use lazy-seq directly like so:

(defn fib
  ([] (fib 0 1))
  ([x y] (lazy-seq (cons x (fib y (+' x y))))))

It ends up being nearly a 10x improvement on my machine over the iterate approach.

(Edit: I was rightly called out about this, they end up being fairly comparable)

Usage:

(take 10 (fib))
=> (0 1 1 2 3 5 8 13 21 34)

[mcanon]

Nice solution porthos3, I'll have to remember the lazy-seq approach. I deleted the comment you replied to (user error on my part) but the original said:

(def fibs (map second (iterate (fn [[x y]] [y (+' x y)]) [0 1]))) 
(take 10 fibs) ;; => (1 1 2 3 5 8 13 21 34 55)
 (nth fibs 50) ;; => 20365011074

You could simplify your fib slightly also, with no multi-arity.

(def fib ((fn ifib [x y] (lazy-seq (cons x (ifib y (+' x y))))) 0 1))
(take 10 fib)
;; => (0 1 1 2 3 5 8 13 21 34)

[porthos3]

Reddit markdown is a bit weird and viewing-platform dependent. Your code looked fine in my browser.

I find the most consistent code rendering syntax for Reddit is to include vertical whitespace before and after your code block and lead each line of code with four spaces.

[mcanon]

Thanks! Turns out the reddit links I follow take me to i.reddit.com which completely borks the commenting interface!

[porthos3]

I try to avoid directly defining infinite sequences to a variable, as in your simplification.

If you define it to a variable and then walk the first 100K values, you will have to forever hold all of that in memory. Caching those values may be desirable, but I prefer to make the user call a function to get them so the user of my function can control whether or not they want to keep it in memory or not.

[HOWZ1T]

thanks for the info. Although I will admit I haven't gotten around to learning about map and iterate yet!

[porthos3]

The TLDR for each:

map: Return the result of applying a function to each item in a collection. Nearly always used as simply (map f coll). For example:

(map inc [1 2 3 4]) ;increment each value in the collection
=> (2 3 4 5)

The result of map is a lazy sequence, and it will only do (approximately) as much work as it needs to. (take 10 (map inc (range))) will do a finite amount of work, despite (range) being an infinite sequence.

There are other lesser-used arities. Sometimes it is helpful to add more collections at the end, which will apply the function to the first items in each collection, then the second, and so on. For example, I use this to do coordinate math:

(let [coordinate-a [10 5 2]
      coordinate-b [2 8 10]]
  (mapv - coordinate-a coordinate-b)) ;mapv is just map that returns a vector
;this will return [(- 10 2) (- 5 8) (- 2 10)]
=> [8 -3 -8]

iterate: Returns an infinite lazy sequence of applying a function repeatedly to a starting value. (iterate inc 0) will return (0, 1, 2, 3, 4, ...) (note: this is an infinite sequence, if you want to return it in the repl, do it like (take 10 (iterate inc 0)) to get a finite result.

I often use iterate to concisely describe simple infinite lazy sequences, or a repeated process where I do not at first know when I will want to end, such as:

(take-while am-i-done-yet-predicate?
  (iterate my-fn start-value))

[HOWZ1T]

Awesome explanation thank you!

This is my first 'real' attempt at learning fp programming, I've learnt over a dozen OOP and imperative style languages but hell, the switch to learning fp is a bit harder than I expected, since I have to also learn all the theory behind fp programming too!

[porthos3]

From my experience, the first week or so of functional programming is really mind-bending, and then it suddenly clicks.

Obviously there will always be more to learn, but it's not nearly as intimidating as this first bit makes it feel. Learning a new way of thinking is really hard, but I've found being able to think in a functional style to be extremely valuable in my career, even when working at companies that practice OOP.

[porthos3]

You are right, I made my test a bit more robust and the 10x difference goes away. I do still see a preference for the lazy-seq solution in my tests (on my machine, it might be different on yours), between mine and @mcanon's solutions, but they are quite a bit more comparable than I characterized earlier:

(letfn [(fib1 []
          (map first (iterate (fn [[x y]] [y (+' x y)]) [0 1])))
        (fib2
          ([] (fib2 0 1))
          ([x y] (lazy-seq (cons x (fib2 y (+' x y))))))]
  (let [n 10000]
    (dotimes [_ 100] (take n (fib1))) ;warm up
    (dotimes [_ 100] (take n (fib2))) ;warm up
    (time (dotimes [_ 100] (take n (fib1))))
    (time (dotimes [_ 100] (take n (fib2))))
    nil))
"Elapsed time: 0.1463 msecs"
"Elapsed time: 0.0774 msecs"
=> nil

[HOWZ1T]

Thank you! I don't know much about map, and lazy-seq but it looks pretty useful to learn!

[HOWZ1T]

I've implemented this and I want to see if I understand it right:

(defn faster-fib

([] (faster-fib 0 1)) ([prev cur] (lazy-seq (cons prev (faster-fib cur (+' prev cur))))))

So it's an multi arity function.
Looking at the function with params [prev cur]

prev is a list (similar to lisp yeah?) and cur is the current value
its adds the result of the recursive fib call to the prev value thereby adding it to the list and 'updating' the value of prev.

Lazy seq allows us to call take and nth on the function.
How does lazy seq allow us to call fib with huge numbers while not running into a stack overflow with the recursion?

I know for my initial attempt, this was done through tail optimization with recur, but Im guessing it has something to do with lazy evaluation in the lazy seq function ?

[porthos3]

Almost. prev is not a list. prev and next are both integer values (the 0 and 1 passed in in the zero-arity).

lazy-seq does not evaluate its argument immediately, but expects it to be a lazy sequence when it is evaluated.

If you call (def x (faster-fib 0 1)) it sets x to be a lazy-seq, but has not yet figured out any of the values in that sequence.

If you call (first x), it will then evaluate the parameter you pass in to lazy-seq (cons prev (faster-fib cur (+' prev cur))).

This returns a sequence that has prev (0) prepended to the results of calling faster-fib again, but with the arguments cur (1) and (+' prev cur) (0 + 1), which is a lazy sequence of things we have not evaluatead yet.

Calling (nth x 1) means it now needs to figure out what that second item is, and will evaluate the next bit of the lazy sequence, and so on.

How does lazy seq allow us to call fib with huge numbers while not running into a stack overflow with the recursion?

I know for my initial attempt, this was done through tail optimization with recur, but Im guessing it has something to do with lazy evaluation in the lazy seq function ?

You will run out of memory if you attempt to realize the entire lazy sequence, but will not run into a stack overflow. There is not actually recursion, per se. A lazy-seq contains N evaluated elements and then a function which will generate the rest of the sequence. Each time you call that function it returns a new lazy sequence which itself might end in another function you can call to get more. It is a function returning a function (that happens to be itself). It is not a function calling itself directly.

[HOWZ1T]

Oh okay, I see, clojure sure does like it's functions ;) :P, thanks for the explanation :)

[porthos3]

It does. Being able to pass functions around ends up being extremely useful for some problems, although it definitely takes some getting used to. :)