How powerful is/ functional programming? Can you do the stuff you want to do? YES. Functional programming is perfectly capable of writing any algorithm you care to write. (That doesn't mean you want to, or that you will like it, but you can.) Turing completeness: A language can calculate anything a Turing Machine can calculate. We wink a little bit when we say this because real computers have finite memory. So we can that we can allocate (new, malloc) as much as we need. We imagine that integers can be as large as they need to be. Is a language Turing-complete? Rule of thumb is this: Can you iterate? Can you follow one statement with another? YES ==> a,b The comma operator does that for us. Can you do an if-block? if (test) stuff else other stuff end if YES ==> test?stuff:otherstuff This is what the ternary operator does for us? Can you do a generic loop? do stuff until (test) other stuff end do YES, in "functional C" but we have to use recursion to do this: Loop (vars) return (stuff,(test)?returnvalue:(otherstuff,Loop(vars)); What is the downside of emulating a loop with recursion? The big problem is adding to the stack. Anytime you call a method you push onto the stack. Eventually you'll get stack overflow. Tail recursion: If the last action of a method is a recursive call, any optimizing compiler "worth its salt" will replace the recursion with a branch. MyMethod (parameters) { ...stuff... MyMethod (new parameters); } MyMethod ends with a recursive call. So, the compiler rather than adding to to the stack, will instead update the parameter variables of MyMethod to match the parameters being passed into the recursive call, and then branch back to the beginning of the method. Look at fib: int fib (int i) { return ((i<=1)?i:fib(i-1)+fib(i-2)); } Look at QuickSort: Separate Array into two sections around a pivot. QuickSort (firsthalf). QuickSort (secondhalf). <== This one can be replaced with tail recursion. Look at MergeSort: Mergesort (first half). Mergesort (second half). Merge halves together. <= Not tail recursive. Loop (vars) return (stuff,(test)?returnvalue:(otherstuff,Loop(vars)); Notice that the very last thing done in this Loop method is the recursion, so this will converted to tail recursion, the stack won't get used, and it will work just like a real loop!!! Mastermind Grading: Correct Answer: 1122 My guess: 2211 First, we look for exact matches. There aren't any. The first 2 matches a 2 somewhere. The second 2 matches a different 2 somewhere. The first 1 matches a 1 somewhere. The second 1 matches a different 1 somewhere. Grade: 0 correct positions, 4 incorrect positions. Correct answer: 1132 My guess: 2211 Look for exact matches: there aren't any. The first 2 matches a 2 somewhere. The second 2 does not match anything, because that correct 2 has already been matched. Both 1's can be matched to different 1's. So the grade is 0 correct positions, 3 incorrect positions. Two phases to the Mastermind program. The computer grades the player, and the player grades the computer. How to grade??? Go through and look for exact matches. Simple loop: Does a[i]==b[i]? Then count the number of 0's in each, the 1's in each, the 2's in each, and so forth. Sum the minimum number of 0's, the minimum # of 1's, the minimum # of 2's and so forth. From this sum, subtract the number of exact matches, and this will be the number of incorrect positions. For example, Correct answer is 0042. First guess is 4949. Look for exact matches, there is one. Correct positions is 1. 0 1 2 3 4 5 6 7 8 9 C 2 0 1 0 1 0 0 0 0 0 G 0 0 0 0 2 0 0 0 0 2 M 0 0 0 0 1 0 0 0 0 0 Sum is 1. Sum - correct is incorrect 1-1 = 0. No incorrect positions. Correct positions is 1. Incorrect positions = 0. Correct is 0042. Guess is 2042. Look for exact matches: there are 3. 0 1 2 3 4 5 6 7 8 9 C 2 0 1 0 1 0 0 0 0 0 G 1 0 2 0 1 0 0 0 0 0 M 1 0 1 0 1 0 0 0 0 0 Sum is 3. 3-3 = 0, so 3 correct positions, 0 incorrect positions. How does the computer guess? Create an array of size 10000. Initialize it from 0000 to 9999. Choose a random element of the array. Fill the hole by moving the last element into position of the one you've just chosen. 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 9 6 7 8 If this guess grades correctly against all previous guesses, make this your next guess. Otherwise, choose a different random element until you get one that grades correctly. Mastermind run: C:\Users\apoe>mastermind COVID19 has chosen a pattern! Guess 1: Enter guess: 0042 No correct digits. Guess 2: Enter guess: 5678 2 correct digits in an incorrect position. Guess 3: Enter guess: 7819 2 correct digits in an incorrect position. Guess 4: Enter guess: 3783 1 correct digit in the correct position. Guess 5: Enter guess: 1761 1 correct digit in the correct position. 1 correct digit in an incorrect position. Guess 6: Enter guess: 9717 2 correct digits in the correct position. 1 correct digit in an incorrect position. Guess 7: Enter guess: 6715 2 correct digits in the correct position. Guess 8: Enter guess: 7716 1 correct digit in the correct position. 2 correct digits in an incorrect position. Guess 9: Enter guess: 6779 2 correct digits in the correct position. 2 correct digits in an incorrect position. Guess 10: Enter guess: 6797 4 correct digits in the correct position. You solved it in 10 guesses. Choose a pattern. Press ENTER when done: Guess 1: 4949 Number of correct digits in the correct position: 1 Number of correct digits in an incorrect position: 0 Guess 2: 7970 Number of correct digits in the correct position: 0 Number of correct digits in an incorrect position: 1 Guess 3: 4782 Number of correct digits in the correct position: 1 Number of correct digits in an incorrect position: 1 Guess 4: 6743 Number of correct digits in the correct position: 1 Number of correct digits in an incorrect position: 0 Guess 5: 2042 Number of correct digits in the correct position: 3 Number of correct digits in an incorrect position: 0 Guess 6: 1042 Number of correct digits in the correct position: 3 Number of correct digits in an incorrect position: 0 Guess 7: 0042 Number of correct digits in the correct position: 4 Number of correct digits in an incorrect position: 0 COVID19 got it in 7 guesses. COVID19 has defeated you!