Last active
December 17, 2024 19:35
-
-
Save simon-brooke/b1967fc2dab0a9ac1ff4a95b2aa4a7c9 to your computer and use it in GitHub Desktop.
Fairly idiomaticFibonacci sequence in Clojure, using `reduce`
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(ns fibs.fibonacci | |
"Compute Fibonacci sequences. | |
The motivation for writing this was reading a presentation by Stuart | |
Sierra on Fibonacci sequences in which he showed both recursive and tail | |
recursive solutions in Clojure, both of which he correctly noted blew up | |
for large values of `n`, but did not show a `reduce` based solution which | |
would seem efficient, idiomatic and (relatively) robust. | |
Stuart's presentation is here: | |
https://fpilluminated.com/downloadFromS3/252/2024-12-15-fibonacci-function-gallery-part-1.pdf | |
Of course, mine does maintain the sequence in memory and will crash out of | |
memory for *very* large values of `n`, and has some minor hacky features I'm | |
not wholly satisfied with, but it still seems to me a better solution.") | |
(defmacro bigint? | |
"Returns true if n is a BigInt." | |
[n] `(instance? clojure.lang.BigInt ~n)) | |
(defmacro integer-or-1 | |
"If `n` is an integer (int or bigint), return `n`; else | |
return 1." | |
[n] | |
`(cond (int? ~n) ~n | |
(bigint? ~n) ~n | |
:else 1)) | |
(defn fib-next | |
"Considering `l` as a reversed fibonacci sequence, return the next element | |
in that sequence" | |
[l] | |
(+' (integer-or-1 (first l)) | |
(integer-or-1 (second l)))) | |
(defn- rfibs | |
"Return a reversed Fibonacci sequence of length `n`+ 1, because we want the | |
value of `(fib n)` on the front of it. HACK: if called with `n` = zero | |
it will return the wrong answer, but | |
1. this would be trivial to fix at the expense of making the algorithm less | |
clear, and | |
2. it's private, so cannot be invoked from user code." | |
[n] | |
(reduce (fn [l _] (cons | |
(fib-next l) | |
l)) | |
;; ππ π = 0 β¨ π = 1 | |
(list 1 1) | |
;; decrement `n` because the first two items are literals | |
(range (dec n)))) | |
(defmacro fibs | |
"Return a Fibonacci sequence of length `n`." | |
[n] | |
`(reverse (rfibs (dec ~n)))) | |
(defmacro fib | |
"Return the `n`th number in a (zero based) Fibonacci sequence." | |
[n] | |
`(if (> 2 ~n) 1 | |
(first (rfibs ~n)))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment