Scheme - Inserting a number in a List

Question

I have this code :

(define (Insert value list)
  (if (null? list) (list value))
  (if (< value (car list)) (list (Insert (value list))))
  (Insert (cdr list) list))

I want this code to take a list (assuming it's in low to increasing order of integers) and insert a number in the correct place. This code does not work but I don't know why. Anyone know?

There's a fundamental error in here, in the way you're building the output list. Use `cons` for that, refer to your text book. — Óscar López, Dec 05 '16 at 00:18

Óscar López · Accepted Answer · 2016-12-05T00:13:50.223

You have a bunch of errors. First, let's see how you can fix your implementation:

(define (insert value lst)
  (cond ((null? lst)          ; if the list is empty
         (list value))        ; then return a single-element list
        ((<= value (car lst)) ; if current element >= value
         (cons value lst))    ; insert value in current position
        (else                 ; otherwise keep building the list
         (cons (car lst)      ; by adding current element
               (insert value (cdr lst)))))) ; and advancing recursion

Now, let's see what went wrong with your code:

You must not name a parameter list, that clashes with the built-in procedure of the same name - one you're actually using! it's clear that they'll conflict
The conditionals are incorrectly structured, if you have multiple conditions use a cond expression. Notice that the values of the first two ifs are discarded, because they're not nested (inside a procedure, only the value of the last expression is returned). Some Scheme interpreters will even raise an error when you write ifs without the corresponding else part
In the second condition, you must stop the recursion by consing the value with the rest of the list. It's better to stop as soon as possible, when element >= value, in case there are repeated elements
In the last condition, you're passing the parameters in the wrong order, and forgot about the value
Also in the last condition, you forgot to cons the current element

@A.L no, alternatively you can nest `if`s. It's ugly, but works. What you _have to_ ensure is that the conditions are mutually exclusive — Óscar López, Dec 04 '16 at 23:35
What about using cons? I only have experience with using append. Would append work in this case? Or is cons necessary — A.L, Dec 04 '16 at 23:57
`cons` is the most fundamental operation for building new data in Scheme, you should get acquainted with it as soon as possible. Always prefer `cons` over `append`, for efficiency reasons. See this [post](http://stackoverflow.com/q/19213072/201359). — Óscar López, Dec 05 '16 at 00:02

score 1 · Answer 2 · answered Dec 04 '16 at 23:33

You have several errors in your code. First, in Scheme it is more natural to include else clauses for ifs. Also, you had wrong the last if. Here is a version of your code with minor modifications:

(define (Insert value lst)
  (if (null? lst) (list value)
      (if (< value (car lst))
          (cons value lst)
          (cons (car lst) (Insert value (cdr lst))))))

Note that you have to provide actions for when the value is less than the head of the list and when it is not, and you have to construct the returning value using cons.

Scheme - Inserting a number in a List

2 Answers2