CODEWITHSUNDEEP
functional-programminglispcommon-lisp
Billda
Billda

Reputation: 5997

Processing pairs of successive elements in a list with standard mapping functions?

I have a small exercise in Lisp:

Write a function test-delta with parameters delta and lst, which will check if the difference between successive elements in lst is smaller than delta. Write the function in two ways:

  • recursively
  • using a mapping function

I have no problem writing that function recursively, but I don't know which mapping function I should use. All the standard mapping functions work with only one element of the list at a time. reduce cannot be used either, because I do not have some operation to use between successive elements. What function could I use here?

Upvotes: 1

Views: 146

Answers (2)

Joshua Taylor
Joshua Taylor

Reputation: 85883

All standard functions are working only with one element at time.

Reduce function cannot be use either because i do not have some operation to use between to elements.

There's already an answer by uselpa showing that you can do this with reduce, but it feels a bit awkward to me to bend reduce to this case.

It's much more natural, in my opinion, to recognize that the standard mapping functions actually let you work with multiple lists. I'll show mapcar and loop first, and then every, which I think is the real winner here. Finally, just for completeness, I've also included maplist.

mapcar

The standard mapcar can take more than one list, which means that you can take elements from two different lists at once. Of particular note, it could take a list and (rest list). E.g., 

(let ((list '(1 2 3 4 5 6)))
  (mapcar 'cons
          list
          (rest list)))

;=> ((1 . 2) (2 . 3) (3 . 4) (4 . 5) (5 . 6))

loop

You can use loop to do the same sort of thing:

(loop
   with l = '(1 2 3 4 5 6)
   for a in l
   for b in (rest l)
   collect (cons a b))
;=> ((1 . 2) (2 . 3) (3 . 4) (4 . 5) (5 . 6))

There are some other variations on loop that you can use, but some of them have less conventient results. E.g., you could loop for (a b) on list, but then you get a (perhaps) unexpected final binding of your variables:

(loop for (a b) on '(1 2 3 4 5 6)
     collect (list a b))
;=> ((1 2) (2 3) (3 4) (4 5) (5 6) (6 NIL))

This is similar to what maplist will give you.

every

I think the real winners here, though, are going to the be every, some, notevery, and notany functions. These, like mapcar can take more than one list as an argument. This means that your problem can simply be:

(let ((delta 4)
      (lst '(1 2 4 7 9)))
  (every (lambda (x y)
           (< (abs (- x y)) delta))
         lst
         (rest lst)))
;=> T

(let ((delta 2)
      (lst '(1 2 4 7 9)))
  (every (lambda (x y)
           (< (abs (- x y)) delta))
         lst
         (rest lst)))
;=> NIL

maplist

You could also do this with maplist, which works on successive tails of the list, which means you'd have access to each element and the one following. This has the same 6 NIL at the end that the second loop solution did, though. E.g.:

(maplist (lambda (tail)
           (list (first tail) 
                 (second tail)))
         '(1 2 3 4 5 6))
;=> ((1 2) (2 3) (3 4) (4 5) (5 6) (6 NIL))

Upvotes: 3

uselpa
uselpa

Reputation: 18927

reduce can be used:

(defun testdelta (delta lst)
  (reduce
   (lambda (r e)
     (if (< (abs (- r e)) delta)
       e
       (return-from testdelta nil)))
   lst)
  t)

or, without return-from (but possibly slower):

(defun testdelta (delta lst)
  (and
   (reduce
    (lambda (r e) 
      (and r (if (< (abs (- r e)) delta) e nil)))
    lst)
   t))

Upvotes: 1

Related Questions