Chapter 3: Functional Programming, Part Deux

Whoever said that pleasure wasn’t functional?

—Charles Eames

3.1 Cryptography and Prime Numbers

../_images/Alien4.PNG

I’m headed home soon, but there’s just a bit more shopping to be done first!

Imagine that our alien is sitting at a cafe, surfing the Internet, sipping a triple mochaccino, and is now about to purchase the Harry Potter Complete DVD Collection (movies 1 through 17) from the massive online store, Nile.com. As it types in its credit card number to make its purchase, it suddenly pauses to wonder how its financial details will be kept secure as they are transmitted over the cafe’s Wi-Fi and then over the vast reaches of the Internet. That’s a valid concern. The good news is that many online stores use cryptography to keep such transactions secure.

../_images/Alien4.PNG

Rivest, Shamir, and Adleman received the Turing Award—the computer science equivalent of the Noble Prize.

One of the most famous and widely-used cryptography schemes is called RSA, after the three computer scientists who invented it: Ron Rivest, Adi Shamir, and Leonard Adleman. Here’s how it works: The online store has its own mathematical function that all customers use to encrypt their data before transmitting it over the network. This mathematical function is made publicly available. The hope is that while anyone can easily use this function to encrypt data, only the online store can “undo” (or, more technically, “invert”) the function to decrypt the data and recover the original number.

For example, imagine that Nile.com tells customers to use the function \(f(x)=2x\). It’s certainly easy to encrypt any number we wish to send—we simply double it. Unfortunately, any first grader with a calculator can decrypt the message by simply dividing it by 2, so that encryption function is not secure.

The RSA scheme uses a slightly more complicated function. If \(x\) is our credit-card number, we encrypt it using the function \(f(x) = x^e \text{ mod } n\), where \(e\) and \(n\) are carefully chosen numbers. (Remember from the previous chapter that \(x^e \text{ mod } n\) means the remainder when \(x^e\) is divided by \(n\); it can be easily computed in Python using the expression (x**e) % n.)

It turns out that if \(e\) and \(n\) are chosen appropriately, the online store will be able to decrypt the number to retrieve the credit card number \(x\) but it will be nearly impossible for anyone else to do so—even though everyone knows \(e\) and \(n\).

That’s pretty interesting, but how do we choose \(e\) and \(n\) and how will the store later decrypt the number that it receives? Well, we first choose two different large prime numbers \(p\) and \(q\) at random. Next, \(n\) is just \(pq\). Now, to get the number \(e\), we have to perform two steps: first we let \(m = (p−1)(q−1)\), and then we choose our exponent \(e\) to be a random prime number less than \(m\) that is also not a divisor of \(m\). That’s it!

Now, any number \(x\) less than \(n\) can be encrypted by computing \(x^e \text{ mod } n\). Once we have selected \(e\) and \(n\), we can share those values with anyone wishing to send us encrypted information. In a typical Internet shopping transaction, your web browser would get the publicly available values of \(e\) and \(n\) from the online store and use them to encrypt your credit card number, \(x\). Together, the values \(e\) and \(n\) are called the public key for this store. (In cryptology, a public key is simply a key that can be safely published without giving away the corresponding secret key.)

For example, let \(p=3\) and \(q=5\). They’re certainly prime (although they are way too small to be secure in practice). Now, \(n=3 \times 5=15\) and \(m = (3−1) \times (5−1) = 8\). For our encryption exponent \(e\), we could choose the prime number 3 because it’s less than 8 and also doesn’t divide 8. Now, we can encrypt any number less than n. Let’s encrypt the number 13, for example. We can compute \(13^3 \text{ mod } 15\) in Python as (13**3) % 15; the result is 7. So 7 is our encrypted number, which we send over the Internet to the online store.

../_images/Alien4.PNG

I think the mathematics of cryptography should be called “discreet” math.

How does the store decrypt that 7 and discover that the original number was actually 13? At the same time that the encryption exponent e was computed, we should have also computed a decryption exponent \(d\), which has two properties: it is between 1 and \(m − 1\), and \(ed \text{ mod } m = 1\). It’s not hard to show that, because of the way \(e\) and \(m\) were chosen, there is exactly one value that has these properties; we call d the multiplicative inverse of e modulo m. In our example, \(e = 3\) and \(m = 8\), and \(d\) is also 3 (it’s a coincidence that \(e\) and \(d\) are equal; that’s not normally the case—if it were, the decryption key wouldn’t exactly be a secret!). Notice that \(ed \text{ mod } 8 = 9 \text{ mod } 8 = 1\). Now, the online store can decrypt any number \(y\) that it receives by simply computing \(y^d \text{ mod } n\). In our case, we received the encrypted number \(y = 7\). We compute \(7^3 \text{ mod } 15\) using Python ((7**3) % 15) and get the answer 13. Indeed, that’s the value that we encrypted a moment ago! Keep in mind that while the encryption key \(e\) and \(n\) are public, the online store must keep the decryption key \(d\) private. Anyone with access to \(d\) can decrypt any message sent with the encryption key.

Exactly why this works is not too hard to show and is often taught in an introductory discrete math or algorithms course. But you may be wondering why we are so confident that the scheme is secure. This, too, requires a bit more time to explain than we have here. We will point out, however, that since the the values \(e\) and \(n\) are public, if a malicious person could find the two primes \(p\) and \(q\) that we originally selected, then they could figure out \(m\) and then \(d\) and they could crack the code. The good news is that “factoring” a number \(n\) into its prime divisors is known to be a “computationally hard” problem—very hard. (Computationally hard means a problem that takes a long time to compute the answer for.) For example, the U.S. National Institutes of Standards and Technology estimates that if we encrypt a message today using public keys that are about 600 digits long, it would take until about the year 2030 to crack the code—even if a very large number of very fast computers were used for the attack.

3.2 First-Class Functions

../_images/Alien4.PNG

I prefer to do everything first-class.

Recall that in the previous chapter we learned about Python functions and explored the power of recursion. The style of programming that we examined—programs constructed from functions that call one another (and possibly themselves)—is called functional programming. Interestingly, in functional programming languages like Python, functions are actually data just like numbers, lists, and strings. We say that functions are “first-class citizens” of the language. In particular, we can write functions that take other functions as arguments and return other functions as results! In this chapter we’ll explore these ideas, first using them to write a short program that efficiently generates long lists of primes, and ultimately writing a function that generates both the encryption and decryption functions for RSA cryptography. By the end of this chapter, we’ll have written Python programs that will allow you to securely send data to your friends.

3.3 Generating Primes

