;:PS5
;;Ruoyu Wu               rw186
;;Cindy Weng             cw357
(require racket/base)
(require racket/stream)

;;2.1
;;1.
;(map list '(1 2 3) '(4 5 6))
(define cart
  (lambda (A B)
    (cond ((null? A) '())
          (else (append (map (lambda (x) (list (car A) x)) B) (cart (cdr A) B))))))

(cart '(1 2 3) '(4 5 6))

;;2.
(define fcn?
  (lambda (S)
    (letrec ((helper
              (lambda (S lst)
                (cond ((null? S) #t)
                      ((member (caar S) lst) #f)
                      (else (helper (cdr S) (cons (caar S) lst)))))))
      (helper S '()))))


;;3.
(define pi1
  (lambda (S)
    (map (lambda (x) (car x)) S)))

(pi1 '((1 6) (2 4) (3 5)))

(define pi2
  (lambda (S)
    (map (lambda (x) (cadr x)) S)))

(pi2 '((1 6) (2 4) (3 5)))

;;4.
(define diag
  (lambda (A)
    (map (lambda (x) (list x x)) A)))

(diag '(1 2 3 4 5))


;;5.
(define diag?
  (lambda (D)
    (cond ((null? D) #t)
          ((not (equal? (caar D) (cadar D))) #f)
          (else (diag? (cdr D))))))

(cadar '((1 6) (2 4) (3 5)))
(diag? '((1 1) (2 4) (3 3)))
(diag? '((1 1) (2 2) (3 3)))

;;6.
(define diag-inv
  (lambda (Delta)
    (map (lambda (x) (car x)) Delta)))

(diag-inv '((1 1) (2 2) (3 3)))


;;7.
;;(a)
;;If A has 2 elements denoted as a and b, P(A) contains the empty set, {a}, {b}, and
;;{a, b}. Therefore, P(A) has 4 elements.

;;(b)
;;If A has 2 elements denoted as a, P(A) contains the empty set and {a}. Therefore,
;;P(A) has 2 elements.

;;(c)
;;If A has 2 elements denoted as a, b, and c, P(A) contains the empty set, {a}, {b},
;;{c}, {a, b}, {a, c}, {b, c}, and {a, b, c}. Therefore, P(A) has 8 elements.

;;(d)
;;P(A) has 1 element: the empty set.

;;(e)
(define powerset
  (lambda (A)
    (cond ((null? A) '(()))
        (else (let ((rest (powerset (cdr A))))
                 (append rest
                         (map (lambda (x) (cons (car A) x)) rest)))))))

(powerset '(1 2 3))

;;(f)
;;If the set A has n elements, the power set of A will have 2^n elements.

;;(g)
;Proposition
;I want to prove that for any natural number n >= 0, if the set A has n elements,
;the power set of A (denoted as P(A)) will have 2^n elements.
;
;Induction variable
;The variable that I will be doing induction on is n.
;
;Base case
;When n=0, P(A) contains the empty set, so P(A) has 1 element.
;2^0 = 1. Therefore, the proposition holds for the base case.
;
;Induction hypothesis
;Assume that for some n > 0, that for all k > 0 and k <= n, if the set A has k
;elements, the power set of A (denoted as P(A)) will have 2^k elements.
;(Induction hypothesis)
;
;Inductive step
;Show that if the set A has n+1 elements, the power set of A (denoted as P(A))
;will have 2^(n+1) elements.
;
;Let S be an arbitrary set with n elements, and let x be an element that is not
;contained in the set S.
;By I.H., we know the P(S) should have 2^n elements.
;Now, we consider the set A = (cons x S).
;The power set of A includes all sets in P(S), since a subset of S is also a subset
;of A. Note that none of those sets contains x. Therefore, the rest of the sets in
;P(A) are subsets of A that contain x, which are equivalent to all the subsets of S
;but with x added to each one of them. Therefore, A has n+1 elements, and P(A) will
;have 2^n + 2^n = 2^(n+1) elements. The proposition is thus proved.

;;(h)
;Because if A has size n, the size of P(A) would be 2 to the power of n.


;;2.2

(define ones  (stream-cons 1 ones))
(define integers (stream-cons 1 (add-streams ones integers)))

(define add-streams
  (lambda ((a <stream>) (b <stream>))
    (cond ((stream-empty? a) b)
          ((stream-empty? b) a)
          (else (stream-cons (+ (stream-first a) (stream-first b))
                                (add-streams (stream-rest a) (stream-rest b)))))))

;;5.

;;6.
(define diag-inv-stream
  (lambda (Delta)
    (stream-map (lambda (x) (car x)) Delta)))
(stream->listn (diag-inv-stream (cart-streams integers integers)) 10)

;;7.

(define powerset-stream
  (lambda (A)
    (cond ((stream-empty? A) '(()))
        (else (let ((rest (powerset-stream (stream-rest A))))
                 (add-streams rest
                         (stream-map (lambda (x) (cons (car A) x)) rest)))))))


(stream->listn (powerset-stream integers) 5)