;; ==================================
;; CMPU 145, Spring, 2019
;; Cartesian Product Implementation
;; February 19, 2019
;; ==================================
#lang racket
(include "asmt-helper.scm")
(header "Sample Code" "A Cartesian Product Implementation")
(problem "cross-product, an implementation of the function formerly known as Cartesian product")
;; Cross product implementation
;; - Inputs: input-list1, input-list2: two lists representing sets (no duplicates)
;; - Output: A list of lists representing a set of ordered pairs, namely,
;; the cross product of input-list1 and input-list2
(define cross-product
(lambda (input-list1 input-list2)
;; Base case: input-list1 is empty, so the cross product is empty.
;; Recursive case: input-list1 has at least one element.
(if (null? input-list1)
'()
;; Since we generate two lists, we use append to combine them.
(append
;; For each element of input-list2, make a pair starting with
;; (first input-list1)
(map (lambda (z)
(list (first input-list1) z))
input-list2)
;; Generate the pairs for the rest of input-list1.
(cross-product (rest input-list1) input-list2)))))
(tester '(cross-product '(1 2 3) '(x y)))
(tester '(cross-product '() '(1 2 3)))
(tester '(cross-product '(1 2 3) '()))
(tester '(cross-product '() '()))
(tester '(cross-product '((1 2) (1 5)) '(A B)))
(problem "Keep all pairs that satisfy a given predicate")
;; Keep pairs
;; - Inputs:
;; - pred, a predicate that takes two inputs
;; - pairs, a list of pairs
;; - Output: A list of all pairs (a b) such that (pred a b) is true.
(define keep-pairs
(lambda (pred pairs)
(cond
;; Base Case: There are no pairs, so return the empty list.
((null? pairs)
'())
;; Recursive Case: The first pair in PAIRS satisfies the predicate,
;; so we cons it onto whatever the recursive function call returns.
;;
;; NOTE: Because (first pairs) is a pair, such as (a b), we must use
;; the built-in APPLY function to get the effect of (pred a b).
;; Another option would be to write:
;; (pred (first (first pairs)) (second (first pairs)))
((apply pred (first pairs))
(cons (first pairs)
(keep-pairs pred (rest pairs))))
;; Recursive Case 2: The first pair does NOT satisfy PRED, so ignore
;; the first pair and just return whatever the recursive function call
;; returns.
(else
(keep-pairs pred (rest pairs))))))
;; First, we test by providing the set of pairs explicitly
(tester '(keep-pairs < '((1 1) (1 2) (1 3) (2 1) (2 2) (2 3)
(3 1) (3 2) (3 3))))
(newline)
;; We can also let CROSS-PRODUCT construct the list of pairs for us
(tester '(keep-pairs < (cross-product '(1 2 3) '(1 2 3))))
(tester '(keep-pairs = (cross-product '(1 2 3) '(1 2 3))))
(tester '(keep-pairs (lambda (a b) (not (= a b)))
(cross-product '(1 2 3) '(1 2 3))))
(newline)
;; And we can have different sets in the cross product
(tester '(keep-pairs = (cross-product '(1 2 3 4) '(2 4 6 8))))
(tester '(keep-pairs >= (cross-product '(1 2 3 4) '(2 4 6 8))))