Deleting a sequence from a list

[devonman88]

Hi there,

I have just entered the world of LISP so I'm a bit of a newbie!

I want to change a list containing something like (2 x + 1) into something like (2 x) i.e. I want to find and delete all (+ 1)s in a list.

I am familiar with the delete function but that only takes an atom:

(delete '+ '(2 x + 1))
(2 x 1)

and

(delete '(+ 1) '(2 x + 1))
(2 x + 1)

I can write something to find a sequence i.e. + 1 in a list but how do I delete the sequence?

Thanks in advance

[makia]

CL-USER> (set-difference '(2 x + 1) '(+ 1))

(X 2)
CL-USER> (remove-if (lambda (a) (member a '(+ 1))) '(2 x + 1))
(2 X)
CL-USER>

Notice that in set-differece case order is not preserved.

[danb]

I have just entered the world of LISP so I'm a bit of a newbie!

Welcome

I want to change a list containing something like (2 x + 1) into something like (2 x) i.e. I want to find and delete all (+ 1)s in a list.

Walk down the list, checking each cdr (ie. remainder) of the list to see if it starts with the sequence. If it does, then find the remainder of the list starting right after the sequence, and append whatever you get from removing the sequence from that, to whatever earlier elements you didn't already delete. If the current list (ie. remainder of the original list) doesn't start with the sublist, then cons the current first element (the car of the current list) onto whatever you get from removing the sequence from the cdr of the list, and append that.

A slick way of writing the function is to do the sublist test and find the next remainder together, and then have the main function call itself recursively, building up a stack of cons instructions that assembles the output list as soon as the input list is fully analyzed. The recursive solution uses a lot of memory for long lists, but it's easy to write once you figure out how recursion works.

Code: Select all

(defun starts-with (list sublist)
  (let ((cell list))
    (dolist (x sublist (values t cell))
      (if (eql x (car cell))
          (setf cell (cdr cell))
          (return (values nil nil))))))

(defun remove-sublist (sublist list)
  (and list
       (multiple-value-bind
             (starts-with-sublist next-cell)
           (starts-with list sublist)
         (if starts-with-sublist
             (remove-sublist sublist next-cell)
             (cons (car list) (remove-sublist sublist (cdr list)))))))


Code: Select all

DS> (remove-sublist '(+ 1) '(2 x + 1))
(2 X)
DS> (remove-sublist '(+ 1) '(2 x + 1 - b))
(2 X - B)
DS> (remove-sublist '(+ 1) '(2 x + y - 1 - b))
(2 X + Y - 1 - B)
DS> (remove-sublist '(+ 1) '(+ 1))
NIL


[devonman88]

Thanks so much - brilliant . I feel like I'm really starting to let go of my procedural way of thinking and accept this functional way, thanks for all the help! I'll have an experiment with this.