重复过滤后的列表顺序 [英] List order after duplicate filtering

问题描述

我正在尝试自学函数式语言思维，并编写了一个过程，该过程接受一个列表并返回一个过滤掉重复项的列表.这是有效的，但输出列表按在输入列表中找到每个重复项的 last 实例的顺序排序.

I'm trying to teach myself functional language thinking and have written a procedure that takes a list and returns a list with duplicates filtered out. This works, but the output list is sorted in the order in which the last instance of each duplicate item is found in the input list.

(define (inlist L n)
  (cond
   ((null? L) #f)
   ((= (car L) n) #t)
   (else (inlist (cdr L) n))
   ))

(define (uniquelist L)
 (cond
   ((null? L) '())
   ((= 1 (length L)) L)
   ((inlist (cdr L) (car L)) (uniquelist (cdr L)))
   (else (cons (car L) (uniquelist (cdr L))))
   ))

所以..

(uniquelist '(1 1 2 3)) => (1 2 3)

...但是...

(uniquelist '(1 2 3 1)) => (2 3 1)

是否有一个简单的替代方法来维护每个重复项的 first 实例的顺序?

Is there a simple alternative that maintains the order of the first instance of each duplicate?

推荐答案

解决这个问题的最好方法是使用 Racket 的内置 remove-duplicates 程序.但当然，您希望从头开始实施解决方案.这是使用惯用 Racket 的一种方式，注意我们可以使用 member(另一个内置函数)代替inlist:

The best way to solve this problem would be to use Racket's built-in remove-duplicates procedure. But of course, you want to implement the solution from scratch. Here's a way using idiomatic Racket, and notice that we can use member (another built-in function) in place of inlist:

(define (uniquelist L)
  (let loop ([lst (reverse L)] [acc empty])
    (cond [(empty? lst)
           acc]
          [(member (first lst) (rest lst))
           (loop (rest lst) acc)]
          [else
           (loop (rest lst) (cons (first lst) acc))])))

或者我们可以使用标准 Scheme 编写相同的程序，如 SICP 所示:

Or we can write the same procedure using standard Scheme, as shown in SICP:

(define (uniquelist L)
  (let loop ((lst (reverse L)) (acc '()))
    (cond ((null? lst)
           acc)
          ((member (car lst) (cdr lst))
           (loop (cdr lst) acc))
          (else
           (loop (cdr lst) (cons (car lst) acc))))))

以上使用了 命名 let 进行迭代，并展示如何编写 tail-递归实现.它按预期工作:

The above makes use of a named let for iteration, and shows how to write a tail-recursive implementation. It works as expected:

(uniquelist '(1 1 2 3))
=> '(1 2 3)

(uniquelist '(1 2 3 1))
=> '(1 2 3)

这篇关于重复过滤后的列表顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！