Chapter 15: Part 4 equal-simple function

Scheme Function Example

Introduction

• This lecture focuses on an example function in Scheme called equal-simple. It builds upon the previous lectures for Chapter 15, particularly the concept of the member function.

Review of the member Function

• The member function takes two parameters: an item and a list.
• It checks if the item is an element of the provided list.
• If the item is found within the list, the function returns true; otherwise, it returns false.

Introduction to the equal-simple Function

• The equal-simple function takes two lists as input.
• It compares the two lists to determine if they are equal.
• If the lists are equal, the function returns true; otherwise, it returns false.

Scenarios for Comparing Two Lists

1. Both lists are null lists: In this case, the lists are considered equal and the function should return true.

   • Example: list1 is '()' and list2 is '()'.

2. List one is a null list, but list two is not: In this scenario, the lists are not equal, and the function should return false.

   • Example: list1 is '()' and list2 is '('a')'.

3. List one is not a null list, but list two is a null list: Similar to scenario 2, the lists are not equal, and the function should return false.

   • Example: list1 is '('a' 'b')' and list2 is '()'.

4. Both lists are not null lists: This is the most complex scenario. The function needs to check the elements of both lists to determine equality.

   • The function should compare the car (first element) of list1 with the car of list2.
     • If the car elements are not equal, then the lists are not equal, and the function should return false.
     • If the car elements are equal, the function needs to check the remaining elements (the cdr of the lists) recursively.

Code Implementation of equal-simple

• The function is implemented using a cond statement with multiple predicates.

Predicate 1

• Checks if list1 is a null list using the null? function.
• If list1 is null:
  • It then checks if list2 is also a null list.
    • If list2 is null, it returns true.
    • If list2 is not null, it returns false.
• This predicate handles scenarios 1 and 2.

Predicate 2

• This predicate is reached only if list1 is not a null list (Predicate 1 is false).
• It checks if list2 is a null list.
• If list2 is a null list, it returns false because list1 is not null, thus handling scenario 3.

Predicate 3

• This predicate is reached only if both list1 and list2 are not null lists.
• It checks if the car of list1 is equal to the car of list2.
• If they are equal:
  • It recursively calls the equal-simple function with the cdr of list1 and the cdr of list2.

Else Part

• The else part is reached if the car of list1 is not equal to the car of list2.
• In this case, the function immediately returns false because the lists are not equal.

Tracing Example 1: (equal-simple '(a b c) '(a c b))

1. Initial call: (equal-simple '(a b c) '(a c b))
   • list1 and list2 are not null.
   • Predicate 3 is evaluated: (car '(a b c)) = (car '(a c b)) => 'a' = 'a' => true
   • Recursive call: (equal-simple '(b c) '(c b))
2. Recursive call: (equal-simple '(b c) '(c b))
   • list1 and list2 are not null.
   • Predicate 3 is evaluated: (car '(b c)) = (car '(c b)) => 'b' = 'c' => false
   • The else part is executed, returning false.
3. The result false is returned to the initial call, so the final result is false.

Tracing Example 2: (equal-simple '(a b) '(a b))

1. Initial call: (equal-simple '(a b) '(a b))
   • list1 and list2 are not null.
   • Predicate 3 is evaluated: (car '(a b)) = (car '(a b)) => 'a' = 'a' => true
   • Recursive call: (equal-simple '(b) '(b))
2. Recursive call: (equal-simple '(b) '(b))
   • list1 and list2 are not null.
   • Predicate 3 is evaluated: (car '(b)) = (car '(b)) => 'b' = 'b' => true
   • Recursive call: (equal-simple '() '())
3. Recursive call: (equal-simple '() '())
   • list1 is null, so Predicate 1 is true.
   • list2 is also null, so the expression associated with Predicate 1 returns true.
4. The result true is returned up the call stack, leading to a final result of true.

Execution in DrRacket: equal-simple and member function

• The video demonstrates running the equal-simple and member functions within the DrRacket environment.
• The code for the functions from the slides should be written in DrRacket.
• Call the functions with different list to check if they are working correctly.

Other Scheme Function Examples:

• car: Returns the first element of a list.
  • Example: (car '(a b c)) returns 'a'.
• cdr: Returns the rest of the list, excluding the first element.
  • Example: (cdr '(a b c)) returns '(b c)'.
• cons: Adds an element to the beginning of a list.
  • Example: (cons 'a '(b c)) returns '(a b c)'.

Null List Examples

• The video shows several examples of checking if different expressions return true or false when being ran with null.

Using Symbols

• Here an example of assigning a value to a symbol, such as pi:
  • Example: (define pi 3.14)
  • Then if you call pi, it will return 3.14

Upcoming Quiz Information

• There will be a quiz on Friday covering the material discussed in this lecture and the lecture from Monday.