Is there a way to use iteration in Common Lisp and avoid side-effects at the same time?

Question

I've written two versions of a lisp function. The main difference between the two is that one is done with recursion, while the other is done with iteration.

Here's the recursive version (no side effects!):

(defun simple-check (counter list)
  "This function takes two arguments: 
  the number 0 and a list of atoms. 
  It returns the number of times the 
  atom 'a' appears in that list."
  (if (null list)
      counter
      (if (equal (car list) 'a)
          (simple-check (+ counter 1) (cdr list))
          (simple-check counter (cdr list)))))

Here's the iterative version (with side effects):

(defun a-check (counter list)
  "This function takes two arguments: 
  the number 0 and a list of atoms. 
  It returns the number of times the 
  atom 'a' appears in that list."
  (dolist (item list)
    (if (equal item 'a)
        (setf counter (+ counter 1))
        (setf counter (+ counter 0))))
  counter)

As far as I know, they both work. But I'd really like to avoid side-effects in the iterative version. Two questions I'd like answered:

Is it possible to avoid side effects and keep iteration?
Assuming the answer to #1 is a yes, what are the best ways to do so?

Do you consider `(loop for x in list count (eql x 'a))` to have side-effects? why? why not? I thought side-effects were defined as effects that change the world outside a function, not inside it. — coredump, Jun 22 '19 at 06:04
The `else` clause of your `if` statement in the iterative solution makes no sense. You can use `when` if you only have one clause. Furthermore, using `incf` instead of `setf` makes it more concise. — Martin Buchmann, Jun 22 '19 at 07:00

score 4 · Answer 1 · answered Jun 22 '19 at 18:56

4

For completeness, note that Common Lisp has a built-in COUNT:

(count 'a list)

answered Jun 22 '19 at 18:56

coredump

37,664
5
43
77

Svante · Accepted Answer · 2019-06-22T10:04:08.870

In some ways, the difference between side-effect or no side-effect is a bit blurred. Take the following loop version (ignoring that loop also has better ways):

(loop :for x :in list
      :for counter := (if (eq x 'a) (1+ counter) counter)
      :finally (return counter))

Is counter set at each step, or is it rebound? I. e., is an existing variable modified (like in setf), or is a new variable binding created (as in a recursion)?

This do version is very much like the recursive version:

(do ((list args (rest list))
     (counter 0 (+ counter (if (eq (first list) 'a) 1 0))))
    ((endp list) counter))

Same question as above.

Now the “obvious” loop version:

(loop :for x :in list
      :count (eq x 'a))

There isn't even an explicit variable for the counter. Are there side-effects?

Internally, of course there are effects: environments are created, bindings established, and, especially if there is tail call optimization, even in the recursive version destroyed/replaced at each step.

I see as side effects only effects that affect things outside of some defined scope. Of course, things appear more elegant if you can also on the level of your internal definition avoid the explicit setting of things, and instead use some more declarative expression.

Ehvince · Answer 3 · 2019-06-22T20:49:58.590

3

You can also iterate with map, mapcar and friends.

https://lispcookbook.github.io/cl-cookbook/iteration.html

I also suggest a look at remove-if[-not] and other reduce and apply:

(length (remove-if-not (lambda (x) (equal :a x)) '(:a :b :a)))  ;; 2

edited Jun 22 '19 at 20:49

answered Jun 22 '19 at 18:24

Ehvince

17,274
7
58
79

and as reminds Coredump: `(count 'a list)` ! https://lispcookbook.github.io/cl-cookbook/data-structures.html#count-foo-sequence Also `count-if` and `count-not`. – Ehvince Jun 22 '19 at 20:52

score 1 · Answer 4 · answered Jun 25 '19 at 01:02

Passing counter to the recursive procedure was a means to enable a tail recursive definition. This is unnecessary for the iterative definition. As others have pointed out, there are several language constructs which solve the stated problem elegantly.

I assume you are interested in this in a more general sense such as when you cannot find a language feature that solves a problem directly. In general, one can maintain a functional interface by keeping the mutation private as below:

(defun simple-check (list)                                                                    
  "return the number of times the symbol `a` appears in `list`"                                 
  (let ((times 0))                                                                            
    (dolist (elem list times)                                                                 
      (when (equal elem 'a)                                                                   
        (incf times)))))

Is there a way to use iteration in Common Lisp and avoid side-effects at the same time?

4 Answers4