Motivated by RSA cryptography, our first mission is to find a way to generate a list of primes. One reasonable way to do this is to first write a function that determines whether or not its argument is prime. Once we have such a function, we could use it to test a sequence of consecutive numbers for primality, keeping those that are prime in a list.

But how do we test if a single positive integer \(n\) is prime? One idea is to simply test whether any number between 2 and \(n − 1\) divides it. If so, the number is not prime. Otherwise the number is prime. (In fact, it suffices to test just the numbers between 2 and \(\sqrt{n}\), since if \(n\) is not prime, at least one of its divisors must be less than or equal to \(\sqrt{n}\). But for now, let’s simply test all the possible divisors between 2 and \(n−1\).)

To that end, it would be useful to have a function divisors(n) that accepts our number n (which we wish to test for primality) and returns True if n has any divisors (other than 1 and itself), and False otherwise. Actually, it will turn out to be handy if divisors accepts two additional numbers, low and high, that give a range of divisors to test. That will let us reduce the amount of work that has to be done.

For example, divisors(15, 2, 14) should return True because 15 has a divisor between 2 and 14 (and therefore is not prime), but divisors(11, 2, 10) should return False because 11 has no divisors between 2 and 10 (and therefore is prime). Also, note that divisors(35, 2, 4) should return False even though 35 is not prime.

We can write the divisors(n, low, high) function using recursion! To simplify matters, we’ll assume that the arguments are all positive integers. If low is higher than high, then the answer is False because n cannot have any divisors in the specified range (since there are no numbers in increasing order between low and high). So, if low > high we must return False—which is a base case.

But what if low is less than or equal to high? In this case, we can test whether n has a divisor between low and high like this: If n is divisible by low, then we’ve found a divisor in that range and we must return True. Otherwise, the answer to the question: “Does n have a divisor between low and high?” now becomes the same as the answer to the question “Does n have a divisor between low+1 and high?” But that’s a version of the original question, and thus one that we can solve recursively! Here’s our solution:

def divisors (n, low, high):
    '''Returns True if n has a divisor in the range from low to high.
    Otherwise returns False.'''
    if low > high:
        return False
    elif n % low == 0: # Is n divisible by low?
        return True
    else:
        return divisors (n , low + 1, high)

Now we can test if n is prime by checking whether it has any divisors between 2 and n-1:

def isPrime (n):
    '''For any n greater than or equal to 2,
    Returns True if n is prime. False if not.'''
    if divisors (n, 2, n-1):
        return False
    else :
        return True

We can do this even more elegantly this way:

def isPrime (n):
    '''For any n greater than or equal to 2,
    Returns True if n is prime. False if not.'''
    return not divisors (n, 2, n-1)

Recall from Chapter 2, that not “negates” a Boolean, so if divisors(n, 2, n-1) is True then not divisors(n, 2, n-1) is False, and if divisors(n, 2, n-1) is False then not divisors(n, 2, n-1) is True.

Now we can use isPrime to generate lists of primes, again using recursion. Imagine that we want to know all of the primes from 2 to some limit, for example 100. For each number in that range, we could test if it’s prime and, if so, add it to our growing list of primes. Before you look at the code below, see if you can determine the base case and the recursive step for such a function.

Now, here is the Python implementation:

def listPrimes (n, limit):
    '''Returns a list of prime numbers between n and limit.'''
    if n == limit:
        return []
    elif isPrime (n):
        return [n] + listPrimes (n+1, limit)
    else:
        return listPrimes (n+1, limit)

Notice that in the second return statement, we returned [n] + listPrimes(n+1, limit) rather than n + listPrimes(n+1, limit). Why? Well, in this case the plus sign means that two lists should be concatenated, so the expressions on its left and right have to be lists. Indeed, the result of calling listPrimes will be a list, since by definition a list is what this function returns (and notice that in the base case it returns the empty list). However, n is a number, not a list! To make it a list, we place it inside square brackets. That way, we are concatenating two lists and life is good.

The above strategy for generating primes works, but it’s quite slow—particularly when attempting to generate large primes. The problem is that it repeats a lot of work. For example, if you call listPrimes(51, 2, 50) it will test 2 as a divisor and fail—but it will still insist on testing 4,6,8,...,50 even though we’ve already proven that 51 isn’t even!

../_images/Alien4.PNG

It’s not entirely clear that Eratosthenes actually discovered this idea.

A much faster algorithm for generating primes is the so-called sieve of Eratosthenes. This method is named after Eratosthenes, an ancient Greek mathematician who lived around 2200 years ago. Here’s the idea: To find all of the primes from 2 to 1000, for example, we first write down all of the integers in that range. Then we start with 2; it’s the first prime. Now, we remove (or “sift”) all multiples of 2 from this list since they are definitely not prime. When we’re done, we come back to the beginning of our remaining list. The number 3 survived the sifting of numbers that was performed by 2, so 3 is prime. We now cancel out all remaining numbers that are multiples of 3, since they too cannot be prime. When we’re done, we look at the first number in the remaining list. It’s not 4 (it got sifted out earlier when we looked at 2), but 5 is there. So 5 is prime and we let it sift all of its multiples that remain in the list. We continue this process until every remaining number has had a chance to sift the numbers above it.

../_images/Sieve_of_Eratosthenes_animation.gif

Figure 3.1: Sieve of Eratosthenes

