4
\$\begingroup\$

I solved FizzBuzz using tail recursion. Is it efficient enough?

(defun mod-3 (n)
   (zerop (mod n 3)))

(defun mod-5 (n)
  (zerop (mod n 5)))


(defun analyzer (n)
  (if (mod-3 n)
  (if (mod-5 n)
      'fizzbuzz
      'fizz)
  (if (mod-5 n)
      'buzz
      n)))


(defun fizzbuzz (limit)
  (fizzbuzz-helper limit nil))


(defun fizzbuzz-helper (limit result)
  (cond ((zerop limit) result)
    (t (fizzbuzz-helper (- limit 1)
            (cons (analyzer limit) result)))))
\$\endgroup\$
4
\$\begingroup\$

When a function does too little...

I personally find that your mod-3 and mod-5 functions do something so very specific that you may as well at least combine them into a generic function.

I would call them something different, because what your functions are really doing is not a modulus (there's already a mod function for that), it's verifying if a number is evenly divisible by another number. I would write something like this:

(defun evenly-divisible-by (n x)
  "Given divisor n and dividend x, returns true if x ÷ n has no remainder."
  (zerop (mod x n)))

analyzer

This function's name really doesn't say much to the next person reading the code. What does it analyze? Why? What goal is it trying to achieve? I think a name like calc-fizzbuzz-for-n would honestly be much more clear about (1) the action "calc" and (2) the expected result from the action "fizzbuzz".

In this function, the indentation you applied is a bit misleading. I added some comments below to illustrate:

(defun calc-fizzbuzz (n)
  (if (evenly-divisible-by 3 n)
  ;then...
  (if (evenly-divisible-by 5 n)
      ;then...
      'fizzbuzz
      ;else...
      'fizz)
  ;else...
  (if (evenly-divisible-by 5 n)
    ;then...
    'buzz
    ;else...
      n)))

This seems minor for just a small indentation (and Lisp can make it seem more trivial since you have all those parentheses anyways), but if you wrote something like this in a more "typical" language, I would certainly expect it would be pointed out during a code review...

if (condA) {
if (condB) {
    foo.actionB();
} else {
    foo.actionA();
}
if (condC) {
    foo.ActionC();
} else {
    foo.defaultAction();
}
}

Applying above changes as well, I think this would be better:

(defun calc-fizzbuzz-for-n (n)
  "Given a number n, return whether it is evenly divisible by 3 (fizz), 5 (buzz), 
  or both (fizzbuzz). Returns n when neither condition is true."
  (if (evenly-divisible-by 3 n)
      (if (evenly-divisible-by 5 n)
          'fizzbuzz
          'fizz)
      (if (evenly-divisible-by 5 n)
          'buzz
          n)))

Optional & default values

As far as I can tell, the only purpose of the fizzbuzz function is to take a limit argument, then call fizzbuzz-helper with the limit and added nil for its result argument. This can be simplified by making the result argument optional, like so:

(defun fizzbuzz (limit &optional result)

Note: I changed its name to fizzbuzz since it is no longer a "helper" to your original fizzbuzz function.

According to a related article on nullprogram.com:

If second and third arguments are not provided, b and c will be bound to nil. To provide a default argument, put that parameter inside a list. Below, when a third argument is not provided, c will be bound to "bar".

(defun foo (a &optional b (c "bar"))

So in your case, result will be nil unless it is provided a different argument. Alternatively, and as it appears to be the intention, you can force result to be nil by default using the let special operator:

(defun fizzbuzz (limit)
  (let (result) ;; defaults to nil if not specified
                ;; you can also do this if you find it more clear: (let ((result nil))
    (cond ;...

Alternative solution using lambda expression

This type of approach is often more idiomatic to Lisp/functional programming. You can use an anonymous function (a.k.a. lambda expression) as an argument to a map function. Your last line would look something like this:

(t (map 'list
        #'fizzbuzz
        (loop for i from 1 to limit by 1 collect i)))

or simpler:

(t (loop for i from 1 to limit collect (fizzbuzz i)))

More modern Lisps have a built-in range function to make things simpler, which Common Lisp doesn't; thankfully though, you can just write your own (code below from Stack Overflow answer Python's range() analog in Common Lisp):

(defun range (max &key (min 0) (step 1))
   (loop for n from min below max by step
      collect n))

And your last line can simply become:

(t (map 'integer #'(lambda (N) (fizzbuzz N)) (range limit 1)))

Thanks to @Renzo for the correction, your last function could be written as:

(defun fizzbuzz (limit) 
  (mapcar #'calc-fizzbuzz-for-n (range (1+ limit) :min 1)))

or using LOOP:

(defun fizzbuzz (limit) 
  (loop for n from 1 upto limit
        collect (calc-fizzbuzz-for-n n)))
\$\endgroup\$
  • \$\begingroup\$ For typical Common Lisp style guidelines (e.g. alignments), please see this or this. \$\endgroup\$ – Renzo Mar 15 '16 at 16:02
  • \$\begingroup\$ @Renzo I have seen those before, did you have anything to point out specifically though? I more often write Clojure Lisp than Common Lisp so it's possible the style I use is biased by that. \$\endgroup\$ – Phrancis Mar 15 '16 at 16:04
  • \$\begingroup\$ In particular, one should put the arguments on the same line of the function name, and align the “then” and “else” part under the “condition” of the if (uniformly). \$\endgroup\$ – Renzo Mar 15 '16 at 16:10
  • 1
    \$\begingroup\$ The final function should be (defun fizzbuzz (limit) (mapcar (lambda (n) (calc-fizzbuzz-for-n n)) (range (1+ limit) :min 1))) \$\endgroup\$ – Renzo Mar 15 '16 at 16:21
  • \$\begingroup\$ OK thank you so much, I corrected my answer according to your comments! \$\endgroup\$ – Phrancis Mar 15 '16 at 16:37
3
\$\begingroup\$

You are asking if your solution is efficient enough, by using tail recursion, that certain compilers, under certain conditions, can transform in iteration.

But, as discussed in other answers and comments, in Common Lisp one could also use directly the iteration operators present in the language.

For instance, by using your first three functions, one could redefine fizzbuzz in this way:

(defun fizzbuzz (limit)
   (loop for i from 1 to limit collect (analyzer i)))

Hopefully, a good compiler should compile the above function with a code similar to that of your function (and when I tried the functions with SBCL, this is what happened, giving a time of ~0.8 seconds for a limit of 10000000 for both of them).

But a way of improving the efficiency of the fizzbuzz function is to eliminate the need of performing the modulo operations, which are costly, by generating directly all the elements with a function like this one:

(defun fizzbuzz (limit)
  (let ((circ '#1=(nil nil fizz nil buzz fizz nil nil fizz buzz nil fizz nil nil fizzubzz . #1#)))
    (loop for i from 1 to limit collect (or (pop circ) i))))

The function first defines a circular list of 15 elements, which is the repeating pattern of the elements of the FizzBuzz problem, in which nil stands for a number, and fizz buzz and fizzbuzz stand for themselves. ('#n=(e1 e2 ... en . #n) is called “sharp-notation”, see for instance this question, and allows the direct construction in Common Lisp of a circular list, that is a list in which the last element points back to the first one).

Then the iteration is performed in this way: looping with i from 1 to limit, an element is extracted from the list with (pop circ), that advances circto the next element, and if the element is not nil then it is returned, otherwise the current value of i is returned. This is done with the or operator, that returns the first operand which is not null, or nil if all the operands are null.

The gain in efficiency with this approach is of 55-60%.

\$\endgroup\$
  • 1
    \$\begingroup\$ That is a great answer, sir. Though I had an idea like that, I couldn't solve as I haven't learn those yet. \$\endgroup\$ – min Mar 16 '16 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.