删除 Scheme 中列表的最小元素

Question

有什么方便的方法去掉最小元素吗？我只能想到一种方法，找到最小值然后将其删除。但这似乎效率低下。

(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

找到最小值然后将其删除是一种有效的方法，但可以使用解释器中的 min and remove* 内置函数以更少的代码完成。例如，在球拍中：

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

这就是它的工作原理，请注意它删除了所有次出现的最小元素：

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

我们在这里讨论的是另一种效率 - 当然，我们在输入列表上迭代两次（但这对于小列表来说不是问题，而且仍然是 O(n) 解决方案） .但是使用内置程序比您自己的时间更有效，我们不必编写和测试新代码，只需编写一些众所周知的函数即可。这就是您在用函数式语言编写代码时应该追求的 "efficiency"！

无论如何，如果你真的想编写自己的代码，你的两个实现都可以改进：min 可以减少迭代（你调用递归两次在每个步骤中！）和 remove 可以一次删除所有出现的事件，并且这两个过程都需要更好地处理边缘情况（如果输入列表为空会发生什么？）-再次，我不建议重新发明轮子, 但现在开始:

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

Answer 2

如果你想保留一个纯函数，不行。充其量您最终一次构建两个列表，这可能会节省程序步骤但需要更多堆栈内存。列表可以通过 consing 一个累加器反向构建，该累加器最后需要反向。你不能通过在尾部位置调用 cons 来构建列表的旧 stanby 方法，因为你不确定那将是你的列表

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

较不纯粹的解决方案是上面实施的尾模缺点。如果您不介意修改原始列表，则以下内容将起作用。

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

；错误修复:) (remove-min! (list 4 1 1 5 3 6)) =-> (4 1 5 3 6)

删除 Scheme 中列表的最小元素

Removing the minimum elements of a list in Scheme

scheme