SHARE
TWEET

Untitled

a guest Nov 16th, 2019 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ;:PS5
  2. ;;Ruoyu Wu               rw186
  3. ;;Cindy Weng             cw357
  4. (require racket/base)
  5. (require racket/stream)
  6.  
  7. ;;2.1
  8. ;;1.
  9. ;(map list '(1 2 3) '(4 5 6))
  10. (define cart
  11.   (lambda (A B)
  12.     (cond ((null? A) '())
  13.           (else (append (map (lambda (x) (list (car A) x)) B) (cart (cdr A) B))))))
  14.  
  15. (cart '(1 2 3) '(4 5 6))
  16.  
  17. ;;2.
  18. (define fcn?
  19.   (lambda (S)
  20.     (letrec ((helper
  21.               (lambda (S lst)
  22.                 (cond ((null? S) #t)
  23.                       ((member (caar S) lst) #f)
  24.                       (else (helper (cdr S) (cons (caar S) lst)))))))
  25.       (helper S '()))))
  26.  
  27.  
  28. ;;3.
  29. (define pi1
  30.   (lambda (S)
  31.     (map (lambda (x) (car x)) S)))
  32.  
  33. (pi1 '((1 6) (2 4) (3 5)))
  34.  
  35. (define pi2
  36.   (lambda (S)
  37.     (map (lambda (x) (cadr x)) S)))
  38.  
  39. (pi2 '((1 6) (2 4) (3 5)))
  40.  
  41. ;;4.
  42. (define diag
  43.   (lambda (A)
  44.     (map (lambda (x) (list x x)) A)))
  45.  
  46. (diag '(1 2 3 4 5))
  47.    
  48.  
  49. ;;5.
  50. (define diag?
  51.   (lambda (D)
  52.     (cond ((null? D) #t)
  53.           ((not (equal? (caar D) (cadar D))) #f)
  54.           (else (diag? (cdr D))))))
  55.  
  56. (cadar '((1 6) (2 4) (3 5)))
  57. (diag? '((1 1) (2 4) (3 3)))
  58. (diag? '((1 1) (2 2) (3 3)))
  59.  
  60. ;;6.
  61. (define diag-inv
  62.   (lambda (Delta)
  63.     (map (lambda (x) (car x)) Delta)))
  64.  
  65. (diag-inv '((1 1) (2 2) (3 3)))
  66.  
  67.  
  68. ;;7.
  69. ;;(a)
  70. ;;If A has 2 elements denoted as a and b, P(A) contains the empty set, {a}, {b}, and
  71. ;;{a, b}. Therefore, P(A) has 4 elements.
  72.  
  73. ;;(b)
  74. ;;If A has 2 elements denoted as a, P(A) contains the empty set and {a}. Therefore,
  75. ;;P(A) has 2 elements.
  76.  
  77. ;;(c)
  78. ;;If A has 2 elements denoted as a, b, and c, P(A) contains the empty set, {a}, {b},
  79. ;;{c}, {a, b}, {a, c}, {b, c}, and {a, b, c}. Therefore, P(A) has 8 elements.
  80.  
  81. ;;(d)
  82. ;;P(A) has 1 element: the empty set.
  83.  
  84. ;;(e)
  85. (define powerset
  86.   (lambda (A)
  87.     (cond ((null? A) '(()))
  88.         (else (let ((rest (powerset (cdr A))))
  89.                  (append rest
  90.                          (map (lambda (x) (cons (car A) x)) rest)))))))
  91.  
  92. (powerset '(1 2 3))
  93.  
  94. ;;(f)
  95. ;;If the set A has n elements, the power set of A will have 2^n elements.
  96.  
  97. ;;(g)
  98. ;Proposition
  99. ;I want to prove that for any natural number n >= 0, if the set A has n elements,
  100. ;the power set of A (denoted as P(A)) will have 2^n elements.
  101. ;
  102. ;Induction variable
  103. ;The variable that I will be doing induction on is n.
  104. ;
  105. ;Base case
  106. ;When n=0, P(A) contains the empty set, so P(A) has 1 element.
  107. ;2^0 = 1. Therefore, the proposition holds for the base case.
  108. ;
  109. ;Induction hypothesis
  110. ;Assume that for some n > 0, that for all k > 0 and k <= n, if the set A has k
  111. ;elements, the power set of A (denoted as P(A)) will have 2^k elements.
  112. ;(Induction hypothesis)
  113. ;
  114. ;Inductive step
  115. ;Show that if the set A has n+1 elements, the power set of A (denoted as P(A))
  116. ;will have 2^(n+1) elements.
  117. ;
  118. ;Let S be an arbitrary set with n elements, and let x be an element that is not
  119. ;contained in the set S.
  120. ;By I.H., we know the P(S) should have 2^n elements.
  121. ;Now, we consider the set A = (cons x S).
  122. ;The power set of A includes all sets in P(S), since a subset of S is also a subset
  123. ;of A. Note that none of those sets contains x. Therefore, the rest of the sets in
  124. ;P(A) are subsets of A that contain x, which are equivalent to all the subsets of S
  125. ;but with x added to each one of them. Therefore, A has n+1 elements, and P(A) will
  126. ;have 2^n + 2^n = 2^(n+1) elements. The proposition is thus proved.
  127.  
  128. ;;(h)
  129. ;Because if A has size n, the size of P(A) would be 2 to the power of n.
  130.  
  131.  
  132. ;;2.2
  133.  
  134. (define ones  (stream-cons 1 ones))
  135. (define integers (stream-cons 1 (add-streams ones integers)))
  136.  
  137. (define add-streams
  138.   (lambda ((a <stream>) (b <stream>))
  139.     (cond ((stream-empty? a) b)
  140.           ((stream-empty? b) a)
  141.           (else (stream-cons (+ (stream-first a) (stream-first b))
  142.                                 (add-streams (stream-rest a) (stream-rest b)))))))
  143.  
  144. ;;5.
  145.  
  146. ;;6.
  147. (define diag-inv-stream
  148.   (lambda (Delta)
  149.     (stream-map (lambda (x) (car x)) Delta)))
  150. (stream->listn (diag-inv-stream (cart-streams integers integers)) 10)
  151.  
  152. ;;7.
  153.  
  154. (define powerset-stream
  155.   (lambda (A)
  156.     (cond ((stream-empty? A) '(()))
  157.         (else (let ((rest (powerset-stream (stream-rest A))))
  158.                  (add-streams rest
  159.                          (stream-map (lambda (x) (cons (car A) x)) rest)))))))
  160.  
  161.  
  162. (stream->listn (powerset-stream integers) 5)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top