LISP function always returning nil

Question

(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...

Nconc is destructive in the sense that it changes the last cdr of all but its last argument. It returns the concatenated list. When it's first argument is nil,there's nothing there to modify. Nconc is just a function ,so it can't modify outside variable bindings — Joshua Taylor
– Joshua Taylor, Commented Nov 26, 2015 at 15:08

Renzo · Accepted Answer · 2015-11-26 14:14:56Z

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))).

Rainer Joswig · Accepted Answer · 2015-11-26 16:35:25Z

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)

Collectives™ on Stack Overflow

LISP function always returning nil

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related