Reputation: 71
(defun insert (number lst)
(let ((before nil))
(if (= (length lst) 0) (return-from insert (list number)))
(loop for n from 0 to (1- (length lst)) do
(if (< number (nth n lst)) (progn (nconc before (list number)) (nconc before lst) (return-from insert before) )
(progn (nconc before (list (pop lst))))))
(nconc before (list number))
(return-from insert before)))
So, I'm trying to insert a number sorted in the list. Forgive for my somehow bad LISP practice, I started learning not much time ago.
I'm going through the list and inserting the elements into a 'before' list. If the number I want to insert is less than the list element I'm currently in, I append the number to insert in the 'before' list then I append what's left of the original list 'lst' to the 'before' list, then returning 'before'.
However, this function always returns NIL. Any ideas why? I mean, both pop and nconc are destructive...
Upvotes: 0
Views: 1209
Reputation: 139261
Let's look at a few problems of your code.
Inefficiency: wrong data structure or wrong choice of operations
if you use LENGTH
or NTH
on a list, you can bet that it is wrong. Lists are linked lists and operations like LENGTH
and NTH
are potentially expensive. Especially if done a gazillion time in a loop or recursive calls. If you want to use these functions, then vectors are the natural choice. If you want to use lists, then try hard to avoid these functions. The only 'cheap' operations for linked lists are the ones at the head of the list.
IF, RETURN
If you need RETURN
or RETURN-FROM
then the chance is high that you don't use Lisp's built-in data flow.
...
(if something (return ...))
...)
better written as
... (if something then else)
LOOP
for n from 0 to (1- something)
is just
for n below something
NCONC
Always use the return value of NCONC
. The return value is the concatenated list.
Built-in functionality
CL-USER 12 > (defun insert (number list)
(merge 'list list (list number) #'<))
INSERT
CL-USER 13 > (insert 10 (list 1 2 3 7 8 10 40))
(1 2 3 7 8 10 10 40)
Upvotes: 4
Reputation: 27424
In Common Lisp, is not a good practice to insert a value in a list, in the sense of modifying the list. What is instead common practice, is to write a function that, given a list, builds a new list with the element inserted at the right place.
For instance, if you want to insert a number in an already sorted list, you can do it with a simple recursive function:
(defun insert (number lst)
(cond ((null lst) (list number))
((<= number (car lst)) (cons number lst))
(t (cons (car lst) (insert number (cdr lst))))))
(insert 3 '(1 2 5 9))
(1 2 3 5 9)
In your function you use nconc
as it should modify not only the list, but also the variable that contains it. But this does not happen if the variable is an empty list. For instance:
> (setq a nil)
NIL
> (nconc a (list 4 5))
(4 5)
> a
NIL
You should always assign the result of the nconc
to the variable that you want to modify, like (setq a (nconc a (list 4 5)))
.
Upvotes: 4