(http://commons.wikimedia.org/wiki/File:Sieve_of_Eratosthenes_animation.gif)

We’ll implement a recursive algorithm motivated by Eratosthenes’ algorithm as a Python function called... primeSieve. (In the spirit of full disclosure, our implementation will take a few liberties with Eratosthenes’ algorithm.) It will take a list of numbers 2,3,... up to the largest number that we’re interested in, and will return a list of all the primes in the original list. Fortunately, Python has a built-in function that allows us to obtain the list of all integers from a starting point to an ending point. It’s called range, and in Python 2 it works like this:

>>> range(0,5)
[0, 1, 2, 3, 4]
>>> range(3,7)
[3, 4, 5, 6]

In Python 3 range works almost the same, but it needs a little nudge to turn the result into a list:

>>> list(range(0,5))
[0, 1, 2, 3, 4]
>>> list(range(3,7))
[3, 4, 5, 6]

Notice that the list that we get back from range seems to stop one number too soon. That may seem weird, but as we’ll see later, it turns out to be useful. So getting all the integers from 2 to 1000, for example, is easy: range(2, 1001). We can then pass that list into the primeSieve function.

Before writing primeSieve let’s just do a small thought experiment to better understand how it will work. Imagine that we start it with the list range(2, 11), which is:

[2, 3, 4, 5, 6, 7, 8, 9, 10]

Passing this list to primeSieve is basically saying “Could you please find me all of the primes in this list?” To accommodate your polite request, the primeSieve function should grab the 2 and hold on to it because it’s a prime. It should then sift all of the multiples of 2 from this list, resulting in a new list:

[3, 5, 7, 9]

Now what? Well, primeSieve would like to do as little work as possible and instead send that list to some function and ask it, “Could you please find me all of the primes in this list?” Aha! We can send that list back to primeSieve because its job is to find the primes in a given list. That’s just recursion!

So, continuing with our example, the first time we called primeSieve it found the 2, sifted out the multiples of 2 to get the list [3, 5, 7, 9], and called primeSieve on that list. Whatever comes back from the recursive call will be tacked on to the 2 that we’re currently holding—and then we’ll have the whole list of primes from 2 to 10.

The recursive call to primeSieve with the argument list [3, 5, 7, 9] will similarly grab the 3 from the front of that list, sift out all of the multiples of 3 to get list [5, 7], and will ask for help finding the primes in that list. Whatever primes are returned will be tacked on to the 3 that we’re holding, and that will be all of the primes in the list [3, 5, 7, 9].

../_images/Alien4.PNG

I think that this approach should be called the “wishful thinking” method because we just wish for a helper function whenever we need one.

In the next recursive call, we’ll grab 5 and recur on the list [7]. That recursive call will grab the 7 and recur on the empty list. We see here that since the list is getting shorter each time, the base case arises when we have an empty list. In that case, primeSieve must report that “the list of all the primes in my argument is empty”—that is, it should return the empty list.

We still need a function that will do the actual sifting. We can imagine a function called sift that takes two arguments—a number toRemove and a list of numbers numList—and returns all of the numbers in numList that are not multiples of toRemove. Let’s come back to that in a moment, and write our primeSieve under the assumption that we have sift. This approach for writing programs is called top-down design because we start at the “top” (what we want) and then work our way down to the details that we need.

def primeSieve(numberList):
    '''Returns the list of all primes in numberList, using a prime sieve algorithm.'''
    if numberList == []:      # if the list is empty,
        return []             # ...we're done
    else:
        prime = numberList[0]  # The first element is prime!
        return [prime] + primeSieve(sift(prime, numberList[1:]))

Now, we need to sift. The next section will introduce a tool that will help us do exactly that, so read on...

3.4 Filtering

Fortunately for us, Python (like most functional programming languages) has a built-in function named filter that does (almost) exactly the sifting that we would like to do.

We’ll eventually get back to the problem of general list sifting that we started above, but for the moment let’s just focus on the problem of sifting a list by removing numbers divisible by two. To demonstrate filter in action, let’s first define a function called isNotDivisibleBy2 that takes a number n as an argument and returns a Boolean value: True if the number is not divisible by 2 (i.e., it is odd) and False otherwise (i.e. it is even).

def isNotDivisibleBy2(n):
    '''Returns True if n is not divisible by 2,
    else returns False.'''

    return n % 2 != 0

Now back to filtering. Having isNotDivisibleBy2, here’s how we can use it with Python’s filter function. In Python 2 it looks like this:

>>> filter(isNotDivisibleBy2, range(3, 10))
[3, 5, 7, 9]

In Python 3, filter doesn’t eagerly produce a list, so we need to send its result to the list function, as follows:

>>> list(filter(isNotDivisibleBy2, range(3, 10)))
[3, 5, 7, 9]
../_images/Alien4.PNG

I couldn’t function without a filter to remove the noxious oxygen from Earth’s air!

You may have inferred what filter is doing: its first argument is a function and its second argument is a list. The function is a special one that takes a single argument and returns a Boolean result. A function that returns a Boolean is called a predicate; you can think of the predicate as telling us whether or not it “likes” its argument. Then, filter gives us back all of the elements in the list that the predicate likes. In our example, isNotDivisibleBy2 is a predicate that likes odd numbers. So we got back the list of all the odd numbers in the original list.

A function that takes other functions as arguments?! Strange, but definitely allowed, and even encouraged! This idea is central to functional programming: functions can be passed into and returned from other functions just like any other kind of data. In fact, Chapter 4 will explain why this idea is not so strange after all.

../_images/Alien4.PNG

Four letr wrds rock!

Lists of numbers are not all we can filter. Here’s another example of filter, this time using lists of strings. In preparation for its next visit to Earth, our alien is attempting to master English and a number of other languages. The alien has a list of words to learn, but it’s particularly keen on learning the four-letter words first. For example, if it’s given the list of words ['aardvark', 'darn', 'heck', 'spam', 'zyzzyva'] it would like to have a way of filtering that list to just be the “bad” words ['darn', 'heck', 'spam'].

Again, we define a predicate function first: a function called isBad that takes a string named word as an argument and returns a Boolean value: True if the word is of length four and False otherwise.

def isBad(word):
    '''Returns True if the length of "word" is 4, else returns False.'''

    return len(word) == 4
../_images/Alien4.PNG

*In Python 2, we can omit the call to list, so we simply have filter(isBad, ...

Now that we have isBad, here’s how we can use it with Python’s filter function:

>>> list(filter(isBad, ['ugh', 'darn', 'heck', 'spam', 'zyzzyva']))
['darn', 'heck', 'spam']

3.5 Lambda

Filter helps us sift lists of numbers, but so far all we’ve seen how to do is to sift them to remove even numbers. If we wanted to remove multiples of 3 we would need another helper function:

def isNotDivisibleBy3(n):
    '''Returns True if n is not divisible by 3, else returns False.'''
    return n % 3 != 0

And then we’d need another to remove multiples of 5, and one for 7, and 11, and so on. Obviously this is not going to work.

The idea behind our primeSieve function is that we want to change what we are filtering for “on the fly,” depending on which number is currently first in the list. You might imagine that we could add a second argument to our predicate function, as follows:

def isNotDivisibleBy(n, d):
    '''Returns True if n is not divisible by d, else returns False.'''
    return n % d != 0

Generally, this would solve the problem, but in this case we have a problem: filter requires that the predicate function we pass it takes only one argument. So this new definition will not work either.

../_images/Alien4.PNG

Is a disposable function environmentally friendly?!

What we really need is a sort of “disposable” function that we can define just when we need it—using the number we currently care about sifting—and then immediately throw it away after we are done using it.

In fact, this function will be so temporary that we won’t even bother to give it a name! Such a function is called an anonymous function.

Here’s what an anonymous function definition looks like for our isNotDivisibleBy2 example:

>>> filter(lambda n: n % 2 != 0, range(0, 1001))
../_images/Alien4.PNG

“Lambda” derives from a branch of mathematics called the lambda calculus (see section 3.7), which influenced the first functional language, LISP.

The word “lambda” indicates that we are defining an anonymous function—a short-lived function that we need right here and nowhere else. Then comes the names of the arguments to the function (in this case, one argument named n), then a colon, and then the value that this function should return. So, this anonymous function lambda n: n % 2 != 0 is exactly equivalent to our isNotDivisibleBy2 function above.

The anonymous function syntax in Python is odd; in particular, we don’t put parentheses around the function’s arguments, and there is no return statement. Instead, anonymous functions in Python implicitly return whatever value comes after the colon.

Just to make the point that anonymous functions really are full-fledged functions, take a look at this:

(ch03_lambda)

Whoa—that’s really weird! In the first line, we’re defining a variable named double and giving it the value lambda x: 2 * x. But in a functional programming language functions are truly first-class citizens; they are data just like numbers, strings, and lists. So double is a function with one argument, and if we want to use it we need to pass it a value. In the second line, that’s exactly what we’re doing. In fact, when we define a function in the “normal” way, that is by starting with the line def double(n), we are really just saying double is a variable whose value is the function that I’m going to define in the lines following the def statement.”

../_images/Alien4.PNG

*If using Python 2, we can omit the call to list.

Finally, we can use anonymous functions to finish writing sift, as follows:

def sift(toRemove, numList):
    '''Takes a number, toRemove, and a list of numbers, numList.
    Returns the list of those numbers in numList that are not multiples of toRemove.'''

    return list(filter(lambda x: x % toRemove != 0, numList))

The anonymous function we pass into filter uses toRemove in its body without having to pass it in as an argument. It can do this because this function is defined in an environment where toRemove already exists and has a value.

Of course we could also write sift using the list-comprehension syntax (see the sidebar in section 3.6.2); then it would look like this:

def sift(toRemove, numList):
    return [x for x in numList if x % toRemove != 0]

Finally, as a reminder, here is our primeSieve function again, using sift:

def primeSieve(numberList):
    '''Returns the list of all primes in numberList using a prime sieve algorithm.'''
    if numberList == []:      # if the list is empty,
        return []              # ...we're done
    else:
        prime = numberList[0]  # The first element is prime!
        return [prime] + primeSieve(sift(prime, numberList[1:]))

It’s surprising how much entertainment value there is in running primeSieve to generate long lists of primes. However, Python got angry with us when we tried something like this:

../_images/Alien4.PNG

*If using Python 2, we don’t need to call list.

>>> primeSieve(list(range(2, 10000)))

We got a long and unfriendly error message. The reason is that this created a lot of recursion, and Python is trained to believe that if there is a lot of recursion going on, there must be an error in your program (usually because you forgot to put in a base case). Exactly how much recursion Python thinks is too much depends on the Python version and your computer’s operating system. However, you can ask Python to allow you more recursion by including the following two lines at the top of your file:

import sys
sys.setrecursionlimit(20000) # Allow 20000 levels of recursion

We asked for \(20,000\) levels of recursion here. Some operating systems may allow you more or less than this. (Most modern machines will allow much, much more.)

../_images/Alien4.PNG

Shameless sales pitch!

This brings us to one last point: while the prime sieve is quite efficient, most good implementations of the RSA scheme use even more efficient methods to generate large prime numbers. In practice, the primes used by RSA when encoding Internet transactions are generally a few hundred digits long! A CS course on algorithms or cryptography may well show you some of the more sophisticated and efficient algorithms for generating primes.

3.6 Putting Google on the Map!

In the rest of this chapter we will continue to build on the idea of functions as first-class citizens that can be passed into or returned from other functions. We’ll look at two more examples: Google’s MapReduce approach to processing data, and taking derivatives of functions.

Imagine that you work for Nile.com. Your company maintains a list of product prices, and periodically the prices are systematically increased. Your boss comes into your office one morning and asks you to write a function called increment that takes a list of numbers as an argument and returns a new list in which each number is replaced by a value one greater. So, with the argument [10, 20, 30], the result should be [11, 21, 31].

No problem! We can write increment recursively. For the base case, if the argument is an empty list, we’ll also return an empty list. (Remember, the result is always a list of the same length as the argument, so returning anything other than the empty list in this case would be violating our contract!). For the recursive case, we observe that we can easily increment the first number in the list: We simply find that element and add one to it. We can then slice that first element off the list and increment the remainder. The phrase “increment the remainder” is essentially saying “use recursion on the remaining list.” In other words, increment([10, 20, 30]) will first find the 10, add one to make it 11, and then recursively call increment([20, 30]) to get the result [21, 31]. Once we have that, we just concatenate the 11 to the front of that list, resulting in [11, 21, 31]. Here’s the Python program:

def incrementList(numberList):
    '''Takes a list of numbers as an argument and returns
       a new list with each number incremented by one.'''

    if numberList == []:
        return []
    else:
        newFirst = numberList[0] + 1  # increment 1st element
        # Next, increment the remaining list
        incrementedList = incrementList(numberList[1:])
        # Now return the new first element and the
        # incremented remaining list
        return [newFirst] + incrementedList

3.6.1 Map

../_images/Alien4.PNG

This boss is straight out of Dilbert!

Your boss is pleased, but now tells you “I need a very similar function that takes a list as an argument and adds 2 to each element in that list.” Obviously, we could modify increment very slightly to do this. Then your boss tells you, “I need yet another function that takes a list as an argument and triples each element.” We can do that too, but this is getting old.

We see that your boss frequently needs us to write functions that take a list of numbers as an argument and return a new list in which some function is applied to every element in that list.

../_images/Alien4.PNG

This is known more succinctly as the principle of generalization. We’re trying to make our function more general and less specific.

An important principle in computer science is “if you are building lots of very similar things, try instead to build one thing that can do it all.”

We’ve seen this principle before when we started writing functions, but here we’ll take it one step further. The “do it all” thing in this case is a function called map, which is built in to Python and many other functional programming languages. We’ll show it to you and then explain. But first, it will be handy to have two simple functions to help with our example. One function, called increment, takes a number as an argument and returns that number plus 1. The second, called triple, takes a number as an argument and returns three times that number:

def increment(x):
    '''Takes a number x as an argument and returns x + 1.'''
    return x+1
def triple(x):
    '''Takes a number x as an argument and returns 3 * x.'''
    return 3 * x

If you’re using Python 2, you can now do the following:

>>> map(increment, [10, 20, 30])
[11, 21, 31]
>>> map(triple, [1, 2, 3, 4])
[3, 6, 9, 12]

If you’re using Python 3, map is a bit lazy and requires some cajoling to produce the list, just like filter did. The magic incantation required in Python 3 looks like this:

>>> list(map(increment, [10, 20, 30]))
[11, 21, 31]
>>> list(map(triple, [1, 2, 3, 4]))
[3, 6, 9, 12]

This is passing the result of map to a built-in function called list, which forces Python 3 to actually produce the list.

Notice that map takes two arguments. The first is a function; the second is a list. The function that is given to map (e.g., increment and triple in our examples) must be a function that takes one argument and produces a single result. Then, map applies that function one-by-one to each element in the list to build a new list of elements.

Sometimes, we don’t need to create our own functions to give to map. For example, take a look at this example:

>>> map(len, ['I', 'like', 'spam'])
[1, 4, 4]

In Python 3, this would be

>>> list(map(len, ['I', 'like', 'spam']))
[1, 4, 4]

In this case, the built-in function len is applied to each of the strings in the given list. First, len is applied to the string 'I'. The length of the string is 1 and that’s the first thing to go in the result list. Then the len function is applied to the string 'like'; the result is 4, which is the next thing to go in the result. Finally, the length of 'spam' is 4, which is the last value placed in the result list.

Notice how our abstraction theme comes into play with map. The details of how the function we pass to map is applied to the list are hidden away. We no longer have to worry specifically about how to step through the list to modify each element: map does this for us.

Note

List Comprehensions

The map, reduce, and filter functions, and the lambda notation for anonymous functions, are not unique to Python; they are found in most functional programming languages. However, Python offers an alternative syntax to map and filter called list comprehensions, which allow us to avoid using lambda. Sometimes that’s both conceptually easier and faster to type!

Let’s start with the example from Section 3.6.1, where we wanted to increment every element in the list [10, 20, 30]. Whereas earlier we used map and an increment function to do this, the list comprehension syntax looks like this:

>>> [x + 1 for x in [10, 20, 30]]
[11, 21, 31]

Similarly, we can triple every element in the list [1, 2, 3, 4] using the syntax:

>>> [3 * x for x in [1, 2, 3, 4]]
[3, 6, 9, 12]

In general, the syntax is:

[f(x) for x in L]

...where f is some function and L is some list. Notice that this is really just like map in that we are mapping the function f to every element x in the list L. By the way, there’s nothing special about the name x for the variable; we could use a different variable name as in:

>>> [len(myString) for myString in ['I', 'like', 'spam']]
[1, 4, 4]

A very similar syntax can be used to do the job of filter. Rather than using filter to obtain the four-letter words in a list as we saw earlier, we can use list comprehensions this way:

>>> words = ['aardvark', 'darn', 'heck', 'spam', 'zyzzyva']
>>> [x for x in words if len(x) == 4]
['darn', 'heck', 'spam']

In this case, we defined the list words before using the list comprehension, just to make the point that we can do that. Of course, we could have also done this as:

>>> [x for x in ['aardvark', 'darn', 'heck', 'spam', 'zyzzyva']
... if len(x) == 4]

Similarly, we could get the multiples of 42 between 0 and 1 million (another example where we used filter) this way:

>>> [x for x in range(0, 1000000) if x % 42 == 0]

In general, the format for using list comprehensions to filter looks like this:

[x for x in L if ...]

...where L is a list and the ... represents some Boolean expression; that is, an expression that evaluates to either True or False. We get back the list of all values of x in the list L for which that Boolean expression (recall that it’s called a predicate) is True. That is, we get all of the values of x that the predicate “likes.” Finally, we can write list comprehensions that combine both map and filter into one. Here’s an example where we produce the square of every even number between 0 and 10:

>>> [x**2 for x in range(0, 11) if x % 2 == 0]
[0, 4, 16, 36, 64, 100]

This list comprehension is mapping the function \(f(x) = x^2\) to every value of x in the list of integers from 0 to 10 subject to filtering that list through a predicate that only likes even numbers. Thus, we get the squares of even numbers. In general, the syntax is:

[f(x) for x in L if ...]

where f is a function, L is a list, and what comes after the \(\dots\) is a predicate. We get back the list of \(f(x)\) values for those values of x for which the predicate is True.

By the way, this syntax works just the same in Python 2 and 3. Python 3 doesn’t require any special prodding to produce a list when list comprehensions are used.

3.6.2 Reduce

../_images/Alien4.PNG

Ten mochaccinos, a laptop, the Harry Potter DVD collection,...

Our alien has just learned about map and is quite excited. During its visit to Earth, the alien purchased a number of items and it plans to request reimbursement from its employer.

For example, here is a list of the costs, in U.S. dollars, of several items purchased by the alien: [14, 10, 12, 5]. The alien would like to convert these costs to its own currency and then add up the total. The exchange rate is 1 U.S. dollar equals 3 alien dollars. So, the values of the four items in alien dollars are [42, 30, 36, 15] and the total request for reimbursement in alien dollars will be \(42 + 30 + 36 + 15 =123\).

Converting a list from U.S. dollars to alien dollars is no problem—we did that above using map and our triple function. Now, though, we want to add up the elements in the resulting list. We could write a recursive function for that task. However, it turns out that there are many very similar tasks that the alien needs to perform as well.

Here’s one: Imagine that the alien converted between a variety of currencies while shopping on Earth. For example, the alien first got some dollars, then changed dollars into Euros, then changed Euros into rubles, and then rubles into yen. If the alien started with 1 U.S. dollar, how many yen is that? This is a matter of computing the products of exchange rates. If one dollar is 0.7 Euros, one Euro is 42 rubles, and one ruble is 3 yen, then one dollar is \(0.7 \times 42 \times 3 = 88.2\) yen. So now the alien needs to compute the product of a list of numbers.

Again, rather than writing a separate function to add up the numbers in a list and another to multiply the numbers in a list (and possibly others to do other things to elements in a list), Python provides a general-purpose function called reduce that reduces all of the elements in a list to a single element (e.g., their sum or product or something else).

Let’s first define a function called add that takes two arguments and returns their sum, and another called multiply that takes two arguments and returns their product.

def add(x, y):
    '''Returns the sum of the two arguments.'''
    return x + y

def multiply(x, y):
    '''Takes two numbers and returns their product.'''
    return x * y

Now, here’s reduce in action:

>>> from functools import *
>>> reduce(add, [1, 2, 3, 4])
10
>>> reduce(multiply, [1, 2, 3, 4])
24

In the first case reduce reduced our list to the sum of its elements, and in the second case to the product of its elements. Notice that the first argument to reduce is a function and the second is a list. A subtle point here is that the function that we give as an argument to reduce must take two arguments and return a single result. Then, reduce takes the first two elements from the list and applies the given function to reduce them to one element, takes that result and the next element from the list and applies the function to them, and repeats that process until all of the elements are reduced to a single value.

../_images/Alien4.PNG

While reduce is built in to Python 2, in Python 3 you’ll need to include the line from functools import * before using reduce. You can include that line at the Python prompt or at the top of any file that uses reduce.

3.6.3 Composition and MapReduce

../_images/Alien4.PNG

Remember that in Python 3 you’ll need to include the line from functools import * since we’re using reduce here.

Finally, imagine that we plan to frequently take a list, map some function (e.g., triple) to each element in that list to produce a new list (e.g., the list of 3 times each element), and then apply some other function to reduce that new list to a single value (e.g., using add to get the sum of these values). This is a combination of map and reduce, or more accurately the composition of map and reduce. Let’s write such a function and call it mapReduce. It will take two functions and a list as arguments—the first function for map and the second for reduce:

(ch03_mapreduce)

Alternatively, this can be done more succinctly in one line as follows:

def mapReduce(mapFunction, reduceFunction, myList):
    '''Applies mapFunction to myList to construct a new list
    and then applies reduceFunction to the new list
    and returns that value.'''

    return reduce(reduceFunction, map(mapFunction, myList))

Now, for example, we can use mapReduce to convert prices from U.S. dollars to alien dollars and add up the total, like this:

>>> mapReduce(triple, add, [14, 10, 12, 5])
123

The second version of mapReduce above is particularly elegant in the way that map and reduce are composed or “glued” in one line. Notice that in order for Python to evaluate the expression reduce(reduceFunction, map(mapFunction, myList)) it must first evaluate map(mapFunction, myList), since that is one of the arguments to reduce. So, the map function is applied to mapFunction and list myList to get the resulting list. Now, reduce has both the function and the list that it needs to do its thing.

The mapReduce function is so broadly useful that it inspired a major part of Google’s internal software design! To read more about it, you can (of course) just Google “mapReduce.”

Note

Functional Programming Meets Psychotherapy

The ideas behind functional programming actually predate the computer. A mathematical framework called the lambda calculus was developed by the logician Alonzo Church in the 1930’s to examine the limits of what is theoretically computable. (We address some of these issues in Chapter 7.) The lambda calculus served as the basis of actual programming languages, such as the early language LISP developed at MIT in the 1950’s. The “lambda” in lambda calculus is the reason for its appearance in Python’s anonymous functions.

LISP and related functional programming languages have been of particular interest to researchers in Artificial Intelligence (AI) because they are well suited for analyzing text. We can take a human’s typed input and write functions that process the words as strings and sentences as lists of strings. This is called natural language processing. (The “natural” here refers to human languages in contrast to programming languages.)

One of the early and controversial examples of natural language processing and artificial intelligence was the ELIZA program, first written by Professor Joseph Weizenbaum at MIT in the mid-1960’s. Eliza impersonated a psychologist and allowed the human user to enter text that ELIZA would process and return a simple response that—while not actually aware of the user’s emotions—seemed generally appropriate. Eliza was first written by Weizenbaum in a language called SLIP, but was later reprogrammed in LISP.

Here’s the beginning of an actual transcript of an interaction with ELIZA from an online version of the program (available here).

Eliza: Hello. I am ELIZA. How can I help you?

You:  I am learning about functional programming.

Eliza:  How long have you been learning about functional programming?

You:  I guess it has been a few weeks now.

Eliza: Can you elaborate on that?

Responses such as “Can you elaborate on that?” or even “Tell me about your mother” are commonly used and quickly reveal that ELIZA is actually rather clueless. While Weizenbaum evidently only intended ELIZA to serve as a demonstration of the power of natural language processing, some people actually took an interest in using ELIZA as their therapist! A book and a documentary have been made about Weizenbaum and ELIZA, and a number of free and commercial versions of the program are available, including some that have a very bad attitude and deliberately berate their “patient.”

3.7: Functions as Results

If functions can be the arguments to other functions, it must also be possible for them to be the results of functions, right? Take a look at this scale function and try to figure out what it does:

The scale function takes the number 42 as an argument and returns a function (the lambda indicates that we’re giving back a function) that we are then assigning to the variable f. So f is a function, but what does that function do? Well, for any argument x it returns 42 * x—as we see here:

>>> f(2)
84
>>> f(10)
420

There’s something odd here! In the definition of the scale function, the line:

return lambda x: n * x

makes it look like the function that we’re returning has two variables, n and x, whereas the lambda x indicates that this a function of just one variable, x. Indeed, in the examples above, we defined f = scale(42) and then we gave f just one argument as in f(2) and f(10).

When we said f = scale(42), the 42 was passed into scale‘s argument n, and n was replaced with 42. Therefore, scale(42) actually returned

../_images/Alien4.PNG

Maybe I can write a program that will write all my future CS programming assignments for me!

lambda x: 42 * x

That’s clearly a function of just one variable and that is the function that we then assigned to our variable f.

Although the scale function is admittedly not super-useful, the amazing thing here is that we wrote a program that can write other programs—a powerful concept that is widely used by computer scientists. Indeed, many complex programs are, at least in part, written by other programs.

By the way, rather than using an anonymous function inside our scale function, we could have given the function a name and returned that function. We do this as follows:

def scale(n):

    def multiply(x): # Here we are defining a new function,
        return n * x # but it's INSIDE scale!

    return multiply  # Here we are returning that function

Notice that the indented def multiply(x) indicates that multiply is being defined inside scale, so this is defining multiply to be one of scale‘s own variables, just like defining any variable within a function. The only difference is that multiply is a function rather than a number, list, or string. Then, once we’ve defined that variable, we return it. Now, calling scale(42), for example, gives us back a function and we can do exactly what we did a moment ago with the first version of scale:

>>> f = scale(42)
>>> f(2)
84
>>> f(10)
420

Functions that take other functions as arguments or return a function as a result are called higher-order functions.

3.7.1: Python Does Calculus!

../_images/Alien4.PNG

I’d rather impersonate them and alienate them!

In addition to learning English and other languages, our alien has been advised to study calculus before returning to Earth, so that it can better impersonate a college student.

You probably recall the idea of taking the derivative of a function. For example, the derivative of \(f(x) = x^2\) is a new function \(f'(x) = 2x\). For our purposes, the key observation is that the derivative of a function is another function. You may also recall that there are many rules for computing derivatives, and yet some functions are very hard to differentiate and others are downright impossible. So in some cases we may want to approximate the derivative—and we can do this computationally! In fact, let’s write a Python function that differentiates any function (approximately).

We looked back at our own calculus notes and found that the derivative of a function \(f(x)\) is a function \(f'(x)\) defined as follows:

\(\displaystyle{f'(x) = \lim_{h \rightarrow 0} \frac{f(x+h) - f(x)}{h}}\)

The derivative is defined as “the limit as \(h\) goes to zero.” However, for small positive values of \(h\), like \(h = 0.0001\), we get a good approximation of the limit. We can make the approximation as good as we want by making \(h\) as small as we want. Our objective, then, is to write a function called derivative that takes a function and a value of \(h\) as an argument, and returns another function that is the approximation of the derivative for that value of \(h\). Here we go:

def derivative(f, h):
    '''Returns a new function that is the approximation of
    the derivative of f with respect to h.'''

    return lambda x: (f(x+h) - f(x)) / h

Notice that we’re returning a function, as we’re supposed to. That function takes an argument x and returns the approximate value of the derivative at that value x for the given h.

Wait a second! It seems that the function that we’re returning is using a function f and two numeric variables, x and h—so why do we see just the variable x after the lambda? This is the same issue that we saw earlier with the scale function. Remember that when we call the derivative function, we pass it both a function f and a number h. Then, that function and that number are “plugged in” wherever we see a f and a h in the program. In the expression lambda x: (f(x+h) - f(x)) / h, both the f and the h are no longer variables—they are actual values (albeit the f is a value that happens to be a function). So, the lambda anonymous function truly only has one argument, and that’s x.

Let’s try it out. First, let’s define a function \(x^2\) and name it square.

def square(x):
    return x**2

Now, let’s use our derivative function:

>>> g = derivative(square, 0.0001)
>>> g(10)
20.000099999890608
../_images/Alien4.PNG

The second derivative is “accelerated” material!

The actual derivative of \(x^2\) is \(2x\), so the derivative at \(x=10\) is actually \(20\). We’re getting a pretty good approximation. That’s good, but here’s something better: if we now want to find the second derivative of \(x^2\), we can differentiate our first derivative. The actual second second derivative of \(x^2\) is simply \(2\) (for all values of \(x\)). Let’s see what our derivative function says.

>>> h = derivative(g, 0.0001)
>>> h(10)
2.0000015865662135

3.7.2: Higher Derivatives

Speaking of second derivatives, it sure would be handy to have a more general function that could find us the first, second, third, or generally, the \(k^{th}\) derivative of a function. Let’s write a function called kthDerivative(f, h, k) to do this. It will take arguments that include a function f, a small number h, and a positive integer k and will return an approximation of the \(k^{th}\) derivative of \(f\). We could do this “from scratch”, not relying on the existing derivative function that we just wrote, but since we have it already let’s use derivative.

What’s the base case? The simplest case appears to be when \(k=1\), in which case we just return the derivative of the given function. (Although it would be equally defensible to have a base case at \(k=0\), in which case we would just return \(f\) itself.) Otherwise, \(k > 1\) and we need to find the recursive substructure. Well, the \(k^{th}\) derivative of \(f\) is, by definition, just the derivative of the \((k-1)^{st}\) derivative of \(f\). So we can ask the kthDerivative function to find the \((k-1)^{st}\) derivative of f and then apply our derivative function to it. This should be fun and easy.

../_images/Alien4.PNG

A function of degree 4 is “quartic”, one of degree 9 is “nonic”. Believe it or not, one of degree 100 is called “hectic.”

def kthDerivative(f, h, k):
    '''Returns a new function that is the approximation of
    the kth derivative of f with respect to h.'''
    if k == 1:
        return derivative(f, h)
    else:
        return derivative(kthDerivative(f, h, k-1), h)

Let’s take this out for a spin by defining the “quartic” function \(x^4\) and then taking the third derivative, which we know to be \(24x\).

def quartic(x):
   '''Returns x**4.'''

    return x**4
../_images/Alien4.PNG

Please! Let’s not go any further down the slippery slope of bad math puns.

>>> g = kthDerivative(quartic, 0.0001, 3)
>>> g(10)
241.9255906715989

The actual answer should have been 240; we got an approximation due to the value we used for \(h\).

That was a high-velocity discussion of derivatives, but it demonstrated some of the integral features of functional programming.

3.8: RSA Cryptography Revisited

We began this chapter with a discussion of RSA cryptography. Recall that if Alice wants to be able to receive secure messages, then she can use the RSA algorithm to generate a public and a private key. The public key is entirely public—anyone can use it to encrypt a message to Alice. The private key, however, belongs exclusively to her; she uses it to decrypt messages encrypted using her public key. Of course, if Alice’s friend, Bob, wants to receive encrypted messages too, he can use RSA to generate his own public and private keys. He then shares his public key and keeps his private key secure. When you want to send an encrypted message to Alice, you use her public key to encrypt the message. When you want to send a message to Bob, you use his public key.

Our objective is to write a function called makeEncoderDecoder(), which takes no arguments, constructs the RSA encryption and decryption keys, and returns two functions: The first encrypts data using the encryption key (which is built into the function, so we don’t need to keep track of it—convenient when a key is hundreds of digits long!) The second function decrypts encrypted data using the decryption key (again built-in). Alice, Bob, you, and your friends will all be able to use the makeEncoderDecoder() function to construct encryption and decryption functions; each encryption function will be made public and each decryption function will be kept by its owner. Here’s an example of Alice using makeEncoderDecoder.

>>> AliceEncrypt, AliceDecrypt = makeEncoderDecoder()
Maximum number that can be encrypted is 34
>>> AliceEncrypt(5)
10
>>> AliceDecrypt(10)
5
>>> AliceEncrypt(31)
26
>>> AliceDecrypt(26)
31

Notice here that makeEncoderDecoder returned two functions (we’ll see in a moment how we can return two things), which we’ve named AliceEncrypt and AliceDecrypt. Then, we tested those two functions by encrypting them using Alice’s encryption function (which contains the encryption key inside of it) and then decrypting them with Alice’s decryption function (which incorporates the decryption key).

Let’s first remind ourselves how the RSA scheme works. We begin by choosing two different random prime numbers \(p\) and \(q\) (preferably large, but we’ll be able to decide how large later). We compute \(n = pq\) and \(m = (p-1)(q-1)\). We then choose the public encryption key \(e\) to be a random prime number between 2 and \(m-1\) such that \(e\) does not divide \(m\). Next, we construct the decryption key \(d\) to be the multiplicative inverse of \(e\) modulo \(m\)—that is, the unique number \(d\) such that \(d \leq m-1\) and \(ed \mod m == 1\). Now, we can encrypt a number \(x\) between 1 and \(n-1\) by computing \(y = x^e \mod n\). The value \(y\) is the encrypted message. We can decrypt \(y\) by computing \(y^d\mod n\).

We’ve already written functions that produce lists of prime numbers. We’ll use our efficient primeSieve function for that purpose. Recall that this function takes a list of consecutive integers from 2 to some largest value and returns the list of all primes in that range. Our first task will be to call the primeSieve function and choose two different prime numbers from that list. For now, let’s restrict the range of the prime numbers to be between 2 and 10. This will be useful for testing purposes, and later you can change the maximum value from 10 to something much larger.

To choose items at random, we can use Python’s random package. We tell Python that we want to use that package by including the line import random at the top of the file. Now, we have access to a variety of functions in that package. You can find out what’s in the package by looking at the Python documentation Web site or by typing import random at the Python prompt and then typing help(random), which will describe all of the functions in that package.

One of the most useful functions in the random package is random.choice. It takes a list as an argument and returns a randomly selected element of that list. Here’s an example of that function in action:

>>> import random
>>> random.choice([1, 2, 3, 4])
3
>>> random.choice([1, 2, 3, 4])
2

We need to choose two different prime numbers in the range from 2 to 10. We could use random.choice twice, one to choose each of the two prime numbers, but there is a chance that we’ll get the same prime number twice, which doesn’t work for RSA. So, we can use another function in the random package, random.sample. It takes two arguments: a list and the number of items that we want to choose randomly—but uniquely—from that list. The function returns a list of the randomly selected items. Here’s an example of random.sample in action:

>>> import random
>>> random.sample([1, 2, 3, 4], 2)   # Pick 2 items at random
[4, 3]
>>> random.sample(range(2, 100), 3)  # Pick 3 different items
[17, 42, 23]

When a function returns a list of several items and we know how many items will be in that list, we can give names to those items like this:

>>> import random
>>> a, b = random.sample([1, 2, 3, 4], 2)
>>> a
4
>>> b
3

In this case, we knew that the random.sample function was going to return a list of two items (since we asked it to!) and we assigned the first of those items to the variable \(a\) and the second to \(b\). This technique is called multiple assignment.

Now let’s assume that we’ve already written a function called inverse(e, m) that returns the multiplicative inverse of \(e\) modulo \(m\)—that is, the unique number \(d < m\) such that \(ed \mod m = 1\). We’ll write that function in a moment, but assuming it exists, we have the ingredients for the makeEncoderDecoder function:

def makeEncoderDecoder():
    '''Returns two functions:  An RSA encryption function
       and an RSA decryption function.'''
    #
    # Choose 2 primes:
    #
    p, q = random.sample(primeSieve(list(range(2, 10))), 2)
    n = p*q          # compute n
    m = (p-1)*(q-1)  # compute m
    print ("Maximum number that can be encrypted is ", n-1)

    #
    # Choose a random prime for e:
    #
    e = random.choice(primeSieve(list(range(2, m))))
    if m % e == 0:   # If e divides m, it won't work!
        print ("Please try again")
        return
    else:
        d = inverse(e, m)               # compute d
        encoder = lambda x: (x**e) % n  # encryption function
        decoder = lambda y: (y**d) % n  # decryption function
        return [encoder, decoder]
../_images/Alien4.PNG

Notice that this function is returning a list of two functions: the encryption and decryption functions! The encryption and decryption keys \(e\) and \(d\) are actual numbers that are embedded in those two functions, but \(x\) and \(y\) are the names of variables—the arguments that the user will ask to have encrypted or decrypted.

Finally, we need the inverse(e, m) function. We can implement it very simply by using filter, which we saw in Section 3.4. We’re looking for the single number \(d\) such that \(d < m\) and \(ed \mod m = 1\). So we can generate all of the integers between 1 and \(m-1\) (which is done with range(1, m)) and then filter all of the values \(d\) such that \(ed \mod m == 1\). Mathematicians tell us that there will be exactly one value of those. The filter function returns a list, so we use a sneaky Python trick and treat the call as if it were itself a list: we put [0] after it to pull out the first element and return it.

from functools import *
def inverse(e, m):
    '''Returns the inverse of e mod m'''
    return filter(lambda d: e*d % m == 1, range(1, m))[0]

You have to admit that this is amazing! However, we must admit that there are a few places where this function could be improved and extended. First, the prime numbers that we’re choosing from for \(p\) and \(q\) are in the range from 2 to 10. We could easily change the 10 to something much larger, but we almost certainly don’t want primes as small as 2. On the other hand, the primeSieve function expects to get a list of numbers that begins with 2 (do you see why?). To limit it to large prime numbers, we’d first need to generate primes beginning from 2 and then slice off the small ones. In addition, currently the makeEncoderDecoder might choose an encryption key \(e\) that is a divisor of \(m\). In this case, we’re told to try running the function again. That’s not a very nice solution. You might try to think of ways to fix this so that makeEncoderDecoder would keep choosing values of \(e\) until it finds one that is not a divisor of \(m\). You can do this with recursion, or you can do it with something called a while loop which we’ll see in Chapter 5.

You might also rightfully object that encrypting numbers is not as interesting as encrypting strings (i.e., text). We’d agree. The good news is that strings can be converted into numbers and vice versa, as we’ll see in the next chapter. Thus, it would not be difficult to encrypt strings by first converting them to numbers and then encrypting those numbers as we’ve done here. Decryption would first decrypt the number and then convert that back into the original string. In fact, that’s exactly how real encryption programs work!

3.9: Conclusion

../_images/Alien4.PNG

I’ve been wondering what’s going on inside my laptop.

In this chapter we’ve seen a beautiful idea: Functions are “first-class citizens” of the language, allowing us to treat them just like any other kind of data. In particular, functions can be the arguments and results of other functions. As a result, it’s possible to have general-purpose higher-order functions like map, reduce, and filter that can be used in many different ways by simply providing them with appropriate functions of their own. Moreover, we can write other higher-order functions that produce functions as results, allowing us to easily write programs that write other programs.

Now that we have explored the foundations of programming, we will turn our attention to a new question: “How exactly does a computer actually manage to do all of this amazing stuff?” To answer that question, in the next chapter we’re going to open the hood of a computer and see just how it works.