Week 9 Set b
Due Date Thursday 11/1 at 9:00pm (Week 9)
Purpose Use functions as data and work through a puzzle using recursive reasoning.
Finger Exercises
Finger Exercises
Graded Exercises
Take Me To Church
Alonzo Church is one of the founders of computer science: he came up with the λ calculus, which we know and love so dearly. In fact, he famously argued that λ, much like love, is all you need! Let’s see whether or not he was right by investigating one of our favorite atomic data types, booleans.
Exercise 2 Define the two shortest functions that have this signature. The functions are restricted to only use λ expressions and variables. These will be our Bools.
Exercise 3 Design a bool->boolean function, which will allow us to test the functions we define below by converting to normal ISL #t / #f.
For the following three functions, besides define and λ, your function definitions should not use any ISL-provided functions or keywords (and certainly not bool->boolean, #t or #f).
Exercise 4 Design and/bool, which functions analogusly to and, but takes in two Bools and outputs a Bool.
Exercise 5 Design or/bool, which functions analogusly to or, but takes in two Bools and outputs a Bool.
Exercise 6 Design not/bool, which functions analogusly to not, but takes in one Bool and outputs a Bool.
For those of you who enjoyed this brain teaser but didn’t yet get the chance to finish the second half of lab 7, check it out!
A Leaf On The Wind
; A LeafyTree is one of: ; - 'leaf ; - (make-node LeafyTree LeafyTree) (define-struct node [l r])
Exercise 7 Design the function height, which computes the height of a leafy tree. A 'leaf has height 0.
Exercise 8 Design the function all-leafy-trees, which returns the list of all leafy trees of height n, where n is a given natural number.
As the list of trees produced grows very big very quickly, you should test the length of the output of your function on at least one input greater than 2 using the values found here. You probably don’t want to test on an input greater than 5, though!