CSE 583 - Assignment 1 Discussion

Understanding the
Power Set
Recursive Thinking in Functional
Programming (OCaml & Python)

"The power of recursion lies in the way

it breaks down a problem into simpler
versions of itself."
 What is a Power Set?
Definition:

● The power set of a set S is the set of all possible subsets,

including:
○ The empty set ∅
○ The full set S itself

Example:
For a set {a, b, c}, the power set is:
{ {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

Goal:
Given a list in OCaml, return all subsets of that list.
Example: Menu Selection at a Restaurant

● Imagine you're at a restaurant with three available

dishes: Pizza, Pasta, and Salad.
● The power set represents all possible meal combinations:
○ {} (no meal)
○ {Pizza}, {Pasta}, {Salad} (choosing one dish)
○ {Pizza, Pasta}, {Pizza, Salad}, {Pasta, Salad}
(choosing two dishes)
○ {Pizza, Pasta, Salad} (choosing all three)
● This analogy helps illustrate how subsets represent
different choices from a given set.
 What is a Power Set?
Let’s analyze how subsets grow:
For a set {X, Y, Z}:

1. Start with the empty set: {∅}

2. Add each element one by one and take all previous subsets + new
ones.

Example Breakdown:

Takeaway:

● Every new subset is created by adding an element to existing

subsets.
● This is recursion!
Breaking Down the Recursive Approach

Key Insight:

If we know the power set of a smaller list, we can build

the power set of a larger list.

Recursive Formula:
Breaking Down the Recursive Approach
Contd.
Example for [3, 4]:

1. Base Case: powerset([]) = [[]]

2. Compute powerset([4]):
[[]] → [[], [4]]
3. Compute powerset([3, 4]):

[[], [4]] → [[], [4], [3], [3, 4]]

Conclusion:
Every subset is generated by either including or excluding
the first element.
 Power Set Algorithm
Key Insight: Each element in the list has two choices:
1️⃣ Exclude it from the subset.
2️⃣ Include it in the subset.

This recursive structure allows us to build all possible subsets.

Algorithm Breakdown

1️⃣ Base Case:

● If the list is empty, return [[]] (the power set of an empty

list contains only the empty set).

2️⃣ Recursive Step:

● Compute power set of the remaining elements.

● Create new subsets by adding the first element (h) to each
subset.
 OCaml Implementation
let rec map f lst =
match lst with
| [] -> []
| x :: xs -> (f x) :: (map f xs);;

let rec powerset lst =

match lst with
| [] -> [[]]
| x :: xs ->
let ps = powerset xs in
ps @ map (fun subset -> x :: subset) ps;;

(* Function to generate and return the power set *)

let generate_powerset lst = powerset lst;;

(* Example usage: *)
let test_input = [1; 2; 3];;
let result = generate_powerset test_input;;
 Step-by-Step Execution

1. Input: [3; 4; 10]

2. Compute powerset [10]: [[], [10]]
3. Compute powerset [4;10]: [[], [10], [4], [4,10]]
4. Compute powerset [3;4;10]: [[], [10], [4], [4,10], [3],
[3,10], [3,4], [3,4,10]]
5. Final Output: [[], [10], [4], [4,10], [3], [3,10],
[3,4], [3,4,10]]
 Python Equivalent

def powerset(lst):
if not lst:
return [[]]
ps = powerset(lst[1:])
return ps + [[lst[0]] + subset for subset in ps]
 Partitioning List Elements Using
an Equivalence Relation

What is Equivalence Partitioning?

● Given a list and an equivalence relation (a function

that returns true if two elements are equivalent),
partition the list into subsets where all elements in
each subset are equivalent to each other.

● Example with custom equivalence relation:

● Grouping students by grade level
○ Imagine a classroom where students are from
different grades.
○ The equivalence function determines whether two
students belong to the same grade.
○ Groups are formed accordingly, such as:
[[Grade 1 students], [Grade 2 students], [Grade 3
students]]

● Another Example: Categorizing Movies

○ A movie database may group movies by genre, using an
equivalence function that checks if two movies
belong to the same category.
 Approach & Logic

1. Iterate through each element in the list.

2. Check if it fits into an existing group (based on the
equivalence function).
3. If no existing group works, start a new group.
 OCaml Implementation
(* Helper function to group elements satisfying equivalence relation *)
let rec group_helper eq list group = match list with
| [] -> list, group (* Base case: return the remaining list and the group collected so far
*)
| h::t ->
if (eq h) then
(* If the element satisfies the equivalence function, add it to the group *)
group_helper eq t (group @ [h])
else
(* Otherwise, continue processing the remaining list *)
let (result_list, result_group) = group_helper eq t group in
(h::result_list), result_group;;

(* Function to partition list into equivalence classes *)

let rec equivs eq list = match list with
| [] -> [] (* Base case: an empty list returns an empty set of groups *)
| h::t ->
(* Extract elements belonging to the same group using group_helper *)
let (result_list, result_group) = group_helper (eq h) t [] in
(* Add the newly created group to the result and recurse on the remaining list *)
(h::result_group)::(equivs eq result_list) ;;

(* Example Usage *)
let test_input = [1; 2; 3; 4; 5; 6; 7; 8];;
let result = equivs (fun x y -> x mod 2 = y mod 2) test_input;;
 Recursive Strategy
The function follows a divide-and-conquer approach to partition elements into
equivalence classes.

Step-by-Step Recursive Breakdown:

1. Base Case:
○ If the input list is empty, return an empty list of groups.
2. Selecting a Pivot:
○ Pick the first element (h) from the list as a representative for its
equivalence class.
3. Grouping Elements:
○ Use group_helper to extract all elements equivalent to h from the
remaining list (t).
○ These extracted elements (along with h) form one equivalence class.
○ The remaining list consists of elements that do not belong to this
group.
4. Recursive Call on Remaining Elements:
○ Call the function recursively on the reduced list (elements not in h's
group).
○ This ensures all elements are processed and grouped correctly.
5. Combining Results:
○ The current equivalence class (group of h) is added to the result from
the recursive call.
 Step-by-Step Execution

1. Input List: [1; 2; 3; 4; 5; 6; 7; 8]

2. Start with an empty list of groups.
3. Extract one equivalence class at a time using
group_helper.
4. Recur on the remaining elements.
5. Efficiency Considerations:
a. Uses a helper function to efficiently extract
groups.
b. Avoids inserting elements one-by-one by filtering
equivalence groups first.
 Python Equivalent
def insert_into_group(eq, x, groups):
for group in groups:
if eq(x, group[0]):
group.append(x)
return groups
return groups + [[x]]

def equivs(eq, lst):

groups = []
for x in lst:
groups = insert_into_group(eq, x, groups)
return groups

# Example Usage
print(equivs(lambda x, y: x % 2 == y % 2, [1, 2, 3, 4, 5, 6, 7, 8]))
# Output: [[1, 3, 5, 7], [2, 4, 6, 8]]
 Goldbach’s Conjecture &
Prime Pair Sums
● What is Goldbach’s Conjecture?
○ Every even number greater than 2 can be expressed as the sum
of two prime numbers.

Example:
goldbach_pairs 10;;

(* Output: [(3, 7); (5, 5)] *)

goldbach_pairs 28;;

(* Output: [(5, 23); (11, 17)] *)

 Approach & Logic

1. Check if a number is prime

○ Create a helper function is_prime that returns true
if a number is prime.

2. Find two prime numbers that sum up to n

○ Iterate over numbers from 2 to n // 2.
○ Check if both p and n - p are prime.
○ If so, add (p, n - p) to the result list.
 OCaml Implementation
(* Helper function to check if a number is prime *)
let is_prime n =
let rec check d =
d * d > n || (n mod d <> 0 && check (d + 1)) in
n > 1 && check 2;;

(* Function to find all Goldbach pairs for a given even number *)

let goldbach_pairs n =
if n <= 2 || n mod 2 <> 0 then
failwith "Input must be a positive even number greater than 2."
else
let rec find_pairs p acc =
if p > n / 2 then acc (* Stop when p exceeds n/2 *)
else if is_prime p && is_prime (n - p) then
find_pairs (p + 1) ((p, n - p) :: acc) (* Add valid prime pair *)
else
find_pairs (p + 1) acc (* Continue searching *)
in find_pairs 2 [];;

(* Example Usage *)
let test_input = 10;;
let result = goldbach_pairs test_input;;

(* Print the result *)

let () =
List.iter (fun (a, b) -> Printf.printf "(%d, %d) " a b) result;
 Step-by-Step Execution

1. Input: goldbach_pairs 10
2. Iterate through possible prime numbers:
○ p = 2: 10 - 2 = 8 (not prime) → Skip
○ p = 3: 10 - 3 = 7 (prime) → Add (3,7)
○ p = 4: 10 - 4 = 6 (not prime) → Skip
○ p = 5: 10 - 5 = 5 (prime) → Add (5,5)
3. Final Output: [(3, 7); (5, 5)]
4. Uses a helper function (is_prime) to filter prime numbers.
5. Efficiently finds all valid pairs using recursion.
6. Avoids unnecessary checks by iterating only up to n / 2.
 Python Equivalent
def is_prime(n):
"""Check if a number is prime."""
if n < 2:
return False
for d in range(2, int(n ** 0.5) + 1):
if n % d == 0:
return False
return True

def goldbach_pairs(n):
"""Find all pairs of prime numbers that sum up to the given even
number."""
if n <= 2 or n % 2 != 0:
raise ValueError("Input must be a positive even number
greater than 2.")
return [(p, n - p) for p in range(2, n // 2 + 1) if is_prime(p)
and is_prime(n - p)]
 Generating Squares of Even Numbers

Python Code:
squares = [x * x for x in range(10) if x % 2 == 0]

OCaml Equivalent:

let squares = List.filter (fun x -> x mod 2 = 0) (List.init 10 (fun

x -> x))
|> List.map (fun x -> x * x);;

○ List.init 10 (fun x -> x): Generates numbers 0-9.

○ List.filter (fun x -> x mod 2 = 0): Keeps only even numbers.
○ List.map (fun x -> x * x): Computes squares.
 Cartesian Product

Python Code:
cartesian_product = [(x, y) for x in [1, 2, 3] for y in
['a', 'b', 'c']]

OCaml Equivalent:
let cartesian_product = List.concat_map (fun x -> List.map (fun y ->
(x, y)) ['a'; 'b'; 'c']) [1; 2; 3];;

○ List.map (fun y -> (x, y)) ['a'; 'b'; 'c']: Pairs x with
each y.
○ List.concat_map applies this function to every x in [1; 2;
3].
 List Comprehension & Higher-Order
Functions in OCaml

● Functional Programming Approach:

○ Use higher-order functions instead of explicit
loops.
○ List.map, List.filter, and List.concat_map mimic
Python list comprehensions.
● Efficiency Considerations:
○ OCaml's approach avoids unnecessary intermediate
lists.
○ Readability improves with pipelining (|>).
Compress Consecutive Duplicates

● Objective: Remove consecutive duplicate elements from a

list.
Example:
compress ["a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e";
"e"];;

(* Output: ["a"; "b"; "c"; "a"; "d"; "e"] *)

● Approach:
○ Recursively traverse the list.
○ If the current element is equal to the previous,
skip it.
 OCaml Implementation
let rec compress lst =
match lst with
| [] -> [] (* Base case: Empty list remains empty *)
| [x] -> [x] (* Single element list remains unchanged *)
| x :: (y :: _ as t) ->
if x = y then compress t (* Skip duplicate *)
else x :: compress t;; (* Include non-duplicate
element *)

(* Example Usage *)
let result = compress ["a"; "a"; "b"; "c"; "c"; "a"; "a";
"d"; "e"; "e"; "e"];;
 Remove Elements Based on Predicate

● Objective: Remove elements that satisfy a given

predicate.
Example:
remove_if [1; 2; 3; 4; 5] (fun x -> x mod 2 = 1);;

(* Output: [2; 4] *)

● Approach:
○ Recursively check each element.
○ Retain only elements that do not satisfy the
predicate.
 OCaml Implementation
let rec remove_if lst pred =
match lst with
| [] -> [] (* Base case: Empty list remains empty *)
| x :: xs ->
if pred x then remove_if xs pred (* Skip elements
matching predicate *)
else x :: remove_if xs pred;; (* Include elements
that do not match predicate *)

(* Example Usage *)
let result = remove_if [1; 2; 3; 4; 5] (fun x -> x mod 2 =
1);;
 List Slicing

● Objective: Extract a sublist from index i (inclusive) to

j (exclusive).
Example:
slice ["a"; "b"; "c"; "d"; "e"; "f"; "g"; "h"] 2 6;;

(* Output: ["c"; "d"; "e"; "f"] *)

● Approach:
○ Recursively iterate and collect elements within the
range.
○ Handle cases where indices are out of bounds.
 OCaml Implementation
let rec slice lst i j =
match lst, i, j with
| [], _, _ -> [] (* Empty list case *)
| _, x, y when x >= y -> [] (* Invalid range case *)
| x :: xs, 0, _ -> x :: slice xs 0 (j - 1) (* Collect
elements within range *)
| _ :: xs, _, _ -> slice xs (i - 1) (j - 1) (* Skip
elements until range starts *)

(* Example Usage *)
let result = slice ["a"; "b"; "c"; "d"; "e"; "f"; "g"; "h"]
2 6;;
 List Suffixes

● Objective: Generate all suffixes of a list.

Example:
suffixes [1; 2; 5];;

(* Output: [[1; 2; 5]; [2; 5]; [5]; []] *)

● Approach:
○ Recursively generate suffixes by successively
removing the head of the list.
 OCaml Implementation
let rec suffixes lst =
match lst with
| [] -> [[]] (* Base case: The empty list has only
itself as a suffix *)
| _ :: xs as l -> l :: suffixes xs;; (* Generate suffix
by removing first element *)

(* Example Usage *)
let result = suffixes [1; 2; 5];;
 Identical on a List

● Objective: Check if two functions f and g produce the

same output for every element in a given list.
Example:
let f i = i * i;;
let g i = 3 * i;;
identical_on f g [3];;
(* Output: true *)
identical_on f g [1; 2; 3];;
(* Output: false *)

● Approach:
○ Recursively check if f x and g x produce the same
result for all elements in the list.
 OCaml Implementation
let rec identical_on f g lst =
match lst with
| [] -> true (* Base case: Empty list means all checks
passed *)
| x :: xs ->
if f x = g x then identical_on f g xs (* Check each
element *)
else false;; (* Return false if a mismatch is found
*)

(* Example Usage *)
let f i = i * i;;
let g i = 3 * i;;
let result1 = identical_on f g [3];;
let result2 = identical_on f g [1; 2; 3];;
Polynomial Function Representation

● Objective: Construct a polynomial function from a list

of (coefficient, exponent) tuples.
Example:
let f = polynomial [(3, 3); (-2, 1); (5, 0)];;
f 2;;
(* Output: 3*(2^3) - 2*(2^1) + 5 = 25 *)

● Approach:
○ Convert the list into a function that evaluates the
polynomial for a given x using recursion.
 OCaml Implementation

(* Helper function to compute exponentiation recursively *)

let rec pow x n =
match n with
| 0 -> 1 (* Base case: x^0 = 1 *)
| _ -> x * pow x (n - 1);; (* Recursive case: x^n = x * x^(n-1) *)

(* Function to evaluate a polynomial recursively *)

let rec polynomial lst x =
match lst with
| [] -> 0 (* Base case: Empty polynomial evaluates to 0 *)
| (co, ex) :: t -> co * (pow x ex) + polynomial t x;; (* Recursive evaluation
*)

(* Example Usage *)
let f = polynomial [(3, 3); (-2, 1); (5, 0)];;
let result = f 2;; (* Evaluates 3*(2^3) - 2*(2^1) + 5 *)

(* Print the result *)

let () = Printf.printf "Polynomial evaluated at x=2: %d\n" result;;
 THANKS!

CREDITS: This presentation template was created by

Slidesgo, incluiding icons by Flaticon, and
infographics & images by Freepik.