2

我正在尝试编写一个方案函数，该函数将返回在输入列表中找到的唯一原子，这样。

> (unique-atoms '(a (b) b ((c)) (a (b))))
(a c b)
> (unique-atoms '(a . a))
(a)
> (unique-atoms '())
()

我在想这样的事情作为开始

(define (unique-atoms l)
  (if (null? l)
      '()
   (eq? (car (l) unique-atoms(cdr (l))))))

但我不知道如何收集唯一的原子，并在递归检查所有内容的同时创建一个新列表。

4

4 回答 4

1

这个问题有两个部分：

  1. 您需要找到一种方法来访问给定表单的每个元素，递归到子列表中。
  2. 您需要一种方法来收集正在访问的独特元素。

这是第一部分的解决方案：

(define (recursive-fold visitor initial x)
  (let recur ((value initial)
              (x x))
    (cond ((null? x) value)
          ((pair? x) (recur (recur value (car x)) (cdr x)))
          (else (visitor x value)))))

我把它留给你来实现第二部分。

于 2013-06-30T02:26:50.667 回答
1

以下步行list，逐项。如果该next值本身是一个列表，则进行递归调用(append next rest)- 也就是说，正如list所走的那样，我们同时展平了子列表。

我们使用（尾）递归函数 ,looking来遍历列表并累积rslt. next当不在时，我们添加到结果中rslt。

(define (uniquely list)
  (let looking ((rslt '()) (list list))
    (if (null? list)
        rslt
        (let ((next (car list))
              (rest (cdr list)))
          (if (list? next)
              (looking rslt (append next rest))
              (looking (if (memq next rslt)
                           rslt
                           (cons next rslt))
                       rest))))))
> (uniquely '(a b (a b) ((((a))))))
(b a)

如果您真的希望代码适用于“不正确的列表”，那么'(a . a)谓词可能需要更改。null?list?

于 2013-06-30T04:20:58.507 回答
0

我找到了一个半解决方案，其中删除了非唯一项，尽管这不适用于原子 b 和带有 b 的列表，例如 '(b (b))

(define (uniqueAtoms l)
  (cond ((null? l)
         '())
        ((member (car l) (cdr l))
         (uniqueAtoms (cdr l)))
        (else
         (cons (car l) (uniqueAtoms (cdr l))))))
于 2013-06-30T04:23:14.470 回答
-1

用各种列表结构解决这个问题最简单的方法就是把它分成两部分

1) 展平然后列出 - 这会产生一个没有子列表的正确列表

; if you use Racket, you can use the build-in flatten procedure
; otherwise this one should do
(define (flatten expr)
  (let loop ((expr expr) (res '()))
    (cond 
      ((empty? expr) res)
      ((pair? expr)  (append (flatten (car expr)) (flatten (cdr expr))))
      (else          (cons expr res)))))

2）找到这个正确列表的所有唯一成员

(define (unique-atoms lst)
  (let loop ((lst (flatten lst)) (res '()))
    (if (empty? lst)
        (reverse res)
        (let ((c (car lst)))
          (loop (cdr lst) (if (member c res) res (cons c res)))))))

测试：

; unit test - Racket specific
(module+ test
  (require rackunit)
  (check-equal? (unique-atoms '(a (b) b ((c)) (a (b)))) '(a b c))
  (check-equal? (unique-atoms '(a (b) b ((c . q)) (a (b . d)))) '(a b c q d))
  (check-equal? (unique-atoms '(a . a)) '(a))
  (check-equal? (unique-atoms '(a b (a b) ((((a)))))) '(a b))
  (check-equal? (unique-atoms '()) '()))
于 2013-07-01T21:07:18.543 回答