Using Funcall and function satisfiability

[newstudent]

Could anyone help me solve this Common Lisp question?

Use do, if, and funcall to define (satisfy fun lst) which returns a list of the items in a list that satisfy a function. An item satisfies a function if the function returns true when that item is used as the function’s argument.

This is how far I've gotten:

Code: Select all

(defun satisfy (fun lst)
  "(fun lst)
Returns a list of the items in a list that satisfy a function."
  (do ((numbers lst (cdr numbers))
       (sat ()))
      ((null numbers) sat)
    (if (funcall fun (car numbers))
         (cons (car numbers) sat))))

I'm assuming I haven't used funcall correctly but I have no idea what I'm doing wrong...

[pjstirling]

Your problem is actually that you are mixing imperative with functional style. There is no special handling of the last form of the body of DO, it is discarded, so your call to CONS is wasted, and SAT remains NIL

As an aside, DO should be used only in situations where you can't use one of the more specialised looping constructs (DOLIST etc.) If you need a variable then you should wrap a LET. This is because mentally parsing a DO form to work out what it is actually doing is complicated.

I would have written your function like so:

Code: Select all

(defun satisfy (fun list)
  (let (result)
    (dolist (el list (nreverse result))
      (when (funcall fun el)
        (push el result)))))

Note the call to NREVERSE otherwise your results are backwards.

For completeness a functional style version would be like:

Code: Select all

(defun satisfy (fun list)
  (labels ((rec (list acc)
                (if list
                    (rec (rest list)
                          (if (funcall fun
                                        (first list))
                              (cons (first list)
                                       acc)
                              ;; else
                              acc))
                 ;; else
                 (nreverse acc))))
    (rec list nil)))

Though it's worth noting that the standard doesn't guarantee tail-call optimisation (even if most implementations actually would). This means that the imperative style would be both safer and shorter