CODEWITHSUNDEEP
lispcommon-lisp
Bogdan M.
Bogdan M.

Reputation: 2181

Convert lisp function to use map

Hello I am looking forward to convert my existing function:

(defun checkMember (L A)
  (cond
    ((NULL L) nil)
    ( (and (atom (car L)) (equal (car L) A))  T )
    (T  (checkMember (cdr L) A))))

To use map functions, but i honestly cant understand exactly how map functions work, could you maybe advice me how this func's work?

this is my atempt:

(defun checkMem (L A)
  (cond
    ((NULL L) nil)
    ( (and (atom (car L)) (equal (car L)  (car A)))  T )
    (T  (mapcar #'checkMem  (cdr L) A))))

Upvotes: 2

Views: 470

Answers (4)

Pankaj Sejwal
Pankaj Sejwal

Reputation: 1595

Try this,

Recursive version:

(defun checkmember (l a)
 (let ((temp nil))
  (cond ((null l) nil) ((find a l) (setf temp (or temp t)))
   (t
    (mapcar #'(lambda (x) (cond ((listp x)(setf temp (or temp (checkmember x a))))))
     l)))
  temp))

Usage: (checkmember '(1 (2 5) 3) 20) => NIL

(checkmember '(1 (2 5) 3) 2) => T

(checkmember '(1 2 3) 2) => T

(checkmember '((((((((1)))))))) 1) = T

Upvotes: 1

Kaz
Kaz

Reputation: 58578

A mapping function is not appropriate here because the task involves searching the list to determine whether it contains a matching item. This is not mapping.

Mapping means passing each element through some function (and usually collecting the return values in some way). Sure, we can abuse mapping into solving the problem somehow.

But may I instead suggest that this is a reduce problem rather than a mapping problem? Reducing means processing all the elements of a list in order to produce a single value which summarizes that list.

Warm up: use reduce to add elements together:

(reduce #'+ '(1 2 3)) -> 6

In our case, we want to reduce the list differently: to a single value which is T or NIL based on whether the list contains some item.

Solution:

(defun is-member (list item)
  (reduce (lambda (found next-one) (or found (eql next-one item)))
          list :initial-value nil))

;; tests:
(is-member nil nil) -> NIL
(is-member nil 42) -> NIL
(is-member '(1) 1) -> T
(is-member '(1) 2) -> NIL
(is-member '(t t) 1) -> NIL  ;; check for accumulator/item mixup
(is-member '(1 2) 2) -> T
(is-member '(1 2) 3) -> NIL
...

A common pattern in using a (left-associative) reduce function is to treat the left argument in each reduction as an accumulated value that is being "threaded" through the reduce. When we do a simple reduce with + to add numbers, we don't think about this, but the left argument of the function used for the reduction is always the partial sum. The partial sum is initialized to zero because reduce first calls the + function with no arguments, which is possible: (+) is zero in Lisp.

Concretely, what happens in (reduce #'+ '(1 2 3)) is this:

  • first, reduce calls (+) which returns 0.
  • then, reduce calls (+ 0 1), which produces the partial sum 1.
  • next, reduce calls (+ 1 2), using the previous partial sum as the left argument, and the next element as the right argument. This returns 3, of course.
  • finally, reduce calls (+ 3 3), resulting in 6.

In our case, the accumulated value we are "threading" through the reduction is not a partial sum, but a boolean value. This boolean becomes the left argument which is called found inside the reducing function. We explicitly specify the initial value using :initial-value nil, because our lambda function does not support being called with no arguments. On each call to our lambda, we short-circuit: if found is true, it means that a previous reduction has already decided that the list contains the item, and we just return true. Otherwise, we check the right argument: the next item from the list. If it is equal to item, then we return T, otherwise NIL. And this T or NIL then becomes the found value in the next call. Once we return T, this value will "domino" through the rest of the reduction, resulting in a T return out of reduce.

If you insist on using mapping, you can do something like: map each element to a list which is empty if the element doesn't match the item, otherwise nonempty. Do the mapping in such a way that the lists are catenated together. If the resulting list is nonempty, then the original list must have contained one or more matches for the item:

(defun is-member (list item)
  (if (mapcan (lambda (elem)
                (if (eq elem item) (list elem))) list)
     t))

This approach performs lots of wasteful allocations if the list contains many occurrences of the item.

(The reduce approach is also wasteful because it keeps processing the list after it is obvious that the return value will be T.)

Upvotes: 7

Rainer Joswig
Rainer Joswig

Reputation: 139261

(defun memb (item list)
  (map nil
       (lambda (element)
         (when (eql item element)
           (return-from memb t)))
       list))

Upvotes: 3

Frédéric Dumont
Frédéric Dumont

Reputation: 978

What about this:

(defun checkMember (L a)
  (car (mapcan #'(lambda (e)
                   (and (equal a e) (list T)))
               L)))

Note: it does not recurse into list elements, but the original function did not either.

Upvotes: 3

Related Questions