查找并删除列表中指定元素的最后一次出现[racket]

Question

我已经开始编写一个函数，该函数应该查找列表中元素的最后一次出现。我的想法是使用search来计算指定符号的出现并将其返回。然后我会将计数传递给removeLast，这将删除元素。然后，我会减少removeLast的计数，以便于基本情况。从我看到使用set!通常是不好的做法。有没有更好/更优雅的方式来“记住”符号的最后一次出现。

(define (lastLess lis symbol) 
    (define count 0) 
    (set! count (search symbol lis count)) 
    (removeLast symbol lis count) 
) 

(define (search symbol lis count) 
    (cond ((null? lis) count) 
    ((eq? symbol (car lis)) (+ count (add1 (search symbol (cdr lis) count)))) 
    ((pair? (car lis))(+ count(+ 0 (search symbol (car lis) count)))) 
    (else (+ count(+ 0 (search symbol (cdr lis) count)))) 
    ) 
) 

(define (removeLast symbol lis count) 
    (cond ((null? lis) '()) 
    ((eq? count 0) (cdr lis)) 
    ((eq? symbol (car lis)) ((set! count (sub1 count)) 
          (cons (car lis)(removeLast symbol (cdr lis) count)) 
          ) 
          ) 
    ((pair? (car lis)) (removeLast symbol (car lis) count)) 
    (else (cons (car lis) (removeLast symbol (cdr lis) count))) 
    ) 
) 

运行代码是((set! count (sub1 count))(cons (car lis)(removeLast symbol (cdr lis) count))))抛出一个错误：

application: not a procedure; expected a procedure that can be applied to arguments given: # arguments...: '(e)

编辑：这是阶级的分配，所以多余的reverse s为不能接受的，我必须考虑巢名单。

Answer 1

您遇到的错误来自cond子句。你有多余的括号（set！count ...）。

你的问题是你对set的痴迷！ 此：

(define (lastLess lis symbol) 
    (define count 0) 
    (set! count (search symbol lis count)) 
    (removeLast symbol lis count)) 

本来可以做

(define (lastLess lis symbol) 
    (removeLast symbol lis (search symbol lis 0))) 

或我，你想分配，使用结果时，不止一个地方

(define (lastLess lis symbol) 
    (let ((count (search symbol lis 0))) 
    (if (< 0 count) ; noe or more occurences 
     (removeLast symbol lis count) 
     lis))) 

你的搜索程序将启动，这是很好列表中列出的列表没有完成列表中的列表，每列为(a b (c d b) a b)，您的过程将返回2而不是3. +可以有任意数量的参数所以你不需要嵌套它们。试试这个：

(define (search symbol lis count) 
    (cond ((null? lis) count) 
    ((eq? symbol (car lis)) (search symbol (cdr lis) (add1 count))) 
    ((pair? (car lis)) (search symbol (cdr lis) 
           (search symbol (car lis) count))) 
    (else (search symbol (cdr lis) count)))) 

请注意如何处理配对。现在您的removeLast不应该跳过计数为零但符号匹配且计数为1时得到的任何数据。

祝您好运！

Answer 2

您应该为此使用内置程序。特别是，注意remove删除的lis的第一元素等于symbol，所以去除最后元素倒车列表的一个简单的问题：

(define (lastLess lis symbol) 
    (reverse (remove symbol (reverse lis)))) 

(lastLess '(1 2 3 4 5 1) 1) 
=> '(1 2 3 4 5) 

上述解决方案不要求根本不使用set!，正如你怀疑的那样，不推荐 - 虽然可以解决这个问题，但是在列表中优先选择功能性解决方案。

当然，可以编写一个更有效的解决方案，一个只能遍历列表一次，但问问自己：你真的需要增加这种解决方案的复杂性吗？高性能如此重要？如果答案是否定的，那么坚持一个更简单，更清晰的解决方案。

Answer 3

这仍然使用集合，但是我认为这是一个更优雅的解决方案，因为该集合在作为foldr作为参数传递的匿名函数的闭包中使用。如果发现第一个匹配（记得从尾部开始工作，它会自动失效以作为缺点工作）。因为foldr从列表的尾端运行，所以不需要额外的遍历。make-remover是一个功能过程（一个输入将会总是映射到相同的输出），但输出是无功能的，但它不是一个问题，因为你只使用它一次并扔掉它（而且你不会错过一对一的映射）

(define (remove-last x L) 
(let ((proc (make-remover x))) 
    (foldr proc '() L))) 


(define (make-remover removee) 
(let ((active? #t)) 
    (lambda (x y) 
    (cond ((not active?) (cons x y)) 
     ((eq? x removee) (begin (set! active? #f) y)) 
     (else (cons x y)))))) 

这不会遍历树（在嵌套列表的工作），但它不应该是可怕的难以修改foldr相似的foldr相似树，将在子列表FOLDR应用程序到他们面前。