scheme - 重复过滤后的列表顺序

Question

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

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

是否有一种简单的替代方法可以保持每个副本的第一个实例的顺序？

Answer 1

解决这个问题的最好方法是使用 Racket 的内置 remove-duplicates程序。但当然，您希望从头开始实现该解决方案。这是一种使用惯用 Racket 的方法，请注意我们可以使用 member (另一个内置函数)代替 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 所示:

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

上面使用了一个 named let用于迭代，并展示了如何编写 tail-recursive执行。它按预期工作:

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

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