Activity: Higher Order Functions

Table of Contents

1 Activity structure

This is an activity not an assignment. That means it is not a graded assessment: you won't get formal feedback on it, but it is a great chance to practice with the ideas we've been talking about and it may also guide you through some new ideas. You'll work on it during class, usually with another students, or if you have to miss class, you'll complete it outside of class.

If you're working with someone, you should work in a paired programming style. At any point in time, one of you is "driving," i.e. actually using the keyboard and mouse. The other is actively engaged following along, preventing bugs, and providing ideas. You'll tradeoff who is driving about every 10 minutes, and it's important that regardless of whose computer you're using, you take turns typing and controlling it - the owner of the computer should not be the only one who drives. Before you start coding for a new part of the activity, I strongly encourage you to sketch out your strategy with your partner. You might discuss possible approaches together, and write down some ideas on paper that will then help you when you begin coding.

At the end of class, you should make sure you turn your code in (even if you're not done), as that gives you access to my solutions, and to email the code to your partner (so they can turn it in to access my solutions).

2 Setup

If both you and your partner have computers with you with the tools for our class setup on it, decide whose computer you'll be using.

Them you'll do the activity in VS Code: download the starter code (below), unzip it, move it into the ProgrammingLanguages folder for our docker container, and then open that folder as a docker in VSCode.

<<<<<<< HEAD Click here to access the starter code for this activity. ======= Click here to access the starter code for this activity. >>>>>>> dev

3 Tasks

Put all of your code for these tasks in main.scm. Put written answers in WrittenAnswers.txt.

3.1 map practice

  • Here's some Scheme code: 
(map (lambda (item) (+ 2 item)) '(1 4 7 10))

What will this expression evaluate to? Try to figure it out without using the interpreter. Write your answer in WrittenAnswers.txt. After you've come up with an answer, check your answers in Guile by running the input; you'll need to use the following line first to tell Guile to use a module: 

(use-modules (rnrs))

3.2 fold-left

Recall that Scheme has two versions of a reduce-like function: fold-left and fold-right. fold-left applies the reduction from left to right, while fold-right applies the reduction from right to left (although as usual, it is always initially accessing the Scheme list from left to right). Here are a couple of inputs and expected outputs for fold-left: 

(fold-left + 3 '(7 0 4)) ;; Returns 14
(fold-left - 3 '(7 0 4)) ;; Returns -8
(fold-left cons 3 '(7 0 4)) ;; Returns (((3 . 7) . 0) . 4)

Make sure you can explain why fold-left returns each of the outputs above for these examples.

3.2.1 input/output practice

Determine the correct outputs for the following inputs (make sure you come up with an answer before you run these!): 

(fold-left * 3 '()) 
(fold-left - 8 '(1 -3 5)) 
(fold-left cons 7 '((1 . 2) 3))

Write each input and the expected output in WrittenAnswers.txt. As above, you can check your answers in Guile by running the input. Make sure you've told Guile to use the module: 

(use-modules (rnrs))

3.2.2 Using fold-left

Imagine I want to sum up all the entries in a list that are less than 10. For example, if I had the list (10 5 9 20 25 2 35), I'd want to get 16, since 5+9+2=16.

In main.scm, write a Scheme function sum-small to accomplish your task. The function should take a single input, the list to sum up, and it should use fold-left. I'd call it like: 

(sum-small '(10 5 9 20 25 2 35))

Not sure where to start? Here's the skeleton of my code: 

(define sum-small
  (lambda (lst)
    (fold-left (lambda (cur-total next-item) [FUNCTION BODY - you'll fill this in!])
               FILL-IN
               lst)))

You'll fill in the function body and the second input to fold-left marked FILL-IN above.

3.2.3 Implementing fold-left

You'll now write your own version of fold-left, which we'll call fold-l. First, brainstorm what the base case(s) and recursive case(s) are, and then write your code in main.scm. Test your code on the examples above. If you wish, you can add your own tests to tests-activity.scm, and then you can run these tests with ./test-activity; look at mine for examples of the syntax, and feel free to ask for help if you get stuck!

3.3 fold-right

Now, you'll do the same thing for fold-right. To remind yourself what fold-right does and how it differs from fold-left, here are a couple of examples of inputs and outputs from fold-right: 

(fold-right cons 3 '(7 0 4)) ;; Returns (7 0 4 . 3)
(fold-right list '(1) '(21 22 23)) ;; Returns (21 (22 (23 (1))))

Before you start writing code, determine the correct outputs for the following inputs (make sure you come up with an answer before you run these!): 

(fold-right cons '(1 2)  '(10 11 12))
(fold-right list 4 '(3))

Write each input and the expected output in WrittenAnswers.txt. As above, you can check your answers in Guile if you use the rnrs module.

Now, write your own version fold-right, which we'll call fold-r. As above, brainstorm what the base case(s) and recursive case(s) should be, and then write your code in main.scm. Test your code using a variety of inputs and outputs.

3.4 Extra time?

If you have extra time, write two functions: reverse-fold-l and reverse-fold-r. Each of these functions takes a list as input, and returns the reverse of that list as output. reverse-fold-l should call the fold-l function, while reverse-fold-r should call the fold-r function.

Hint: My implementation of each of these includes a single call to fold-l or fold-r, and defines a function using lambda to pass in to fold-l or fold-r. One note that may be helpful: the base case of append is such that (append '() 'whatever) evaluates to whatever (i.e., appending to an empty list simply returns wht you're appending to - you might consider how to implement append for why this is the case).

4 Turning in activities

To turn in this activity, zip up the folder with your code, and upload that zip on Moodle. Additionally, email the zip to your partner so they can turn it in too. Even if you worked with a partner or you didn't finish, everyone should turn in the activity in order to gain access to my solutions.