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

The resulting limited-seq is:

(1 2 "Fizz" 4 "Buzz" "Fizz" 7 8 "Fizz" "Buzz" 11 "Fizz" 13 14 "FizzBuzz" 16 17 "Fizz" 19 "Buzz" "Fizz" 22 23 "Fizz" "Buzz" 26 "Fizz" 28 29 "FizzBuzz" 31 32 "Fizz" 34 "Buzz" "Fizz" 37 38 "Fizz" "Buzz" 41 "Fizz" 43 44 "FizzBuzz" 46 47 "Fizz" 49 "Buzz" "Fizz" 52 53 "Fizz" "Buzz" 56 "Fizz" 58 59 "FizzBuzz" 61 62 "Fizz" 64 "Buzz" "Fizz" 67 68 "Fizz" "Buzz" 71 "Fizz" 73 74 "FizzBuzz" 76 77 "Fizz" 79 "Buzz" "Fizz" 82 83 "Fizz" "Buzz" 86 "Fizz" 88 89 "FizzBuzz" 91 92 "Fizz" 94 "Buzz" "Fizz" 97 98 "Fizz" "Buzz")

Another rules set:

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

results in this limited-seq:

(1 "Woof" "Fizz" "Woof" "Buzz" "WoofFizz" 7 "Woof" "Fizz" "WoofBuzz" 11 "WoofFizz" 13 "Woof" "FizzBuzz" "Woof" 17 "WoofFizz" 19 "WoofBuzz" "Fizz" "Woof" 23 "WoofFizz" "Buzz" "Woof" "Fizz" "Woof" 29 "WoofFizzBuzz" 31 "Woof" "Fizz" "Woof" "Buzz" "WoofFizz" 37 "Woof" "Fizz" "WoofBuzz" 41 "WoofFizz" 43 "Woof" "FizzBuzz" "Woof" 47 "WoofFizz" 49 "WoofBuzz" "Fizz" "Woof" 53 "WoofFizz" "Buzz" "Woof" "Fizz" "Woof" 59 "WoofFizzBuzz" 61 "Woof" "Fizz" "Woof" "Buzz" "WoofFizz" 67 "Woof" "Fizz" "WoofBuzz" 71 "WoofFizz" 73 "Woof" "FizzBuzz" "Woof" 77 "WoofFizz" 79 "WoofBuzz" "Fizz" "Woof" 83 "WoofFizz" "Buzz" "Woof" "Fizz" "Woof" 89 "WoofFizzBuzz" 91 "Woof" "Fizz" "Woof" "Buzz" "WoofFizz" 97 "Woof" "Fizz" "WoofBuzz")

Looks trustworthy, huh? But why and how does it actually work? Let's discuss the basis of this approach more formally.

I love this semi-declarative rules-based solution to the problem and used it as a starting point.

But why "semi-" though? And how to make it even more declarative?

First, side-effects. They better be pulled of the function, making it pure (in a Functional Programming sense).
Second, the limit parameter. You actually don't need one for the business logic, it's a "call site" concern, as well as the side-effects.
Last but not least, sequences.

Let's dive into all these details.

The logic of this whole "FizzBuzz" thing revolves around a concept of a sequence — a cyclic sequence, to be more precise. You have a main sequence — an infinite (!) series of natural numbers (1, 2, 3, ...), and a set of prime periods k (for example, for the original problem k = #{3, 5}) for cyclic sequences that result in "marking" each k's member of the series. Then, for each member, depending on whether or not it was "marked", you either leave it intact or substitute with some string literal or a concatenation of string literals. It's also good to notice, that all these can be done in one pass of the main sequence. But how?

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.