Ladies_Man

Работа с множествами

Dec 26th, 2013
209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scheme 1.19 KB | None | 0 0
  1. (define (delete xs x)
  2.   (define (iter xs ys x)
  3.     (if (null? xs)
  4.       (cons x (reverse ys))
  5.         (if (equal? (car xs) x)
  6.           (iter (cdr xs) ys x)
  7.           (iter (cdr xs) (cons (car xs) ys) x ))))
  8. (iter xs '() (car xs)))
  9.  
  10. (define (list->set xs)
  11.   (define (iter xs ys)
  12.     (if (null? xs)
  13.     ys
  14.     (iter (cdr (delete xs (car xs))) (cons (car xs) ys))))
  15. (iter xs '()))
  16.  
  17. (define (set? xs)
  18.   (if (null? xs)
  19.     #t
  20.     (= (length (list->set xs)) (length xs))))
  21.  
  22. (define (union xs ys)
  23.   (list->set (append xs ys)))
  24.  
  25. (define (included? x xs)
  26.   (if (null? xs)
  27.     #f
  28.     (begin (if (equal? x (car xs))
  29.       #t
  30.       (included? x (cdr xs))))))
  31.  
  32. (define (intersection xs ys)
  33.   (define (iter xs zs)
  34.     (if (null? xs)
  35.     zs
  36.     (iter (cdr xs) (if (included? (car xs) ys)
  37.       (cons (car xs) zs)
  38.       zs))))
  39. (iter xs '()))
  40.  
  41. (define (difference xs ys)
  42.   (define (iter xs zs)
  43.     (if (null? xs)
  44.       (reverse zs)
  45.       (iter (cdr xs) (if (included? (car xs) ys)
  46.         zs
  47.         (cons (car xs) zs)))))
  48. (iter xs '()))
  49.    
  50. (define (symmetric-difference xs ys)
  51.   (union (difference xs ys) (difference ys xs)))
  52.  
  53. (define (set-eq? xs ys)
  54.       (null? (difference xs ys)))
Add Comment
Please, Sign In to add comment