Sum of all multiples of 3 or 5 below 1000 (Project Euler #1 - typical)

I'm learning LISP and am starting with Project Euler. I would love some initial feedback on my LISP code for this simple task.

I know it spits out the correct answer, but what I'm not sure about is if I'm using LISP the way it is intended (and the way to strive for in the future in order to achieve success with LISP).

(defun sum (L)
"sum a list"
(apply '+ L)
)

(defun range (max &key (min 0) (step 1))
"range of numbers from min to max by jumps of step"
(loop for n from min below max by step
collect n)
)

; take a range that steps by 3's and a list that steps by 5's and take the union of them (union removes duplicates)
(setq answer (sum (union (range 1000 :step 3) (range 1000 :step 5))))


Minor

Paren placement

Hanging parens are an eyesore.

Global var

Use defvar instead of setq to create global variables.

Sharp-quote for functions

You should do (apply #'+ ...) instead of (apply '+ ...).

Unnecessary allocation

Since your range returns a fresh list, you can use nunion instead of union.

Major

Sum

Your sum function is broken - it will not work on long lists, see CALL-ARGUMENTS-LIMIT.

Here are better ways to do this:

(defun sum (list)
(reduce #'+ list))

(defun sum (list)
(loop for x in list sum x))


Performance

union is probably quadratic in your implementation, so you might want to consider another approach for larger values of 1000 :-)

In addition to the correct and comprehensive answer of sds, I would add that the solution not only has a bad performance since the union function could be quadratic, but that it does not need allocations of lists at all. We can sum the values when they are generated, without storing them in lists (here we use the sum clause of loop):

(+ (loop for n below 1000 by 3 sum n)
(loop for n below 1000 by 5 unless (zerop (mod n 3)) sum n))


The loop in the first line generates and sums all the multiples of 3, while the second loop generates all the multiples of 5 and sum only those that are not simultaneously multiples of 3.

Finally, we can obtain an increase of performance if we get rid of the costly division ((mod n 3)):

(+ (loop for n below 1000 by 3 sum n)
(loop for n below 1000 by 5 sum n)
(- (loop for n below 1000 by 15 sum n)))

• Totally! I tried doing it without allocation, but then realized this was my first time using LISP so it wasn't worth it to make my code perfect instead of just get a solution out there. Thanks for showing me what I was missing out on! Super helpful going forward. – tscizzle Dec 18 '16 at 6:56