Removing the minimum elements of a list in Scheme

Question

Is there any convenient way to remove the minimum element? I can only think of one way, finding the minimum and then removing it. But that seems to be inefficient.

(define (min set)
    (let ((x (car set))
          (rest (cdr set)))
      (if (null? rest)
          x
          (if (< x (min rest))
              x
              (min rest)))))

(define (remove x set)
  (let ((s (car set)))
    (if (= x s)
        (cdr set)
        (cons s (remove x (cdr set))))))

(define (remove-min set)
    (remove (min set) set))
(remove-min `(4 1 4 5))

Answer 1

If you want to keep a pure function, no. At best you end up building two lists at once, which may save procedural steps but requires more stack memory. The lists can by built in reverse by consing an accumulator which requires a reverse at the end. You can't do the old stanby way of building list via a calls to cons in the tail position because you aren't sure that is going to be your list

(define (remove-min L)
  (cond ((number? L) L)
        ((or (null? L) (not (pair? L)))
         (list "undefined value for remove-min" L)) ;could be error
        ((not (number? (car L)))
         'error) 
        (else  
    (let loop ((L (cdr L))   (min (car L)) 
               (current '()) (alt (list (Car L))))
       (cond ((null? L) (reverse current))
             ((or (not (pair? L)) (not (number? (car L))))
              'error)
             ((< (car L) min) 
              (loop (cdr L)  (car L) 
                    alt      (cons (car L) alt)))
             ((= (car L) min)
              (loop (cdr L) min
                    current (cons (car L) alt)))
             (else
              (loop (cdr L)  min 
                    (cons (car L) current) (cons (car L) alt))))))))

(remove-min `(4 1 4 5)) =-> (4 4 5)
(remove-min '(1 2 3 1 2 3)) =-> (2 3 2 3)

Less pure solutions would be the above with a tail modulo cons implemented. If you don't mind modifying the original list the following will work.

(define (remove-min! Lst)
  (cond ((number? Lst) Lst)
        ((or (null? Lst) (not (pair? Lst)))
         'error) ;could be error
        ((not (number? (car Lst)))
         'error) 
        (else 
     (let loop ((L (cdr Lst)) (min (car Lst))   (prior-cons Lst) 
               (poss (list #f))      (rests (list (cdr Lst))))
       (cond ((null? L) 
              (map (lambda (pos rest)
                      (if pos 
                          (set-cdr! pos rest) 
                          (set! Lst rest)))
                    poss
                    rests)
              Lst)
             ((or (not (pair? L)) (not (number? (car L))))
              'error)
             ((< (car L) min) 
              (loop (cdr L)     (car L)  L
                    (list prior-cons)  (list (cdr L))))
             ((= (car L) min) ;;bug here, fixed
              (if (eq? L (car rests))
                  (loop (cdr L) min prior-cons
                        poss 
                       (cons (cdar rests) 
                         (cdr rests)))                            
                  (loop (cdr L) min L
                       (cons prior-cons poss)
                       (cons (cdr L) rests))))
             (else
              (loop (cdr L) min  L  
                    poss     rests)))))))

(remove-min! (list 4 1 4 5)) =-> (4 4 5)
(remove-min (list 1 2 3 1 2 3 1 2 3)) =->(2 3 2 3 2 3)

;Bug fixed :) (remove-min! (list 4 1 1 5 3 6)) =-> (4 1 5 3 6)

Answer 2

Finding the minimum and then removing it is a valid approach, but it can be done with less code using the min and remove* built-in functions in the interpreter. For instance, in Racket:

(define (remove-min lst)
  (remove* (list (apply min lst)) lst))

This is how it works, notice that it removes all occurrences of the minimum element:

(remove-min '(4 1 4 5 1 3))
=> '(4 4 5 3)

We're talking of a different kind of efficiency here - sure, we're iterating twice over the input list (but that's not a problem for small lists, and besides is still an O(n) solution). But using built-in procedures is much more efficient regarding your own time, we didn't have to write and test new code, just compose some well-known functions. That's the kind of "efficiency" you should aim for when writing code in a functional language!

Anyway, if you really want to write your own code, both of your implementations can be improved: min can iterate less (you're calling the recursion twice in each step!) and remove can delete all occurrences at once, and both procedures need better handling of edge cases (what happens if the input list is empty?) - again, I wouldn't recommend reinventing the wheel, but here you go:

(define (min set)
  (define (loop set m)
    (cond ((null? set) m)
          ((< (car set) m)
           (loop (cdr set) (car set)))
          (else
           (loop (cdr set) m))))
  (if (null? set)
      #f
      (loop (cdr set) (car set))))

(define (remove x set)
  (cond ((null? set)
         '())
        ((= (car set) x)
         (remove x (cdr set)))
        (else
         (cons (car set) (remove x (cdr set))))))