## CS5314: Concepts of Programing Languages Spring 2016 Assignment II: Higher Order Functions in Scheme Due Date: April 13, 2016

Functional programming is at its core a computational paradigm that consists solely of function definitions and function applications. Functions are "first class" meaning they can be values of variables, passed as parameters, and returned as the result of a function application. Higher order functions add power to the kinds of computations that can be accomplished in the purely functional progamming paradigm. Our project will give you experience with this paradigm, by having you design, code, and test a set of functions, including some higher order functions. Note: to get full credit for the assignment, some of your functions will have to be higher order (see section on grading).

Problem description - the data to be used. Suppose you are managing a sports team for your school, for example an intramural coed basketball team. We will use 2 different lists as input data for your set of functions. The first input list in this project concerns statistics for a set of teams, the Team_record_list that records the wins and losses for each team for a season. The following BNF defines the syntax of this list:

```Team_record_list --> ( T_record_seq )
T_record_seq --> (Team_record) | (Team_record) T_record_seq
Team_record -->  id int1 int2
```

where id is the team name, int1 is number of the wins and int2 is number of the losses this season for this team. For example, this is a Team_record_list:
((cardinals 5 10) (bluejays 15 3)).

The second input list for the project describes the scoring record for each player on a team in a nested Scheme list. For example, (cardinals (james (10 15 3)) means that the player james on the cardinals team played 3 games in which he scored 10, 15, 3 points repectively. The Team_scoring_list will be a list of such sublists, for example:

```( (cardinals (mary (2 14)) (james (10 15 3))) (crows (joe (2)) (sue (5 10 15 20)) (frank (5 15))) )
```

The BNF describing the structure of the Team_scoring_list in which { (, ), int, id } are all terminal symbols, is shown below:

```Team_scoring_list --> ( T_score_seq )
T_score_seq --> (id PL_score_seq) | (id PL_score_seq) T_score-seq
PL_score_seq --> ( id (Scores) )
Scores --> int | int Scores
```

where in T_score_seq, id is a terminal that is the team's name, and in PL_score_seq, id is a terminal that is the player's name with the list Scores that are the player's scoring record for the season.

Functions to be written.

• teamRatio(): Calculates each team's win_loss_ratio, that is the proportion of all games that the team won (i.e., #wins/(#wins+#losses)) for each team and returns it as a list of pairs: team_name, team_win_loss_ratio.

• sortedTeamRatio(): Returns the team_ratio pairs in a list sorted in order by team_ratio value, highest to lowest from the front of the list. If more than 1 team has the same team_ratio, then this set of teams will appear next to each other in the returned list, in arbitrary order.

• topThree(): Calculates the top three teams in terms of their win_loss_ratios. The return value of this function will be a list of pairs of the top three team names and their ratios in order from highest ratio to lowest. If there are ties for attaining any of the top three values, then the returned list will contain all teams whose ratio is one of these top three values. For example, if the top 3 ratios are .95, .90, .80 then the returned list might be:
( (wrens .95) (robins .90) (herons .80))
If there are multiple teams that attain the same ratio then the returned list might be:
( (wrens .95) (gulls .95) (robins .90) (herons .80)) where the wrens and gulls entries are adjacent and the order in which they appear would be with either one listed first.

• totalPoints(id): Returns the total number of points scored over the season by players on team id.

• averageScorePerPlayer(): Calculates the average score per player by combining the scores of all players on all teams in the league. That is, considering all players on all teams as the population over which the average score per player is computed, so that the denominator will be the total number of scores.

• averageScoreTeam(id): Calculates the average of the average scores per player for team id.

• maxScore(): Returns a list of pairs of each player name and his/her best (max) score for the season, including all players from all the teams.

• topThreeScorers(): Calculates those players who obtained the top single-game score across the entire league of teams. That is, this function returns an ordered list of pairs, the first element being the player obtaining one of the top 3 scores and the second element being the score. These pairs appear in the returned list in the order of highest single-game score to third-highest, with the order of the players with the same score being arbitrary.

For example, if the top three scores over all players was 50, 48, 45 respectively, then this list should contain those players who achieved these scores and their scores, for example: ( (james 50) (sally 48) (tom 45)). But what if more than one player attains a top-3 score? This is possible. Therefore, this function has to compute the top 3 scores in the league, and then needs to identify and return every player who had one of those scores (i.e., in a sublist of the player's name and his/her score). This means that this function may return more than 3 players, however each of them will have scored one of the top 3 scores. For example, when the top 3 scores are 50, 48, 45, then the following return value is possible, depending on the league's scoring records: ( (james 50) (ruth 50) (sally 48) (tom 45) (jill 45) )

• Define your own higher order function on this data, write it, show its use in at least 2 calls, and write a short description of its functionality.

Getting organized: Since there are several Scheme functions to define, first figure out which input data structure is the actual input for each of the functions. It might be easier to complete the functions that use the same input list first, before starting to deal with the next input list structure, but that is up to you. Remember you can define any helper functions you need, as named functions or as lambda expressions, but you have to include all such commented definitions in your final Scheme project submission so your functions can be run.

To use test-driven development with Scheme, the DrRacket environment has been designed with a check-expect function that allows you to give the system a function application on a specific input, and the return value expected, so that DrRacket can check to see if the expected answer is returned. Here is how you would write this:

```; function-name: input1-type input2-type -> output-type
; A brief description of the purpose of the function, including weirdness
(define (function-name input1 input2)
...)
(check-expect (function-name example-input1_1 example-input2_1) expected-result1)
(check-expect (function-name example-input1_2 example-input2_2) expected-result2)
(check-expect (function-name example-input1_3 example-input2_3) expected-result3)
(check-expect (function-name example-input1_4 example-input2_4) expected-result4)
```

This useful website contains information about our version of DrRacket and lists many built-in functions and operations.

Also, please recall that typing Control-i in DrRacket will re-indent your code for you (i.e., sort of a pretty-print that shows syntactic nesting) which helps to find syntax errors.

Grading: The project is due on Weds, April 13th. As usual there will be a 24 hour late turn-in period, but recall that late projects have a 20% reduction in the max grade they can achieve. Your functions will be graded on how they satisfy the specifications above, and should include comments in the code to aid reader understanding. The main point of this project is to learn how to use the power of higher order functions in Scheme. Here is a webpage to consult as to the built-in higher order functions available for your use in our version of DrRacket.

The 150 points for this project will be apportioned in this manner (including some partial credit in some categories):

• 50% correctness (i.e., works on final test data)
• 40% use of higher order functions (10% for coding at least 2 of the assigned functions as higher order functions; 30% for coding only higher order functions for the assignment (i.e., no simple recursion, no while/for loops)
• 10% good comments (i.e., function signature with types for each expected parameter, 1-2 sentence explanation of purpose of the function) followed by the code, followed by tests of the function (i.e., function appications with expected answers).

Remember that you are NOT supposed to write these functions to do complete error checking on the inputs to be used; just assume that the input they receive will be of appropriate type (e.g., atom, number or list).

One fine point: the topThree and topthreeScorers functions actually require in their specification that there be at least 3 teams and 3 players (respectively). Suggestion: write these functions assuming the data list(s) will be long enough; once they work with that assumption you can consider implementing error checking (in case there is not enough data to satisfy the functionality defined). Note: it will be worth more to complete all the function definitions, than do accomplish these 2 error checks and perhaps not complete all the functions, so use your time wisely.

Test data about the players and teams with answers expected from a correct implementation will be made available on this webpage here.

If you define 'helper' functions, they will have to include comments as to their functionality, and you will have to design test data for them. For example, if the incrbyone function was a helper function, then you would have to turn in the following code that includes a few sample commented function applications to show how the function can be applied. This will allow us to easily execute your function definition in DrRacket for grading and should allow for some partial credit in case not all of the functions work correctly.

```(define (incrbyone x) (+ 1 x)) ;increments its parameter by 1
(incrbyone 5) ; answer is 6
(incrbyone (* 4 2)) ; answer is 9
```

Final submission. We expect you will turn in a single file containing your complete set of commented function definitions used in your solution through WEB-Cat. This file should also contain sample function applications for all of your helper functions; these function applications should be located in the file immediately after the helper function definition. Hint: write your helper functions as you need them and test them with appropriate function applications. Later, you can comment out these function applications using ";" while testing your other code.

Last updated 9:58pm on March 30, 2016 BGR

12:50pm 3/30 Major changes/additions: rule for Team_record; function description for: sortedTeamRatio, topThree, averageScorePerPlayer, maxScore, topThreeScorers; using DrRacket automatic re-indent; test data section.