Delete element from List in Scheme

问题:

I have list in this form

( (1 3) (2 2) (3 1) (4 5) (5 1)))

and I want to delete an item let's say (3 1)

So the result will be

( (1 3) (2 2) (4 5) (5 1)))

I have written something like this and I do not know why it is not running correctly.

(define (deleteItem list item)
  (cond
    ((equal? item (car  list)) (cdr list))
    (cons (car  list)(deleteItem(cdr list) item))))

回答1:

There's a built-in function for this, it's called remove:

(define lst
  '((1 3) (2 2) (3 1) (4 5) (5 1)))

(remove '(3 1) lst)
=> '((1 3) (2 2) (4 5) (5 1))

… But I guess you need to implement it from scratch. Some suggestions for your code:

• You should not use list as a parameter name, that'll clash with a built-in function. Let's call it lst instead
• You're missing the base case necessary form most list procedures: what happens if the list is empty?
• You're also missing the else part in the last condition

With all the above fixes in place, the procedure will work:

(define (deleteItem lst item)
  (cond ((null? lst)
         '())
        ((equal? item (car lst))
         (cdr lst))
        (else
         (cons (car lst) 
               (deleteItem (cdr lst) item)))))

(deleteItem lst '(3 1))
=> '((1 3) (2 2) (4 5) (5 1))

回答2:

The procedure already exists:

(remove '(3 1) '((1 3) (2 2) (3 1) (4 5) (5 1))))

Otherwise your procedure should look like this:

(define (deleteItem item list) 
  (cond 
    ((empty? list) '())
    ((equal? item (car list)) (cdr list))
    (else (cons (car list) (deleteItem item (cdr list))))))

You missed:

• the base case, (empty? list)
• the "else" in the final clause

and you shouldn't use list as a variable name because it shadows the build-in procedure list (but it will work).

回答3:

1) if consider the input list may be a simple list, or you just want to delete the item in the top-level of a nested list for example:

delete 2 from (1 2 3 4) will return (1 2 3)
delete 2 from (1 2 3 (2 3) 3 2 4) will return (1 3 (2 3) 3 4)

as we can see the 2nd example above, it just delete the item in the top-level of the nested list, within the inner list, we doesn't change it.

this code should be:

(define (deleteitem list1 item) 
( cond
    ((null? list1) ’())
    ((equal? (car list1) item) (deleteItem (cdr list1) item)) 
    (else (cons (car list1) (deleteitem (cdr list1) item)))
))

2) if consider the input list may be a nested list

for example:

input list: (1 2 3 (3 2 (2 4 (2 5 6) 2 5 6) 2 4) 2 3 (2 3 4))

and delete the element 2 in the input list

the output list should be: (1 3 (3 (3 (5 6) 5 6) 4) 3 (3 4))

and the code should be:

(define (delete2 list1 item) 
    ( cond
    ((null? list1) '())
    ((pair? (car list1)) (con (delete2 (car list1) item) (delete2 (cdr list1) item)))
    ((equal? (car list1) item) (delete2 (cdr list1) item)) 
    (else (cons (car list1) (delete2 (cdr list1) item)))
))