CSC 533: Programming Languages
Spring 2023

HW6: Scheme Structures

For this assignment, you will modify and add to functions that are provided for you in hw6.scm. Download this file, rename it LASTNAME-hw6.scm and enter your name in the comment at the top. Be careful to name your functions exactly as defined in the exercises, and be sure to comment each function as to its behavior.

PART 1: Baseball Stats Revisited

In HW5, you defined a number of functions that calculated baseball statistics. These functions were somewhat awkward, often requring a large number of inputs in order to do the calculation. For this assignment, you will redefine these functions to utilize a data structure of players statistics. For example, the following association list contains players statistics for one team: (define CUBS '((NAME AB R H 2B 3B HR RBI BB HBP SF) ((Willson Contreras) 416 65 101 23 2 22 55 45 24 2) ((Frank Schwindel) 271 23 62 11 0 8 36 19 0 2) ((Nick Madrigal) 209 52 19 52 7 0 0 14 3 0) ((Nico Hoerner) 481 60 135 22 5 10 55 28 6 2) ((Patrick Wisdom) 469 67 97 28 0 25 66 53 9 2) ((Ian Happ) 573 72 155 42 2 17 72 58 6 4) ((Christopher Morel) 379 55 89 19 4 16 47 38 3 2) ((Seiya Suzuki) 397 54 104 22 2 14 46 42 4 3) ((Rafael Ortega) 316 35 76 14 1 7 35 44 2 7) ))

Note that the first entry in the association list serves as a heading for the table. For this particular roster, the entry for each player contains (in order) their name (NAME), at-bats (AB), runs (R), hits (H), doubles (2B), triples (3B), home-runs (HR), runs-batted-in (RBI), walks (BB), hit-by-pitch (HBP) and sac-flies (SF). Note: different rosters might list the stats in a different order (as specified by the roster heading).

Add the following functions to your LASTNAME-hw6.scm file. Note: you should comment each function with a description of its behavior.

  1. Define a function named find-index that takes two inputs, a stat abbreviation and a roster list, and returns the index of that stat entry in the roster. For example, (find-index 'R CUBS) should evaluate to 2 and (find-index 'SF CUBS) should evaluate to 10.
  2. Define a function named lookup that takes three inputs, a player name, a stat abbreviation and a roster list, and returns the stat entry from the roster for that player. For example, (lookup '(Nico Hoerner) 'R CUBS) should evaluate to 60 and (lookup '(Ian Happ) 'SF CUBS) should evaluate to 4.
  3. Reimplement each of the baseball stat functions from HW5: batting-avg, on-base%, total-bases, slugging% and OPS. These new versions should each have only two inputs, the player name and a roster list, and should utilize the lookup function to access the needed stats from the roster. For example, (total-bases '(Seiya Suzuki) CUBS) should evaluate to 172.

PART 2: Binary Trees

In class, we discussed how structured lists could be used to represent binary trees. For example, the following binary tree is represented by the list to the right:

  (define ANIMALS '(dog (bird (horse () ()) (cat () ())) (possum (dog () ()) ())))

Several utility functions (empty-tree?, root, left-subtree, and right-subtree) are provided for you in hw6.scm. Add the following functions for manipulating arbitrary binary trees.

  1. Define a function named rightmost that takes one input, a list representing a binary tree, and returns the rightmost value in the tree. For example, (rightmost ANIMALS) should evaluate to possum.
  2. Define a function named leftmost that takes one input, a list representing a binary tree, and returns the leftmost value in the tree. For example, (leftmost ANIMALS) should evaluate to horse.
  3. Define a function named height that takes one input, a list representing a binary tree, and returns the height of that tree. Recall that the height of a tree is the number of nodes on the longest path from the root to a leaf. For example, (height ANIMALS) should evaluate to 3.

Recall the following definitions from Data Structures:

For example, the tree below is a binary search tree, but is not balanced. Thus, it is not an AVL tree.

  (define NUMS '(8 (6 (5 () ()) (7 () ())) (12 () (15 (14 () ()) ()))))

Add the following functions for manipulating binary trees containing numbers:

  1. Define a function named is-bst? that takes one input, a list of numbers representing a binary tree, and returns #t if that list is a binary search tree (otherwise #f). For example, (is-bst? NUMS) should evaluate to #t.
  2. Define a function named is-balanced? that takes one input, a list of numbers representing a binary tree, and returns #t if that list is relatively-balanced (otherwise #f). For example, (is-balanced? NUMS) should evaluate to #f.
  3. Define a function named is-avl? that takes one input, a list of numbers representing a binary tree, and returns #t if that list is an AVL tree (otherwise #f). For example, (is-avl? NUMS) should evaluate to #f.

PART 3: OOP in Scheme

In class, we discussed how first-class functions and closures could support the equivalent of classes, with private data and methods. The following function models a die object, where the number of sides is specified when creating the die.

(define (Die num-sides) (define roll-count 0) (define (apply op) (cond ((equal? op 'roll) (begin (set! roll-count (+ 1 roll-count)) (+ 1 (random num-sides)))) ((equal? op 'num-sides) num-sides) ((equal? op 'num-rolls) roll-count) (else 'UNDEFINED))) apply)

For example:

> (define d8 (Die 8)) > (d8 'roll) 3 > (d8 'num-sides) 8 > (d8 'roll) 4 > (d8 'roll) 7 > (d8 'num-rolls) 3
  1. Redefine your count-roll function from HW5 to utilize the above "class." Recall that this function takes two inputs, the desired dice total and the number of rolls. For example, (count-roll 7 1000) should simulate 1,000 rolls of two 6-sided dice and return the number of 7's obtained. As before, this function must utilize tail-recursion.

If we wanted to compare the likelihood of obtaining different dice totals, we could simply call the count-roll function repeatedly, e.g., (count-rolls 2 10000), (count-rolls 3 10000), ..., (count-rolls 12 10000). However, it must be noted that each call to count-roll is an independent experiment, and so the sum of the 11 counts would not necessarily add up to 10,000. To be more precise, we really need to conduct one sequence of rolls and keep count of all the totals at the same time.

  1. Define a function named zero-list that takes one input, an integer, and returns a list containing that many zeros. For example, (zero-list 6) should evaluate to (0 0 0 0 0 0).
  2. Define a function named incr-index that takes two inputs, an index and a list of numbers, and returns a copy of that list with the number at the specified index incremented. For example, (incr-index 0 '(0 0 0)) should evaluate to (1 0 0) and (incr-index 2 '(1 0 2 1 4)) should evaluate to (1 0 3 1 4).
  3. Define a function named count-all that takes one input, a number of rolls. The function should simulate that many dice rolls and return a list of counts for each total. For example, (count-all 10000) might return (303 576 869 1112 1386 1674 1297 1065 841 574 303), specifying that there were 303 twos, 576 threes, 869 fours, and so on. As was the case with count-roll, your function must utilize tail-recursion.