The One and Only Truely Functional FizzBuzz (in Clojure)

fizz-buzz.cljc

(ns fizz-buzz
  "Approaching the infamous 'FizzBuzz' code problem with cyclic sequences and declarative rules")

;; SOLUTION

;; Core ideas:
;; 1. Note that the logic is essentially sequential and cyclical.
;; 2. Delay the actual computation (execution) by opting for lazy sequences.
;; 3. Separate control flow and logic, extracting the latter into a ruleset data structure.

;; NB: Here I prioritized the readability by newcomers, and thus tend to use less idiomatic code and don't require any libs.

(defn cyclic-seq-samples
  "Transforms `rules` into samples of cyclic sequences.

   [{:period 3, :literal \"Fizz\"} {:period 5, :literal \"Buzz\"}]
   =>
   [[nil nil \"Fizz\"] [nil nil nil nil \"Buzz\"]]"
  [rules]
  (reduce (fn [seq-samples {:keys [period literal] :as rule}]
            (let [seq-sample (conj (vec (repeat (dec period) nil)) literal)]
              (conj seq-samples seq-sample)))
          []
          rules))

(defn compose-cyclic-seqs
  "Composes `cyclic-seqs` into a single (infinite) lazy sequence."
  [cyclic-seqs]
  (apply map (fn [& seqs-one-step-slice]
               (let [literals (remove nil? seqs-one-step-slice)]
                 (if (empty? literals) nil literals)))
         cyclic-seqs))

(defn transform-seq-members
  "For a `seq` of literals and `nil`s, substitutes `nil`s with indices.
   This is the main output transformation logic of 'FizzBuzz' problem."
  [seq]
  (map-indexed (fn [idx member]
                 (if (some? member) (apply str member) (inc idx)))
               seq))

(defn fizzBuzz
  "For a given set of `rules`, produces a 'FizzBuzz' lazy sequence."
  [rules]
  (->> (cyclic-seq-samples rules)
       (map cycle)
       (compose-cyclic-seqs)
       (transform-seq-members)))

;; CALL SITE / USING IT

(def rules [{:period  3
             :literal "Fizz"}
            {:period  5
             :literal "Buzz"}])

;; so far nothing is computed yet
(def infinite-seq (fizzBuzz rules))

;; limit if necessary, but do not consume just yet
(def limit 100)
(def limited-seq (take limit infinite-seq))

;; finally, consume the lazy seq to achieve desired side effects
(doseq [member limited-seq] (println member))

First of all, the nature of the "FizzBuzz" problem is infinite. It's quite obvious, but how to solve it in such a general form is no longer so obvious. We can pay a closer attention to the main sequence, which in imperative solution takes a form of a fixed array of limit length in memory (that is why we have to limit it in the first place, by the way!). Until there is a limit, we can compute it that way. But your brain does not experience such limitation, when you go through these computations step-by-step, one sequence member at a time, right? This type of problems can be naturally addressed by lazy computations. Lazyness overcomes the issue of infinite sequences and also postpones the memory allocation till the last point, when the output sequence is eventually consumed.

Second of all, one may notice that things tend to change in the output periodically, with a period that is the result of multiplying all prime periods, i.e. 3 * 5 = 15 in our example case. Thus, we can substitute the main sequence with a cyclic one with a suitable period. And here comes the major concept of Functional (and, in fact, any other style of) programming — composition. So, in essence, the solution boils down to figuring out a proper way of composing cyclic sequences, i.e. (x, x, "Fizz") and (x, x, x, x, "Buzz") in our example case, where x is a placeholder, into a (x, x, "Fizz", x, "Buzz", "Fizz", x, x, "Fizz", "Buzz", x, "Fizz", x, x, ["Fizz" "Buzz"]) sequence. Let me re-write it in a bit more practical way — (x, x, ["Fizz"], x, ["Buzz"], ["Fizz"], x, x, ["Fizz"], ["Buzz"], x, ["Fizz"], x, x, ["Fizz" "Buzz"]) — so that final transformation is uniform for all non-x members — we'll just "join" any number of sting literals in them in the end.

Lastly, we still lack numbers on the x's places. And the nature of a cyclic sequence kinda prevents us from having them, right? No. It only prevents us from having them "in place", i.e. as a cyclic sequence members. Happily, we are able to decomplect (or decouple) these two things — the sequence members and, well, their indexes — by indexing the sequence that we derive from a cyclic one. This resulting sequence, depending on the implementation details of a specific library (in a specific programming language), can be indexed quite effectively, e.g. by storing only one number, an index of the previous seq member, in memory at a time.

This "specific" is crucial, so let's pick a truly Functional language to illustrate this whole approach, say Clojure/Script. I'll then use nil as the x placeholder. So, this is the final piece of the puzzle for the solution given in the above Gist.