Hello! The task is as follows: it is necessary to insert a new element into an ordered list, while maintaining its orderliness. The list is unordered at first. It is necessary to work with the same list without creating a new one in the process of sorting and pasting.

So far I have not even found any good information about the list of destructive functions.

  • @AnnaHatiko, According to the rules of the forum, questions should not be limited to solving or completing student assignments. Please clarify what you have done yourself and what did not work out. - Artem
  • while the question is - what are the list-breaking functions? No material has been read on them yet, I haven’t found it anywhere else either - AnnaHatiko
  • "The task is this: it is necessary to insert a new element into the ordered list, keeping its orderliness. The list is unordered at first." So he is ordered or unordered? - alexlz
  • disordered - AnnaHatiko
  • one
    > insert a new item into the ordered list> List first unordered What the hell is it? - Vladimir Gordeev

2 answers 2

Suppose we are talking about Common Lisp.

There is a macro (push item list) that pushes the item value to the top of the list . In essence, it is equivalent to (setf list (cons item list)) .

Accordingly, in order to destructively insert an element into the list from the desired position, you need to take the list after this position, and replace it by inserting the element using push .

True, there is one problem - the tail is most reasonable to get using nthcdr , and this is a function, not an accessor (like car or cdr ), and setf so easy not to give it away. Just insert after the position is written - take cdr from nthcdr - you can feed it push / setf , that's the thing with the ends:

 (defun insert-after (item list index) "Destructively inserts 'item' into 'list' after 'index'." (push item (cdr (nthcdr index list))) list)

But to insert before the position will have a bit more cunning, the case with a zero index must be specially processed. It will turn out to be a macra, and not a function (since it makes no sense to make a function (setf list …) - the scope is different, see example 8.6.8 by reference):

 (defmacro insert-at (item list index) "Destructively inserts 'item' into 'list' before 'index'." `(if (zerop ,index) (push ,item ,list) (insert-after ,item ,list (1- ,index))))

Checking:

 (setf test-list '(abcd)) (insert-at 'z test-list 0) => (zabcd) (insert-at 'x test-list 5) => (zabcdx)

For deletion, the easiest way is probably to use setf - for example, to remove the first list item, you need to replace the list itself with cdr from it. To remove the second one, replace cdr with cddr . Etc.

If the logic of insertion is clear, then there should be no problems with the removal.

  • I'm doing on XLisp. And in my opinion it is necessary through the functions RPLACD, RPLACA to do .. without macros .., etc. - AnnaHatiko
  • There are many possible solutions. It is possible and through them, these are just tools of a slightly lower level than push or nth , they work with cons, not lists. With XLisp, alas, not familiar. - drdaeman

Use the setf macro with nth .

 (defvar *x* '(1 2 3 4)) (nth 3 *x*) ; => 4 (setf (nth 3 *x*) -1) *x* ; => (1 2 3 -1)

Use the original Common Lisp documentation , everything is there.

  • And how to find the term "list-destroying" in this original documentation? The term, I think, is relatively new, of the 21st century. It is, of course, the problems of translation with the unsettled Russian-language terminology - the problem is old, but the "list-destroying" is cool. Function applied - and the list was gone. Yes, and neighboring lists may suffer. - alexlz
  • It is simply called “destructive” there. “List destructive” is already an attempt to glue two definitions (“for working with lists” and “destructive” / “destructive” / “mutators” / ...) into one word. - drdaeman
  • Function modifying the list meant, so destructive list modification translated destructive list modification . - Vladimir Gordeev