LISP function always returning nil

(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

Answers (2)

Rainer Joswig
Rainer Joswig

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

Renzo
Renzo

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

Related Questions