9
\$\begingroup\$

I'm looking to use LISP as best I can, not just get the right answer. This is very early on in my LISP career so feedback is welcome and exciting! Recently asked about Project Euler #1, got some feedback and incorporated into this answer for #2, but I know there's a LOT left to be learned!

Description of Problem #2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

(defun sum (L)
  "sum a list"
  (reduce #'+ L))

(defun filter (L predicate)
  "filters a list"
  (remove-if (complement predicate) L))

(defun fiboNums (maxNum)
  "list of fibonacci numbers that are below maxNum"
  (setq A 1)
  (setq B 2)
  (setq next (+ A B))
  (loop while (< B maxNum) do
    (setq next (+ A B))
    (setq A B)
    (setq B next)
    collecting A))

(defvar answer (sum (filter (fiboNums (* 4 1000 1000)) #'evenp)))
(print answer)
\$\endgroup\$
10
\$\begingroup\$

Notation

It is a common convention in Lisp to avoid uppercase (or mixed lowercase and uppercase) letters in identifiers (symbols), so for instance use l instead of L, or fibo-nums instead of fiboNums, etc.

Variables

If you type your function in a Common Lisp interpreter/compiler, you will receive warnings undefined variable for A B and next. This is because you should introduce local variables before using them with the let or let* special operators (let* is needed if you need to initialize variables with the value other variables introduced). Then, you can assign these variables, as well as all the other type of variables, with setf, that can assign several variables in sequence. So, for instance:

(defun fibo-nums (max-num)
  "list of fibonacci numbers that are below max-num"
  (let* ((a 1)
         (b 2)
         (next (+ a b)))
  (loop while (< b max-num)
    do (setf next (+ a b)
             a b
             b next)
    collecting a)))

Primitive operators

The definition of filter is not necessary, your definition is equivalent to the primitive function remove-if-not.

Algorithm

In this case there is no need of generate a list of Fibonacci numbers and then visiting it, it is sufficient to sum the numbers while generating them:

(defun sum-of-even-fibo (max-num)
  (loop for a = 1 then b
     for b = 1 then next
     for next = (+ a b)
     while (< a max-num)
     when (evenp a)
     sum a))

Finally, since loop is a powerful macro with a complex syntax, here is an alternative version with the more simple macro do*, which has also a syntax more “lisp-style”:

(defun sum-of-even-fibo (max-num)
  (do* ((sum 0)
        (a 1 b)
        (b 1 next)
        (next (+ a b) (+ a b)))
       ((> a max-num) sum)
    (when (evenp a)
      (incf sum a))))
\$\endgroup\$
5
\$\begingroup\$

Overall

The code achieves the most important goal. It runs and produces the correct answer. Using helper/auxiliary methods is a very useful practice and makes the code clearer.

Naming

As mentioned in the accepted answer, it is standard practice to use lower case for all names. The reason is that historically, the Lisp pretty printer prints in ALLCAPS. Using lower case in the source code allows a running program to determine if a source file or other input is machine generated while running...and sometimes Lisp programmers want to do that.

Because Fibonacci is in the realm of mathematics, it might be better to use more mathematical names such as i and j rather than a and b.

Compound names in Lisp are traditionally formmated using dashes. For example, foo-bar rather than "FooBar", "fooBar" or foo_bar. The - in foo-bar cannot be mistaken for the arithmetic subtraction operator because operators always come first in Lisp's s-expressions.

Structure

It is not uncommon for Common-Lisp programs to iterate over loops. On the other hand, another common idiom in Common-Lisp is recursion. Because it is common for contemporary Common-Lisp implementations to optimize tail-calls, it is possible to express loops recursively without danger of running out of stack space.

Lexical Scope

In Common-Lisp new functions can be introduced within the lexical scope of another function using labels and flet. The difference is that labels allows recursive calls and flet does not. Given that most computing devices provide vast resources relative to historical platforms, it might make sense to default to labels and save flet for highly constrained platforms.

Illustrative example

(defun euler-2 (max)
  (labels 
      ((next (n-2 n-1 sum)
         (setq n (+ n-2 n-1))
         (cond
           ((>= n max) sum)
           ((evenp n) (next n-1 n (+ n sum)))
           (t (next n-1 n sum)))))
    (next 1 1 0)))
  • The function euler-2 is named for it's problem domain. It is written to take advantage of SBCL's tail call optimization.
  • It defines an lexically scoped procedure, next internally.
  • In the context of next, the current value is n and it's predecessors are "n minus two" and "n minus one".
  • (next 1 1 0) kicks off next's recursive procedure with initial values.

Circling Back

The original program could be refactored to incorporate several of the suggestions while maintaining the its original iterative approach.

(defun fibo-nums (max)
  "list of fibonacci numbers that are below maxNum"
  (labels
      ((sum (l)
         "sum a list"
         (reduce #'+ l))
       (filter (l predicate)
         "filters a list"
         (remove-if (complement predicate) l))
       ;; add an inner function that does
       ;; all the work
       (f ()
            (progn
              (setq a 1)
              (setq b 2)
              (setq next (+ a b))
              (loop while (< b max) do
                   (setq next (+ a b))
                   (setq a b)
                   (setq b next)
                 collecting a))))
    ;; call the inner function
    (sum (filter (f) #'evenp))))

Note that the locally scoped function f takes no arguments and uses progn to create an executable block of code.

\$\endgroup\$

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.