Using Funcall and function satisfiability

Discussion of Common Lisp

Using Funcall and function satisfiability

Postby newstudent » Sat Feb 02, 2019 12:57 pm

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...
newstudent
 
Posts: 1
Joined: Sat Feb 02, 2019 12:50 pm

Re: Using Funcall and function satisfiability

Postby pjstirling » Sat Feb 09, 2019 6:44 am

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
pjstirling
 
Posts: 162
Joined: Sun Nov 28, 2010 4:21 pm


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 8 guests

cron