Artificial Intelligence courses traditionally used Lisp as their programming language of choice and although some courses across the world still do, it isn't nearly as popular as it once was. Lisp has a few interesting features. First, it is a functional language. Second, it views code as data and data as code (a feature known as homoiconicity). Third, it offered a meta programming feature called "macros" that made the language very flexible. Long before Domain Specific Languages (DSL) became hip, "Lispers" were writing programs composed entirely of DSLs.
Of all of Lisp's properties, homoiconicity was probably the one most critical to symbolic AI. In a field focusing on theorem provers and game playing, the ability to represent both programs and knowledge identically was the proverbial "killer feature". But they were by no means hardcore Haskellesque functional programmers, often wantonly mutating global variables (so denoted by their "earmuffs": *temperature*). Something strickly forbidden in today's functional programming languages.
As the fortunes of numeric AI waxed, the fortunes of symbolic AI waned and because in many people's minds they were bound together, Lisp suffered a similar fate becoming somewhat of a niche language. In many ways, this isn't exactly true but it was certainly the perception. However as computational power has increased in the last decades, many of the concepts developed in the early days of computer science are reappearing. (Some have actually observed that everything in computer science was actually invented before 1970, just waiting for the increased computational power).
And certainly one of those early ideas is functional programming, which is making quite a comeback. The last decade or so has seen the emergence of Haskell, Elixir, F#, Clojure, Scala and other functional programming languages. Traditional languages either have or are adding functional programming features (Java now has anonymous functions or lambdas). Functional programming is experiencing quite a renaissance. I think the main reason is summed up in Steve Yegge's post, The Kingdom of Nouns. For a very ranty but not wrong video watch Object-Oriented Programming is Bad. For a more measured approach, there is Clojure, Made Simple that explains, at least, Clojure's rationale vis-a-vis OOP.
This last bit may have hurt your feelings; I'm sorry. Ironically, it is very likely you never had to be convinced to use OOP in the first place so think how I feel. I cut my teeth on Java and read Bruce Eckel's Thinking in Java to be the best OOP programmer I could be. I read books on test driven development, refactoring, design patterns, etc., all trying to be better.
At some point I moved to Ruby, which was a breath of fresh air. Ruby is a bit closer to SmallTalk, the original OOP language. This was almost certainly part of Java's problem. Java was a very poor port of the OOP ideal espoused by SmallTalk. (If you ever wonder what OOP was supposed to be, download a Squeak environment).
More surprisingly, Ruby has some strong functional programming aspects (see Why Ruby is an acceptable Lisp). As I found myself using more and more of Ruby's functional programming capabilities, I became more and more interested in functional programming. After struggling a bit with Haskell and Scala, I eventually stumbled onto Clojure and after some hemming and hawing, I was sold.
Ideally, I would like to return to an AI course that used Lisp (Clojure) as the main language. Unfortunately, AI has grown to be such a huge beast of a topic, that's almost certainly impossible, at least at right now. Instead what I hope to do is to convey why Python is an acceptable Lisp (actually, with a few additional 3rd party libraries it can be an actual Lisp but that's a different story) and how you might go about using it as such. In any case, it's worth learning a bit of functional programming. You will at least be a better OOP programmer in the end; afterall you are getting a Computer Science degree (or at least taking a course in the Computer Science program.
So rather than require the use of Lisp, I require the use of Python in a particular style, a functional style. This course uses Python as the official language (2.7.X) but you must use it in a "functional style". That's right...OOP is forbidden in this class unless you are using a standard library. This is possible because Python is not a pure OOP language (like Java). It's entirely possible to write programs composed entirely of "free" functions without any classes.
Don't panic! Grab your towel and start reading this notebook. It will attempt to walk you through the basic principles of a functional style of Python. I think you will find the approach rather agreeable.
When I think of Functional Programming, several things come to mind although these are not universally true of all functional programming languages.
Often immutable data structures are included in this list. We'll see about that. Most of the built-in collections in Python are mutable (except for Tuples) and while there are libraries to inject immutable versions of the standard data structures, we might not go quite that far.
At a higher level, we can say the Functional Programming approach constructs programs by building up small easily testable pure functions into a domain specific language (DSL) for the problem at hand called by impure functions at the edges of the program. A pure function is operates only on its formal arguments, returning a value (there would be no reason for a pure function to return nothing). They are extremely easy to reason about and test. An impure function, on the other hand, interacts with the outside world in some way: a database, http request, http post, or collecting input from the terminal. They generally require some kind of external setup to test. They can be difficult to reason about: did the functional fail because it isn't written correctly or because the API endpoint is down or changed?
These functions, both pure and impure, can be assembled in a top-down (start with the main entry function) or bottom-up (start with the lowest level pieces) fashion. Gerald Sussman in The Structure and Interpretation of Computer Programs called the top-down approach "programming by wishful thinking". All will be made clear in time.
But first, since not everyone may be familiar with Python in general, we're going to start with the basics and work our way up. I assume that you can program in some language, probably Java but maybe Ruby and that variable isn't mysterious to you.
Unless specifically overidden in this document, you should follow PEP-8 stylistic conventions in all your code.
Most programming languages are made up of basic constituents that we assemble to make programs. This includes basic data types ("primitives") for numbers and strings, operators for those basic types like addition or multiplication, and collections. The bundling of code into reusable units, most generally called procedures but also called functions or methods. There is also flow control and iteration. We'll review all of these here.
We'll start with the basic numeric, string and boolean primitive data types:
type(2)
type(2.1)
type("python")
It is worth noting that like Ruby, Python has many different ways of specifying Strings which include single quotes, double quotes and three double quotes. The last has a special meaning that we'll delve into later.
type(True)
type(3 + 7j)
type(None)
As an aside, Jupyter Notebook automatically prints the last value produced by a code cell which might be None which is Python's null or nil.
It is worth noting that the "natural" floating point of type of Python is float, not double as it is in many languages. Additionally, Python uses j for the square root of -1 instead of i.
Exercise
While not a basic type, find the documentation for Python's type for dates/times.
It is possible to assign values (and collections of expressions) to names. This seems easy enough but is actually a pretty complicated topic. If you are curious, you can watch by Rich Hickey. We will mostly side step these issues.
In Python, you assign a value to a name using =. There are rules for names. In general, Python uses "snakecase" so that a variable "Number of Accounts" is number_of_accounts and not numberOfAccounts. This is true for functions as well. They must begin with a letter and may contain letters, numbers or underscores. Unlike some other languages, you cannot include other special symbols such as ?, !, etc.
foo = 2
print foo
In general, Python allows you to "rebind" a variable to a new value.
foo = 3
print foo
Python supports operations on all the basic types you might imagine but there are a few "gotchas".
2 + 2
2 + 2.0
2 * 2
2 * 3.0
Exercise
Find a reference for all of Python's operators. You may find some surprises here and there. For example, & and and are not the same thing.
Here we can see type promotion when a float and int are combined in an expression. This doesn't always happen as expected:
2 / 3
2 / 3.0
If you want the first expression to work correctly, as in Python 3, you can import "the future":
from __future__ import division
2 / 3
That import should be in every program you write. It'll save you a ton of headaches later.
"2" + "3"
Here we see that + is semantically overloaded to mean "append" as well as "addition" when the arguments are strings. However, you will see below that when the arguments are of mixed types, there is no automatic type promotion:
try:
2 + "2"
except Exception as e:
print "Exception (%s): %s" % (type(e), str(e))
Note that I knew this would fail so I wrapped the 2 + "2" expression in a try/except block. We'll talk about that later.
In this case, you will need to cast the int:
str(2) + "2"
There are a variety of casting functions:
int("2")
float("2")
ord("2")
The last one might be a bit cryptic...the UTF-8 code for "2" is 50. In order to go the other way, we do:
chr( 50)
Because we often interact with simple programs at the console/terminal, string formatting is often very important. Python sports several ways of doing string formatting.
This uses the % operator.
"pi to 4 decimals is %0.4f" % 3.14159265359
"Hello %s, I hope you love %s" % ("Student", "Python")
This uses the format function.
"pi to 4 decimals is {:0.4f}".format(3.14159265359)
"Hello {0}, I hope you love {1}".format("Student", "Python")
Which style to use is a bit contentious in my mind. Many other programming languages use the C-style formatting and so you only need to learn one string formatting DSL. On the other hand, the % version has been deprecated in Python 3 so...you can name your own poison. The newer version is a lot more flexible allowing for reuse of values as well as named values. You can find more documentation here: Python String Formatting.
Ultimately, for your assignments, the important part is that you print out exactly what is requested since many parts will be automatically graded. Failure to follow directions is still failure.
Python has a large number of data structures or collections. We will cover each one and the basic operations of each. You should refer to the documentation of each for more information.
The most basic collection is a List. The constructor function for a list is list. An empty list can also be created with [] or list(). There are a few cases where using list() is required or Bad Things happen.
a = [1, 2, "a", True]
print a
Technically, I do not need the print a above, I could just put a and it would print out because that's the last expression in the codecell...but it looks weird. I will generally be verbose and use print even when I do not need to.
Above we see a list of four items. We note that they do not all have to be of the same type. We add to a List with append:
print a.append("foo")
Jupyter Notebook is designed to not print out whatever a language's version of "nothing" is. Without the print statement above, we would not have seen the None. I wanted to show you the None because it illustrates an important "gotcha" in Python. Guido van Rossum does not believe in fluent interfaces.
A Fluent Interface typically returns the modified object so that you can call another function on it. Another name for this is method chaining. They are popular in Java, C# and Ruby and some 3rd Party Python libraries do it as well...but not the standard Python libraries.
Our expectation is that a.append("foo") will return a with "foo" appended to it basically so we can do something else to a. For example, we might append something else and then sort the list. Guido will have none of that:
print a
try:
print a.append("bar").append("baz").sort()
except Exception as e:
print "Exception: " + str( e)
This can often be a really inscrutable error but if you break it apart you get the following:
result1 = a.append("bar")
result2 = result1.append("baz")
result3 = result2.sort()
The problem is that result2 is not a List but None which does not have a method named append.
Instead you must make each call separately and note that there is no "result" to save, a is being modified in place:
a = [1, 2, "a", True]
a.append("foo")
a.append("bar")
a.sort()
print a
There is a second "gotcha" in Python. In the bad old days when words meant something, a function was a procedure that was not attached to any object whereas a method was a procedure that operated on an object (actually, in Smalltalk these were called "messages", you sent a "message" to an object).
Keeping this distinction in mind, it is important to know that some procedures involving collections are functions and some are methods. For example, append is a method of List. However, to get the length of a collection you use the len function, not the len method:
len(a)
This can be confusing for people coming from Ruby who expect to be doing something like a.length() or a.count(). That won't work. There are a number of reasons for this that go deep into the philosophy of Python by somewhat derail our present goal so we will not go into it. Suffice it to say that anything that can have a length implements the method __len__ and the function len just delegates to that. This pattern is used throughout Python.
A List is a random access indexed collection so we can get any individual element we want in the typical way:
a[0]
a[1]
a[-1]
Yes, negative indices are permitted and they start from the end. In addition to integer indices, it is possibly to use slices:
a[1:3]
which returns a slice of the List a starting at index 1 (inclusive) and going to index 3 (exclusive). You can leave off the last number if you simply want to go to the end:
a[2:]
In Python, Lists are mutable, that is, you can change the value at specific locations as well as change the size. We have already seen examples of the latter. Let's look at the former:
a[2] = 100
print a
There is also a function for this insert. You can also remove items by either removing the actual value with remove which removes the first occurrence of the value from the list:
a.remove(100)
print a
or del which removes the item at the index:
del a[0]
print a
strangely, del is neither a function nor a method but a statement in the Python language. We will talk about the difference between statements and expressions later.
A Tuple is similar to a List except that it is immutable. Once the values are set, you cannot change them. The constructor function is tuple. There is no such thing as an empty Tuple. Tuples are incredibly useful in Python and you will see many places where Python automatically creates and consumes them.
b = (1, 2, True)
print b
So far, a Tuple looks just like a List using parentheses instead of square brackets...
try:
b[0] = 3
except Exception as e:
print "Exception (%s): %s" % (type(e), str(e))
Nope. You can't change the value of any element of a Tuple. Of course, things can get a bit weird:
b = (1, 2, a)
print b
a.append(3)
b
So while the Tuple itself is immutable, if an element of a Tuple is mutable, you can change it. You are strongly discouraged from doing so.
One last thing that can be weird...you will sometimes need a Tuple of one element:
b1 = (1)
print b1
print type(b1)
Huh, that did not go as planned. The trick is as follows:
b1 = (1,)
print b1
print type(b1)
See that extra comma, (1,)? That makes the difference.
We will have more to say about Tuples later.
The Dict(ionary) is Python's Hash/Map/Hashmap collection. The contructor function is dict while the literal is {}:
c = {"a": 1, "b": 2}
print c
The keys of a Dictionary must be immutable (which makes sense since underneath, a hashing function is being used and changing the underlying value of the key would prevent it from being found).
You can use square brackets to "index" a Dictionary by key or the function get. They have different semantics and usages. Here is square brackets:
c["a"]
c["b"]
try:
c["c"]
except Exception as e:
print "Exception (%s): %s" % (type(e), str(e))
so you will get a KeyError if the key does not exist. If you ever see an error that says that keys must be numbers, you have accidentally gotten a List where you expected a Dict.
If you use get instead of square brackets for a non-existent key, you will get None instead of an error:
print c.get("c")
which can also be a bit problematic because it's kind of a silent failure. get also allows you to provide a default value:
print c.get("c", 1000)
in which case, get redeems itself.
Adding a new value to a Dictionary is as simple as assigning a value to a key:
c["d"] = "nargle"
print c
and we can use del to remove a key:
del c["d"]
print c
Our final collection is sets. The constructor function for Sets is set. You can only create sets using the literal notation as long as they contain something (there is no literal for the empty set). Additionally, it is only the way the contents are specified that ultimately separates a Set literal from a Dict literal.
d = {1, 2, 3}
print d
Because sets are not ordered, there is no way to access a specific element of the set. You can remove elements, though:
d.remove(1)
print d
And, using add, well, add elements to the set:
d.add(4)
print d
Which leads us to the in operator. It makes sense that you can use in to see if a value is "in" a set:
1 in d
2 in d
but you can also use in to test to see if a key exists in a Dictionary:
print c
'a' in c
'c' in c
which helps prevent errors involving non-existent keys. You can also check to see if a value is in a list:
print a
'bar' in a
There's a lot more to collections. You can refer to the official Python documentation. We'll cover some other topics regarding collections as well.
We only need one more basic unit for a Functional Python and that's functions. Named functions are created by using the def statement, the name of the function, formal parameters, an optional documentation string and an indented body. If the function returns values, it must use a return statement; otherwise, it returns None.
def my_function(a, b):
"""my_function takes two arguments and does some really cool stuff"""
return a + b
my_function(2, 3)
There isn't a whole here that's different from other programming languages.
One of the few "gotchas" that some might run into is the necessity of a return statement. In languages like Java, C#, Python, the language is comprised of statements and expressions. Statements do not return a value whereas expressions do. In other languages, like Ruby, Clojure and many other functional programming languages, everything is an expression and there are no statements. In Ruby, if is an expression, you can assign the result to a variable:
foo = if a > 0 then
"frank"
else
"bob"
end
And while Python's conditional looks very similar, it is a statement not an expression (we'll talk about conditionals in a bit). So you may definitely not assign the result to a variable because there is no result.
It is a very common mistake to write a function, call it and get None back and wonder what went wrong. Make sure that if your function is supposed to return something (not all of them do), it is actually using return to return it.
The interesting thing about Python functions is that they are values themselves:
my_function
which means you can assign them to variables and pass them around as values:
your_function = my_function
your_function( 10, 20)
I'm going to write a function below that takes a function as a formal argument and calls it with the arguments 10 and 2 and returns the result:
def call_f(f):
return f( 10, 2)
and call it with my_function as an argument:
call_f(my_function)
It might not be obvious yet, but this is very powerful. We can also use functions to make functions:
def create_add_to_it(it):
def f(x):
return it + x
return f
what I have done is create a function create_add_to_it that takes a single formal argument, it. The body of the function defines a new function f with a formal argument x that adds it and x. The function then returns f. The goal is to create a function that will add any number x to whatever it was set to when the function f was created:
a22 = create_add_to_it(22)
print type(a22)
Here we can see that create_add_to_it really returned a function and we assigned it to the variable a22. Now we use it:
a22(2)
a22(10)
The function f that we create remembers the value of it when it was created by "closing" over the value and is called a closure. We will have more to say about closures later.
There are a lot of other bells and whistles associated with functions in Python and we'll go over a few of them here. Generally speaking, the typical arguments to a function in Python are ordered, that is, the function my_function expects a and then b when it is called:
my_function(3, 2)
Sometimes, I have the values I need to call a function but they are in a collection. The direct way to fix this problem might be something like:
args = [3, 2]
my_function(args[0], args[1])
However, Python contains a bit of syntactic sugar via the splat operator that permits us to do the following:
args = [3, 2]
my_function(*args)
Note that this works for tuples as well:
args = (3, 2)
my_function(*args)
Python also supports something like the reverse of splat in that a function can return more than one value. You can either capture every value individually by assigning in parallel to more than one variable or capture all the values as a collection (Tuple) in one variable.
Let's demonstrate by creating a function that does all the basic operations on two arguments:
def everything(a, b):
assert b != 0
return a + b, a - b, a * b, a / b
Here we know that everything returns 4 values so we assign in parallel to 4 variables:
a, b, c, d = everything(10, 2)
print a
print b
print c
print d
Here we assign to one variable which will hold a Tuple of the results:
a = everything(10, 2)
print a
It is an all or nothing thing, however. You must either get all the values in one variable or a variable for every value:
try:
a, b, c = everything(10, 2)
print a
print b
print c
except Exception as e:
print "Exception (%s): %s" % (type(e), str(e))
The error above tells us that everything returned more than 3 values.
Python also permits named arguments a la Objective-C. In fact, you don't really have to do anything to get it work. If you know the names of the formal arguments to a function, you can use them like so:
a = everything(a=2, b=10)
print a
In case you really want to get crazy, by naming the arguments, you can ignore the order:
a = everything(b=10, a=2)
print a
This leads to a few interesting things. First, by using double splat, we can use a Dict to supply the argument values in a call to a function:
args = {"a": 2, "b": 10}
a = everything(**args)
print a
Second, we can provide default values to our formal arguments with the proviso that no formal argument without a default value can appear after a formal argument with a default value. The following is ok:
def everything(a, b=10):
assert b != 0
return a + b, a - b, a * b, a / b
But the following is not:
def everything(a=10, b):
assert b != 0
return a + b, a - b, a * b, a / b
BAD - if a has a default value, so must b.
Let's see how calling the good version works. The first execution will use the default value of b:
a = everything(20)
print a
This execution will supply a different value of b:
a = everything(20, 100)
print a
So far, we've been talking about named functions. There are also anonymous functions or lambdas in Python as well. They are pretty limited in that they can only only be a single expression. They look something like this:
lambda x, y: x + y
Of course, that's not very useful. Where a lambda is useful is in a situation like we had above where I had a function that took a function as an argument. If I have a very simple computation, I don't have to use a named function but can supply a lambda instead. Remember that call_f applies 10 and 2 to the supplied f which will be an anonymous function this time:
call_f(lambda x, y: x * y)
Consider the following code and its execution:
def add_total(xs):
total = sum(xs)
xs.append( total)
return xs
x1 = [1, 2, 3, 4]
print "Before..."
print "x1", x1
x2 = add_total( x1)
print "After..."
print "x2", x2
print "x1", x1
Ideally, we would like for x1 not to change. This is what would happen in a functional programming language with immutable data structures. However, Python's data structures (except Tuples) are mutable which is the reason for the behavior we see.
While it is possible to add immutable data structures and all the goodies that go with them to Python via 3rd party libraries (these are mentioned at the end of this document), a poor person's way to achieve something similar is through deepcopy:
from copy import deepcopy
def add_total(xs):
xs_copy = deepcopy(xs)
total = sum(xs_copy)
xs_copy.append(total)
return xs_copy
x1 = [1, 2, 3, 4]
print "Before..."
print "x1", x1
x2 = add_total(x1)
print "After..."
print "x2", x2
print "x1", x1
In either case, you need to be careful. If you do not make deep copies, at least make sure you always return the modified data structure rather than relying on the mutation in place (as Python normally does).
If you decide to make deep copies, realize that you are doubling the amount of memory you are using. The efficient immutable data structures in Clojure and the like use structural sharing to minimize duplication. With structural sharing, x1 and the modified x2 "share" [1, 2, 3, 4] and only x2 has 10 appended to the end.
When it comes to writing certain maching learning algorithms, you will most definitely want to do deep copying...even if you were using OOP. In general, if you are very careful, always returning the modified data structure is the first easiest thing to do.
We are now in a position to decompose Object Oriented Programming to a more functional, dataflow style of programming.
As noted in Yegge's blog post, in a language like Java, everything must start out as a noun. This is why the namespaces of Java are littered with things like CommandExecutor, PersonFactory and other such nonsense. Java requires functions to belong to classes, that is, you can only have methods.
Under the covers, however, objects are really just a syntactic sugar for records and procedures. To see how this is so, let us look at a typical Java class definition:
public class Person {
public Person(firstName, lastName) {
this.firstName = firstName;
this.lastName = lastName;
}
public String getFirstName() { return firstName; }
public String getLastName() { return lastName; }
public void setFirstName( firstName) { this.firstName = firstName; }
public void setLastName( lastName) { this.lastName = lastName; }
public String getFullName() { return firstName + " " + lastName; }
}
There are a few things to note here. First, for whatever reason, languages get associated with conventions and the naming convention of arguments and variables in Java is "camelCase". In Python, it is "snake_case". These conventions are often spelled out. In the case of Python, the conventions are documented in PEP 8. You are to follow the PEP 8 conventions for all submissions in this course unless specifically overruled. Failure to do so is a failing submission.
But more to the point, we have a class definition, Person and various getters and setters. The only slightly interesting method is the getFullName method because it does actual work with the values or state of a Person object. But the most important part is this. What is this? (Note that the PEP-8 convention is to use self instead of this but I use this for consistency.)
Let's look at the Python version for further insight:
class Person:
def __init__(this, first_name, last_name):
this.first_name = first_name
this.last_name = last_name
def set_first_name(this, first_name):
this.first_name = first_name
def set_last_name(this, last_name):
this.last_name = last_name
def full_name(this):
return this.first_name + " " + this.last_name
def __str__( this):
return "Person[%s, %s]" % (this.first_name, this.last_name)
Again, this makes an appearance everywhere. Unlike Java, however, this makes an appearance in the method definitions. This was a conscious design decision on van Rossum's part. The lack of this in method definitions in Java is syntactic sugar. (It is actually a common error to forget to include this as a first argument in a method definition. If you see an error that says f takes 2 arguments, 3 arguments given, you have most likely made this mistake).
But this isn't the only way that Python exposes some of the underlying machinery. Let's instantiate a Person object:
class Person:
def __init__(this, first_name, last_name):
this.first_name = first_name
this.last_name = last_name
def set_first_name(this, first_name):
this.first_name = first_name
def set_last_name(this, last_name):
this.last_name = last_name
def full_name(this):
return this.first_name + " " + this.last_name
def __str__(this):
return "Person[%s, %s]" % (this.first_name, this.last_name)
p = Person("Harry", "Potter")
So far, so good. If we print out the object, we get the usual object gobblygook:
p
If instead we "cast" the Person to a str, the Person's __str__ method is called:
print str( p)
Unlike in Java, we didn't need the getters:
print p.first_name
print p.last_name
We didn't really need the setters either:
p.first_name = "Lily"
print p # print calls str()
And as if it couldn't get any more strange, we can add attributes on the fly:
p.first_name = "Harry"
p.title = "The Boy Who Lived"
print p
print p.title
And, of course, we can call our method that does some real work:
print p.full_name()
We've learned a few things from this experiment. Mainly, a class definition is syntactic sugar for a Dict and associated functions that automatically receive that Dict as a first argument. We could just as easily have written:
def person_set_first_name(person, first_name):
person.first_name = first_name
def person_set_last_name(person, last_name):
person.last_name = last_name
def person_full_name(person):
return person.first_name + " " + person.last_name
def person_str(person):
return "Person[%s, %s]" % (person.first_name, person.last_name)
This is, in fact, how classes and objects are represented in many objected oriented languages. The state is stored on the heap and when a method is invoked on an object instance, the interpreter looks up the type of the object and then looks for a munged name exactly like those shown above and invokes it with the object state as the first parameter to the method. The only difference in this regard between Java and Python is that Python has less syntactic sugar but the basic process is the same.
In the bad old days of the C programming language, this is how a lot of programming was done. You created records (basically Dicts) and in functions that operated on those records. This is now, more or less, the functional approach.
In Python, you have several options for replacing classes and objects. In all cases, you will or may need to add functions that work on the objects. They should generally be named using verbs. For example, full_name might be calculate_full_name. We'll talk a bit more about naming later.
On the other hand, you have a few more options in Python for state. You can use a Dict or a NamedTuple.
The simplest thing is to use a Dict for your state. In a functional programming language, the key names of a Dict become the data interface. You may not know at the start what you want that interface to look like. The Dict gives you the ultimate flexibility:
p = {"first_name": "Harry", "last_name": "Potter"}
print p
This flexibility comes at a cost:
try:
print p.first_name
except Exception as e:
print "Exception (%s): %s" % (type(e), str(e))
However, we can easily add new attributes:
p["title"] = "The Boy Who Lived"
print p
The main advantage here is that every bundle of data has the same exact interface and functions: the functions of a Dict. We can use [] or get on every "object" regardless of whether the data represents a person, a car, or a chart.
Sometimes we want something a bit more structured. In that case, we can use a namedtuple. The namedtuple prevents us from accidentally creating or accessing unknown fields. The tradeoff is that we no longer are working with a Dict with a more general interface.
from collections import namedtuple
person = namedtuple('Person', ["first_name", "last_name"])
p = person("Harry", "Potter")
print p
print p.first_name
print p.last_name
try:
p.title = "The Boy Who Lived"
except Exception as e:
print "Exception (%s): %s" % (type(e), str(e))
try:
p.first_name = "Lily"
except Exception as e:
print "Exception (%s): %s" % (type(e), str(e))
The first example above shows that we cannot add arbitrary attributes while the second reminds us that Tuples are immutable. There truly is no free lunch.
Some may be wondering about encapsulation. What about making state private from the awful programmers? The dataflow approach recognizes that data and operations on data are what programs are about and there's no particular reason to encapsulate it. Programmers should be treated like adults. In libraries especially, the public functions and data should be made clear and failure to abide by this declarations is the programmer's fault.
On the other hand, you can get as much or as little encapsulation as you like by using Closures:
"Closures are a poor person's Class; Classes are a poor person's Closure"
Another approach--which admittedly has some dangers in a language like Python where the data structures are mutable--is to use closures.
We saw a closure before:
def create_add_to_it(it):
def f(x):
return it + x
return f
create_add_to_it takes a value, it, and then returns a function that will add some user supplied x to it. The definition of f closes over the value of it and has access to it even after the function f is returned from create_add_to_it.
If you squint, you can think of a class (object) as a closure. The constructor sets values and the methods have access to those values along with their formal arguments. For example:
person = namedtuple('Person', ["first_name", "last_name"])
def construct_person(first_name, last_name):
p = person( first_name, last_name)
def f():
return p.first_name + " " + p.last_name
return {"full_name": f}
harry_potter = construct_person("Harry", "Potter")
print harry_potter["full_name"]()
This probably isn't the best or easiest use of a closure. After all, we've basically replicated how class works. However, closures can be vary powerful in functional programming. You can create a function that would otherwise require a lot of unchanging but necessary arguments by using a function factory that closes over those parameters. Consider the following example:
Imagine we have a problem where we have:
And all we want to do is suggest a location to move to and have find out if the move really happened:
def construct_move_fn(world, movement_rules, costs):
def move( current_location, desired_location):
# do a whole bunch of stuff to see if the robot can move from current to desired.
return actual_location, cost
return move
move = construct_move_fn(world, movement_rules, costs)
current_location = (0, 1)
desired_location = (1, 1)
location, cost = move(current_location, actual_location)
print location, cost
construct_move_fn takes the world (in some format), movement_rules (can you make diagonal moves or only horizontal or vertical moves, how many "spaces"?), and the costs of moving through different terrains or distances. It creates a function move that takes as arguments the current_location of the robot and the desired_location. It will then do a bunch of logic checks to make sure the movement rules are adhered to in the context of the world (for example, a diagonal move might be illegal, the move itself might be illegal because the desired location contains a locked door or the location may not even be in the world!) and return the actual location the robot ends up in along with the cost.
We can then instantiate a specific move function and call it.
By using a closure, we have closed over the arguments that aren't going to change during this run of the program but left them open to change in other runs.
What about Polymorphism? You know...you have Dog, Cat and Mouse objects and you call speak() on each one and it does The Right Thing?
There are actually a number of ways that functional programming languages obtain polymorphism, usually in ways that exceed those possible with OOP. One such way, ported to Python, is with multimethods. Multimethods are interesting because they're more general than the polymorphism you can obtain solely with types. The multimethods module is from Adam Bard's Implementing Multimethods in Python.
from multimethods import *
Multimethods let you change the method invoked on arbitrary values. You set up a decorator @multi that takes the same number of arguments at the implementation methods but returns a value. Each implementation method in turn has a @method decorator that indicates its dispatch function and the value that should cause it to be invoked. Let's do a few concrete examples. The first one will be based on types:
@multi
def print_type(arg):
return arg.__class__
@method(print_type, int)
def print_type( arg):
print "We have an int: " + str( arg)
@method(print_type, list)
def print_type( arg):
print "We have a list: " + ",".join([str(a) for a in arg])
@method(print_type, person)
def print_type( arg):
print "We have a person: " + str( arg)
@method(print_type) # default
def print_type(arg):
print "Not sure what we got: " + str( arg.__class__)
print_type([1, 2, 3])
print_type(1)
print_type(person("Severus", "Snape"))
print_type(2.3)
There are several things to note here:
print_type on various arguments and the correct implementation was executed.@multi.int and list that we couldn't normally add new functions to.As mentioned, you don't have to dispatch on types. That's the beauty of multimethods.
Here's another example that dispatches the subtotal of an order. If the subtotal is over \$200, then we give a 10% discount and free shipping. If the subtotal is over \$100 but less than \$200, we give free shipping, but if the total is over \$50.00 but less than \$100, we give a 5% discount. Below \$50, we do nothing.
@multi
def calculate_order_discount(order):
if order["subtotal"] > 200.00:
return "discount+free_shipping"
if order["subtotal"] > 100.00:
return "free_shipping"
if order["subtotal"] > 50.00:
return "discount"
return "none"
def discount_order(order, discount):
order["discount"] = order["subtotal"] * discount
order["subtotal"] = order["subtotal"] - order["discount"]
order["total"] = order["total"] + order["shipping"]
return order
def add_free_shipping(order):
order["shipping"] = 0
order["total"] = order["subtotal"]
return order
@method(calculate_order_discount, "discount+free_shipping")
def calculate_order_discount(order):
return add_free_shipping(discount_order( order, 0.10))
@method(calculate_order_discount, "free_shipping")
def calculate_order_discount(order):
return add_free_shipping(order)
@method(calculate_order_discount, "discount")
def calculate_order_discount(order):
return discount_order(order, 0.05)
@method(calculate_order_discount, "none")
def calculate_order_discount(order):
return order
Here are some calls to calculate_order_discount:
print calculate_order_discount({"subtotal": 195.50, "shipping": 5.95, "total": 201.45})
print calculate_order_discount({"subtotal": 225.00, "shipping": 5.95, "total": 230.95})
print calculate_order_discount({"subtotal": 10.99, "shipping": 5.95, "total": 16.94})
print calculate_order_discount({"subtotal": 74.98, "shipping": 5.95, "total": 80.93})
There are times, however, when it is nice to have a Type, something that acts like a primitive. This occurs far less frequently than those who are used to OOP might think but if your program really, really needs a Rational type then making a Rational class is probably the right way to go. This will happen far less frequently that you imagine.
If you find yourself trying to justify making a class, think to yourself, is this like int, float or datetime? If it is, then go ahead. If it isn't, then use a Dict.
So the basic model of the functional program is one of a flow of data. The data represents the state of the program, stuff that probably came from the "outside" world, is transformed in some way, and then this result is communicated to the outside world.
Flow Control is achieved in Python with the usual suspects: if and while.
if True:
print "By Zeus's hammer!"
else:
print "By Aquaman's trident!"
if False:
print "By Zeus's hammer!"
else:
print "By Aquaman's trident!"
There is also a one-liner version if you want to work with values:
saying = "By Zeus's hammer!" if True else "By Aquaman's trident!"
print saying
saying = "By Zeus's hammer!" if False else "By Aquaman's trident!"
print saying
In Python, a multibranch conditional is created with elif:
if True:
print "By Zeus's hammer!"
elif False:
print "By Aquaman's trident!"
else:
print "By Odin's spear!"
if False:
print "By Zeus's hammer!"
elif False:
print "By Aquaman's trident!"
else:
print "By Odin's spear!"
if False:
print "By Zeus's hammer!"
elif True:
print "By Aquaman's trident!"
else:
print "By Odin's spear!"
Of course, your tests should be more interesting that the Boolean literals above. It is worth noting at this juncture that the conjunction operator is and not &. Additionally, the inequality operators chain:
x = 10
y = 20
if 0 < x < 20:
print "yes, it is in the range"
if 0 < x < 20 and 0 < y < 100:
print "yes, they are both in the range"
It's worth looking at all the Python Boolean operators. There are some additional surprises there like when to use not.
while comes in handy when you must conditionally evaluate some stream or collection:
xs = "abcdefghijk\nlmnopqrstuvwxyz"
result = ""
x = xs[0]
while x != "\n":
result += x
xs = xs[1:]
x = xs[0]
print result
An interesting side note, Python treats the string xs as a List so we can use random access and slicing.
Looking narrowly at data flow, we find we often have collections of similar data records such as people, orders, items for sale, etc. And that we often need to perform operations on these collections. For example, if we need to re-invoice all past due orders, we will iterate over the orders, determine which ones have not been paid in the last 30 days and send an email indicating that they are over due.
There are a number of ways to do this, even in Python. The simplest way is to use for:
for x in [1, 2, 3, 4]:
print x
for is the perfect loop to use at the impure boundaries of your program, for example, when you are reading data or writing data. The for loop already eschews the problems associated with iterating using indices as JavaScript or old fashioned Java:
xs = [1, 2, 3, 4];
for (int i = 0; i < length( xs); i++) {
println( xs[ i]);
}There are some algorithms that require actual knowledge of the indices. This can be achieved using enumerate. While not particularly functional, since we are mostly "stuck" with mutable data structures, we should use what Python provides:
for i, x in enumerate(["a", "b", "c", "d"]):
print i, x
An equally common operation is to apply a function to each element of a List, creating a new List:
def process(x):
return x ** 2
xs = [1, 2, 3, 4]
result = []
for x in xs:
result.append(process(x))
print result
It is more Pythonic to use a List Comprehension:
result = [process(x) for x in xs]
print result
In functional programming, this operation is called map. Python has a map function as well. It takes a function and a List as arguments:
result = map(process, xs)
print result
Sometimes we want to operate on a subset of the List, xs. This operation is called filter and is built into the List Comprehension. The Pythonic Way is:
result = [process(x) for x in xs if x % 2 == 0]
print result
The functional way is to use filter. We'll use a lambda for our predicate function:
result = map(process, filter(lambda x: x % 2 == 0, xs))
print result
The final operation of functional programming's "Holy Trinity" is reduce. There is no Pythonic reduce because reduce results in a single value not a List (although the single value, confusingly enough, can be a List). reduce takes a function of two arguments, an accumulator and a single value, a list and optionally a starting accumulator value and returns the result.
result = reduce(lambda acc, x: acc + x, xs)
print result
result = reduce(lambda acc, x: acc + x, xs, 100)
print result
result = reduce(lambda acc, x: acc + x, map(process, filter(lambda x: x % 2 == 0, xs)))
print result
The first execution over the values of xs is essentialy 1 + 2 = 3, 3 + 3 = 6, 6 + 4 = 10. The second execution starts with 100 and goes 100 + 1 = 101, 101 + 2 = 103, 103 + 3 = 106, 106 + 4 = 110. The final execution goes 4 + 16 = 20.
Exercise
Write map as my_map and filter as my_filter using reduce
Recursion is often a major part of functional programming. Unfortunately, it is not particularly emphasized in most OOP languages and so the runtimes for those languages often have limited support for recursion or are unable to optimize recursive calls. What is recursion?
Recursion is when a function calls itself. This seems kind of daft. Why would a function call itself? It turns out that recursion is often a natural way of expressing certain kinds of computations especially computations that can be broken down into a sort of "perform some work and combine with previous work" approach.
Let's look at an example. The function map takes a List and a function and applies the function to each element of the List, creating a new List in the process.
We'll start with an iterative version:
def my_iterative_map(f, xs):
result = []
for x in xs:
result.append(f( x))
return result
def times10(x):
return x * 10
print my_iterative_map(times10, [1, 2, 3, 4, 5])
Easy enough. What would a recursive version look like?
In Python, function overloading is not permitted (you cannot write functions with the same name but differ only in terms of numbers of arguments). Because of this, our actual recursive function will be defined and used inside the function called by the programmer:
def my_recursive_map(f, xs):
def recursive_map(acc, remainder):
if len(remainder) == 0:
return acc
acc.append(f(remainder[0])) # append does not return the caller.
return recursive_map(acc, remainder[1:])
return recursive_map([], xs)
print my_recursive_map(times10, [1, 2, 3, 4, 5])
A recursive implementation is very much similar to an inductive proof. There is a base case...when there is no more work to be done and an inductive step when one step in the calculate is performed. Note that because the recursive_map function is defined inside the my_recursive_map function, the former is a closure over the value of f which need not be an argument to recursive_map.
There are a number of ways in which recursion is a bit clumsier in Python:
In many actual functional programming languages, the implementation would look something closer to this:
def my_recursive_map(f, xs):
return my_recursive_map(f, xs, [])
def my_recursive_map(f, xs, acc):
if len( xs) == 0:
return acc
return my_recursive_map(f, xs[1:], acc.append(f(xs[0]))
Recursion is a whole 'nother topic as they say. Any recursive algorithm can be re-written as an iterative algorithm and vice versa. Additionally, many such algorithms already conform to some well-known pattern such as map, reduce or filter so you are well advised to use one of those.
However, that might not always be the case and there are some AI algorithms are are best and naturally written as either recursive or co-recursive functions (f calls g which calls f...etc). These include alpha-beta prunining in Adversarial Search as well as Decision Tree induction.
Therefore you should at least be aware that Python has a recursion depth limit of 1000 by default. If we tried to run the my_recursive_map on a list that was more than 1000 elements long, we would get an exception. This can be fixed with the following code:
import sys
sys.setrecursionlimit(1500)
or to whatever limit you require. You should not set it to be more than you need, however.
Whether you choose to use map, filter, reduce or List Comprehensions plus reduce is up to you. For myself, I tend to use map, filter and reduce to keep things consistent but there's no denying that List Comprehensions are prettier.
You should never use recursion first but try to see if your calculation fits some existing transformational pattern. Then check to see if an iterative version is simpler. Finally, you may need to create a recursive version (although this is just advice for Python in a Functional Style...recursion is often easier than iteration in functional programming languages).
Functional programming languages typically have a whole host of other higher order functions for operating on Lists. Some of them are irrelevant in Python. For example, first is just xs[ 0] and rest is just xs[1:]. last is xs[-1] and butlast is xs[0:-1], take n is xs[0:n], drop n is xs[n:]:
xs = [1, 2, 3, 4]
print "first( xs) =", xs[0]
print "rest( xs) =", xs[1:]
print "last( xs) =", xs[ -1]
print "butlast( xs) =", xs[0:-1]
print "take( 2, xs) =", xs[0:2]
print "drop( 2, xs) =", xs[2:]
There's no doubt that the following is a bit ugly:
result = reduce(lambda acc, x: acc + x, map(process, filter(lambda x: x % 2 == 0, xs)))
One solution is to break it apart:
filtered_xs = filter(lambda x: x % 2 == 0, xs)
mapped_xs = map(process, filtered_xs)
result = reduce(lambda acc, x: acc + x, mapped_xs)
It's not always easy to come up with semantically meaningful names for the intermediate products of a computation, though. Actual function programming languages have a sense of function composition and in languages like Clojure, a threading macro (operator):
(->> xs
(filter even?)
(map process)
(reduce +))
a macro re-writes code before execution. The result of the above macro is the code:
(reduce + (map process (filter even? xs)))
We can actually make our own code somewhat better with some named functions:
def add( a, b):
return a + b
def even( a):
return a % 2 == 0
result = reduce(add, map(process, filter(even, xs)))
which shows that the inline, anonymous functions were creating some of the "noise". As it turns out, you can get a lot of functions like add from the operator module, Operators As Functions.
However, this isn't nearly as general as what's available in actual programming languages. One way to obtain this generality is to realize that 1. functions are values, 2. values can be put into Lists, and 3. reduce can be used to walk over a List:
def compose(fs):
return lambda start: reduce( lambda x, f: f( x), fs, start)
We can use compose to create a function that takes a value and adds 2 to it, then multiplies it by 10 and finally subtracts 5:
g = compose([lambda x: x + 2, lambda x: x * 10, lambda x: x - 5])
print g( 10)
print g( 2)
The downside to such an arrangement is that you can only compose functions that take a single argument. There are number of ways around this. First, using a dataflow approach, that single argument can be a Dict. We'll see an example later where this might work. Second, Python does have some functional programming tools like partial that creates a "partial" function.
A partial function is one where some of the arguments have already been supplied. It's kind of like providing default values but you do it on the "outside" of the function. Here's an example:
from functools import partial
from operator import add, sub, mul
add2 = partial( add, 2)
print add2( 10)
print add2( 20)
print add2( 2)
The downside to such an approach is that you have to supply the values in order. That is, if a function takes 5 arguments, you must supply either the first, first and second, first and second and third, etc. You cannot supply the first and fifth. In order to accomplish that, you need to create a function directly or indirectly:
def addmul(a, b, c):
return (a + b) * c
add3mul4 = lambda x: addmul(2, x, 4)
print add3mul4(10)
Actually creating addmul only makes sense if you're going to use it over and over again. You could just use a lambda otherwise.
We're now in a position to actually solve a problem using Python in a functional style. The main tenets are:
We're going to start with a simple example that neatly expresses the differences between an imperative and declarative program. This example is taking from A practical introduction to functional programming. It involves racing cars. I have made a few modifications to the declarative version to make it more functional.
Basically, each car is a - and there are three of them. At each time step, we randomly move the cars. The car that goes the furthest in 5 time steps is the winner. The program below is imperative, it describes "how". It includes comments to indicate the semantics of various parts of the code:
from random import random
time = 5
car_positions = [1, 1, 1]
while time:
# decrease time
time -= 1
print ''
print 't=', 5 - time
for i in range(len(car_positions)):
# move car
if random() > 0.3:
car_positions[i] += 1
# draw car
print '-' * car_positions[i]
Below we have a declarative version of the same program:
def move_cars():
for i, _ in enumerate(car_positions):
if random() > 0.3:
car_positions[i] += 1
def draw_car(car_position):
print '-' * car_position
def run_step_of_race(time):
time -= 1
move_cars()
return time
def draw(time):
print ''
print "t=", 5 - time
for car_position in car_positions:
draw_car(car_position)
time = 5
car_positions = [1, 1, 1]
while time:
time = run_step_of_race(time)
draw(time)
We can see a few differences here. We created small functions with semantic meanings that did one job. This is the "DSL" for racing cars. The program is built by arranging these functions, essentially solving the problem in terms of the DSL.
We're going to expand on this idea by solving a problem from Programming Challenge. I much prefer the Programming Challenges problems to the pure mathematics problems often found for learning programming because the challenges often bear some resemblance to real life problems whereas the mathematical problems often require some domain knowledge (about primes, for example) and, to me at least, feel artificial.
The problem we will attempt to solve is Challenge 119 - Greedy Gift Givers.
We have a group of friends that engage in gift giving. Each friend has closer friends within the group that they give gifts to and they set aside an amount for gift giving. Each recipient receives a gift of equal value and the gift is an integer value. Any remaining funds are considered as a "self gift" in the calculation.
This program, somewhat cynically, calculates the net gifting of each person in the group of friends. The input is as follows:
5
dave laura owen vick amr
dave 200 3 laura owen vick
owen 500 1 dave
amr 150 2 vick owen
laura 0 2 amr vick
vick 0 0which encodes:
and the correct output for this input is:
amr -150
dave 304
laura 66
owen -359
vick 141I leave it for you to decide who made out in this arrangement.
There are a lot of ways to skin this beast and our solution is probably going to be a bit over-architected in order to demonstrate a few concepts in functional programming and dataflows.
In his presentation on Naming, Zach Tellman notes that there are generally speaking only three operations:
And that except for top level functions that need to combine these operations, functions should only ever do, ideally, one of these three operations.
Following this guidelines, we can break the problem into three basic functions:
read_input() - impure function that reads the string and translates/parses it into a data structure of some kind.calculate_net_gifts() - a pure function that reads the data structure from above and outputs a new data structure with net gifting (or the same data structure with net gifting amounts).write_output() - impure function that writes the net gifting amounts based on the data structure of net gifting.We can write and test these functions individually and then compose them into a solve_problem function that the end.
The main thing we want to decide now is what the schema of our data looks like and how we go from the raw data to data in the proper schema and from data in the proper schema into the expected output.
The schema I've thought of looks like this:
{"dave": {"fund": 200, "recipients": ["laura", "owen", "vick"]},
"owen": {"fund": 500, "recipients": ["dave"]},
"amr": {"fund": 150, "recipients": ["vick", "owen"]},
"laura": {"fund": 0, "recipients": ["amr", "vick"]},
"vick": {"fund": 0, "recipients": []}}
So this is the data that calculate_net_gifts will start with and it's also the data that we want read_input to to generate from the raw data.
When we're done, the data structure will be:
{"dave": {"fund": 200, "recipients": ["laura", "owen", "vick"], "gift": 66, "given": 198, "received": 502, "net": 304},
"owen": {"fund": 500, "recipients": ["dave"], "gift": 500, "given": 500, "received": 141, "net": -359},
"amr": {"fund": 150, "recipients": ["vick", "owen"], "gift": 75, "given": 150, "received": 0, "net": -150},
"laura": {"fund": 0, "recipients": ["amr", "vick"], "gift": 0, "given": 0, "received": 66, "net": 66},
"vick": {"fund": 0, "recipients": [], "gift": 0, "given": 0, "received": 141, "net": 141}}
that is, we want calculate_net_gifts to enrich the original data structure. We will break this down into steps so that we can test them, one by one, along the way. The steps should/could be:
Finally, the write_output function will take the final state of the data structure and write the expected output.
We're going to write calculate_net_gifts first. This allows us to work with our chosen data schema and determine if there are any problems and changing it as necessary. We can also avoid IO in testing for the time being.
We can assume that we already have the initial data structure. We want to write the first step which adds "gift", "given" and "received" to each individual map. If we had such a function then we could simply call it on the value of each key in the outer data Dict. Let's say it's called calculate_gifts.
The question becomes, how do we apply it to each value in data? This is sort of like map but it's not being applied to a List but a Dict and more specifically the values of the Dict (we could imagine a map that is applied to the keys of Dict as well).
This is where familiarity with the basic Python language is helpful. We can:
dict( xs).items().We can define dmap as follows:
def dmap(f, m):
return dict( map( lambda (k, v): (k, f( v)), m.items()))
dmap(partial( add, 1), {"a": 1, "b": 2})
And this is where we get to "programming by wishful thinking", we simply apply dmap to a function we wish we had:
def calculate_all_gifts( data):
return dmap( calculate_gifts, data)
One of the problems with an interpreted language like Python, however, is that we need to define functions in a particular order. Specifically, we must define functions before they are called. This makes this top/down approach a bit difficult in Python although you might use it when doing some initial pen and paper sketching.
The alternative is to recognize we needed the calculate_gifts function and start there instead. This is the bottom/up approach. In either case, we are working declaratively...we are creating units of code that express what to do.
That function will take a person's Dict and calculate an integer gift value, the total amount given away and the remainder as the initial value for received:
def calculate_gifts(person_data):
recipient_count = len(person_data["recipients"])
person_data["gift"] = 0 if recipient_count == 0 else person_data["fund"] // recipient_count # // is floor division
person_data["given"] = person_data["gift"] * recipient_count
person_data["received"] = person_data["fund"] - person_data["given"]
return person_data
We can easily test this bit of code (more generally you'd use a legit Python test framework like nose):
print calculate_gifts({"fund": 200, "recipients": ["laura", "owen", "vick"]})
This indeed looks like what we expect the result to be. Now we can move to calculate_all_gifts:
def calculate_all_gifts(data):
return dmap(calculate_gifts, data)
print calculate_all_gifts({"dave": {"fund": 200, "recipients": ["laura", "owen", "vick"]},
"owen": {"fund": 500, "recipients": ["dave"]},
"amr": {"fund": 150, "recipients": ["vick", "owen"]},
"laura": {"fund": 0, "recipients": ["amr", "vick"]},
"vick": {"fund": 0, "recipients": []}})
That looks good so we can move on to the next step which is to distribute the gifts. This is a bit more complicated. We want to have a single person's gifting and apply it to the correct people in the overall data. With a nested data structure like we have, we're going to have to take it apart to modify the "received" value.
Because Python has mutable data structures, we can use a for loop to modify the Dicts instead of map because modification of a data structure in-place is an impure action. We'll talk a bit about this later.
def distribute_gifts(data, person):
for recipient in person["recipients"]:
data[recipient]["received"] = data[recipient]["received"] + person[ "gift"]
return data
Note that in order to test our function we now need the result of the previous function:
result = calculate_all_gifts({"dave": {"fund": 200, "recipients": ["laura", "owen", "vick"]},
"owen": {"fund": 500, "recipients": ["dave"]},
"amr": {"fund": 150, "recipients": ["vick", "owen"]},
"laura": {"fund": 0, "recipients": ["amr", "vick"]},
"vick": {"fund": 0, "recipients": []}})
result = distribute_gifts(result, result["dave"])
for recipient in result["dave"]["recipients"]:
print recipient, result[ recipient]
Based on what we saw before, this looks right. We now need to apply everyone's gift giving:
def distribute_all_gifts(data):
return reduce(distribute_gifts, data.values(), data)
The function above is kind of sneaky because I actually re-wrote distribute_gifts to make it work. Originally, distribute_gifts took the person's data and the overall data as arguments but I switched them so that the overall data could act as an accumulator of changes and the reduce simply applied the information contained in each individual's gift data to everyone else.
It's sneaky in a second way in that it uses values() on the overall data map because we don't care who is doing the gift giving...all the information we need is contained in the person's gift data.
Finally, we use the overall data as the starting value.
One downside to functional programming can be "higher order diarrhea" where you use such abstract abstractions that three weeks later you can't understand what your code is doing. Where possible it is sometimes better not to chain a bunch of cleverness together and instead give names to intermediate computations.
result = calculate_all_gifts({"dave": {"fund": 200, "recipients": ["laura", "owen", "vick"]},
"owen": {"fund": 500, "recipients": ["dave"]},
"amr": {"fund": 150, "recipients": ["vick", "owen"]},
"laura": {"fund": 0, "recipients": ["amr", "vick"]},
"vick": {"fund": 0, "recipients": []}})
result = distribute_all_gifts(result)
for k in result.keys():
print k, result[ k]
All that remains now is to calculate the net gifting, assuming we had a calculate_net_gifting function, calculate_all_net_gifting is just a dmap of that function. Simplicity itself:
def calculate_net_gifting(person):
person["net"] = person["received"] - person["given"]
return person
def calculate_all_net_gifting(data):
return dmap( calculate_net_gifting, data)
result = calculate_all_gifts({"dave": {"fund": 200, "recipients": ["laura", "owen", "vick"]},
"owen": {"fund": 500, "recipients": ["dave"]},
"amr": {"fund": 150, "recipients": ["vick", "owen"]},
"laura": {"fund": 0, "recipients": ["amr", "vick"]},
"vick": {"fund": 0, "recipients": []}})
result = distribute_all_gifts(result)
result = calculate_all_net_gifting(result)
for k in result.keys():
print k, result[ k]
We can confirm that the values of "net" match those we expect in the output. What remains now is to tie these all together. We could just stick what we have above in a function. It is at this point that we can really see that we are using a Domain Specific Language (DSL) in a declarative way.
def calculate_net_gifts(data):
result = calculate_all_gifts( data)
result = distribute_all_gifts( result)
result = calculate_all_net_gifting( result)
return result
result = calculate_net_gifts({"dave": {"fund": 200, "recipients": ["laura", "owen", "vick"]},
"owen": {"fund": 500, "recipients": ["dave"]},
"amr": {"fund": 150, "recipients": ["vick", "owen"]},
"laura": {"fund": 0, "recipients": ["amr", "vick"]},
"vick": {"fund": 0, "recipients": []}})
for k in result.keys():
print k, result[k]
Although that's a wee bit verbose given we wrote a function to do exactly what was done:
calculate_net_gifts = compose([calculate_all_gifts, distribute_all_gifts, calculate_all_net_gifting])
result = calculate_net_gifts({"dave": {"fund": 200, "recipients": ["laura", "owen", "vick"]},
"owen": {"fund": 500, "recipients": ["dave"]},
"amr": {"fund": 150, "recipients": ["vick", "owen"]},
"laura": {"fund": 0, "recipients": ["amr", "vick"]},
"vick": {"fund": 0, "recipients": []}})
for k in result.keys():
print k, result[k]
Sometimes the more verbose way is easier to debug.
Now we can write a display function, write_output:
def write_output(data):
keys = data.keys()
keys.sort()
for k in keys:
print "%s %d" % (k, data[ k][ "net"])
result = calculate_net_gifts({"dave": {"fund": 200, "recipients": ["laura", "owen", "vick"]},
"owen": {"fund": 500, "recipients": ["dave"]},
"amr": {"fund": 150, "recipients": ["vick", "owen"]},
"laura": {"fund": 0, "recipients": ["amr", "vick"]},
"vick": {"fund": 0, "recipients": []}})
write_output(result)
This is exactly what we wanted.
By cleanly separating our pure and impure functions (except for a bit of mutability we can't avoid in Python), we can easily change what we want to print out if the need arises or where it goes (maybe it goes into a database) or a snarky email get sent at the end of the year.
All without changing the actual computation.
Our penultimate step involves reading the raw data and creating the initial data structure. Let's review the incoming raw data:
5
dave laura owen vick amr
dave 200 3 laura owen vick
owen 500 1 dave
amr 150 2 vick owen
laura 0 2 amr vick
vick 0 0There really isn't a compelling reason to use the first two lines in Python. Perhaps there is in C or Java. We don't need the number of recipients either. Basically we just need to take:
dave 200 3 laura owen vickand turn it into:
("dave" {"fund": 200, "recipients": ["laura", "owen", "vick"]})This is going to require some string parsing. You should review the Python documentation on Strings and Regular Expressions but we can use split. In the code below, we use the convention of naming "magic constants" using ALLCAPS.
NAME = 0
FUND = 1
RECIPIENT_START = 3
def read_person_data(raw_person_data):
parsed_person_data = raw_person_data.split(" ")
name = parsed_person_data[NAME]
fund = int( parsed_person_data[FUND])
recipients = parsed_person_data[RECIPIENT_START:]
return (name, {"fund": fund, "recipients": recipients})
print read_person_data("dave 200 3 laura owen vick")
print read_person_data("laura 0 2 amr vick")
print read_person_data("vick 0 0")
That works very nicely. I used named constants and intermediate values to add semantic meaning to what I was doing. We need to apply it to all the lines of data:
def read_input(raw_data):
lines = raw_data.split("\n")
parsed_data = map(read_person_data, lines[ 2:])
return dict(parsed_data)
# """ is used for multiline strings in Python
raw_data = """5
dave laura owen vick amr
dave 200 3 laura owen vick
owen 500 1 dave
amr 150 2 vick owen
laura 0 2 amr vick
vick 0 0"""
print read_input(raw_data)
Now we're mostly done. We just need to create the outer function, solve:
def solve(raw_data):
data = read_input(raw_data)
result = calculate_net_gifts(data)
write_output(result)
raw_data = """5
dave laura owen vick amr
dave 200 3 laura owen vick
owen 500 1 dave
amr 150 2 vick owen
laura 0 2 amr vick
vick 0 0"""
solve(raw_data)
Let's do it with data we haven't seen before:
raw_data = """3
liz steve dave
liz 30 1 steve
steve 55 2 liz dave
dave 0 2 steve liz"""
solve(raw_data)
As I mentioned at the start, this program was a bit more verbose than it needed to be because I wanted to show you the steps of a data flow program. The "interior" pure function part had three steps that were composed. Exactly where you draw the line depends on how complicated the computation is. You almost certainly want to stop at any point there is something testable. Of course, you can always break things out later if you find you didn't pick the right granularity.
Of course, it's not enough to know about the functional programming part to program in Python in general. You should probably at least be familiar with:
You might also notice that to program in a functional style in Python sometimes requires a bit of a wild west frontier attitude where you often have to write your own abstractions that would be provided in a true functional language. It turns out that some nice people have done that for you.
One such library is toolz that provides a number of typical functional programming abstractions for doing functional programming in Python.
If you want to be a real diehard functional programmer, you may want to consider immutable data structures. pyrsistent provides a library of immutable data structures for use in Python. pyrthon makes the literals use the pyrsistent immutable data structures.
If you want to go absolutely hog wild, you can also use Hy which is a language that uses Lisp syntax but compiles to the Python Abstract Syntax Tree (AST). Basically, it's just an alternative way to to write a Python program--as Lisp s-expressions. However, when used in conjuction with the other libraries, it gives you a powerful functional programming language that includes macros.
Using all four would be some seriously hardcore functional programming Python. For this class, we will restrict ourselves only to those conventions and approaches outlined in this document. Using Hy, for example, is not permitted.
If you are reading this before the semester begins, you might try out "Python in a Functional Style" on some additional Programming Challenges. Try 101 especially without using explicit indexing.