schemeracket

# Extracting data of pairs without the data that encountered before

I have a data which inside of some pairs. But some pairs go a pair that encountered before. I don't want to extract same data again. For example I have a data like this.

So, as you see p3's first item goes p1. However p0's first item has gone that element before.

First, I have defined all pairs first like this

``````(define p2 (cons 2 3))
(define p4 (cons 4 5))
(define p1 (cons p2 1))
(define p3 (cons p1 p4))
(define p0 (cons p1 p3))
``````

then I extracted all pairs by using recursion

``````(define (extract pair)
(if (pair? pair) (append (extract (car pair)) (extract (cdr pair))) (list pair)))
``````

And I get the result of

``````(2 3 1 2 3 1 4 5)
``````

However, I don't want to extract `(2 3 1)` again because I have encountered before. How can I detect that?

Solution

• Try to use `(union x y)` instead of `(append x y)`:

``````(define (extract pair)
(if (pair? pair)
(union (extract (car pair)) (extract (cdr pair)))
(list pair)))

(define (union A B)
(cond [(empty? A) B]
[else
(let ([C (union (rest A) B)])
(cond [(member (first A) C) C]
[else (cons (first A) C)]))]))

(define p2 (cons 2 3))
(define p4 (cons 4 5))
(define p1 (cons p2 1))
(define p3 (cons p1 p4))
(define p0 (cons p1 p3))

(extract p0)
``````