Update: Part 2 is finally available.
Despite the growing interest in functional programming, most people (myself included) seem to have a lot of trouble grasping the core concepts and constructs. (Probably because the early adopters are all, to some extent, math geeks who have never needed to practice explaining things to the lay-person.) Since I finally decided to sit down and figure these things out, I thought it only fair that I share the Google results that led me to my various epiphanies.
Note: The closest I’ve come to actual functional programming languages is adopting parts of the functional style in Python. If my terminology is a little off but I got the gist of the thing, be diplomatic in your complaints. (I’ve had too much experience with math teachers who seem to think that it’s pointless to know how to use math without perfectly comprehending the relevant proofs and being able to write your own.)
The Easy Stuff
First, let’s cover a few things which are generally easy to understand… but only if you’ve heard of them:
- Higher-order Function
- A function which takes another function as an argument. To make this more comfortable, many languages treat functions and data equally. (In object-oriented languages, this is “everything is an object” taken to its logical conclusion). This allows for things like
results = filter(arbitrary_test, input_data). This is an especially useful feature when combined with other features like closures. (explained later)
- Pure Function
- A function that only uses its arguments as input, doesn’t modify variables visible outside itself, and provides all of its output using the language’s “return” statement (or equivalent). In other words, a function with no hidden inputs or side-effects. Pure functions are a Good Thing™ because you know that, with a given set of arguments, they’ll always do the same thing. This helps immensely with testing and debugging. (and makes unit testing much easier and more reliable)
- Tail Recursion
- Getting loop-like behaviour by having functions re-call themselves as the last thing they do. People consider this a good thing because it lets you write loops in a purely functional fashion. (see previous explanation) Functional languages generally optimize this internally so you still get the speed and stack-avoidance of a loop.
Practically speaking, a list comprehension is just a shorthand for saying “Take the elements from list X that satisfy condition Y and perform operation Z on them, then return a list of the results”. The benefit of list comprehensions is that they’re a quick, easy, concise alternative to declaring an empty list and then wrapping a function in a for loop and an if statement. (Technically speaking, they let you build one list from another using set builder notation.)
For example, In Python, you could get the squares of all positive numbers in a list with
new_list = [x**2 for x in old_list if x > 0]. Keep in mind, however, that list comprehensions aren’t limited to working with numbers. I often use one to quickly implement a simple, one-line input normalizer that, in plain English, would be “Take all lines which aren’t empty or beginning with # and strip leading and trailing whitespace.”
When a programming language is given a statement or block of statements, there are various ways it can do things, ranging from fully strict evaluation to fully lazy evaluation. These are usually easier to explain with examples.
The most common subset of lazy evaluation is probably short-circuit evaluation. This means that, if I run something like
fileContent = getFromCache(url) or getFromWeb(url) in Python and getFromCache returns something other than None, an empty string, or the like, getFromWeb will never run because “True or anything” will always be true, so why bother evaulating the second half? This can be confusing if you don’t expect it, but as my example shows, it can also be very useful.
As you probably guessed, strict evaluation operates on the premise that “they said to run it, so we run it… whether or not we’re throwing away the output”. Naturally, in every language, if/then/else constructs use lazy evaluation.
The area of lazy evaluation that is sometimes confusing is eager evaluation versus delayed evaluation. If you’re still reading this, you’re almost certainly familiar with eager evaluation. For example, if you look at a list, you might see something like
[1, 2, 3, 4, 5, 6].
The gist of delayed evaluation is that, at any given time, that list could look more like
[1, 2, 3, ...] with the language evaluating further into the “
...” as needed. This is useful because you can do things like creating an infinite list (Wikipedia uses the Fibonacci sequence as an example) and then retrieving specific values from it.
On a more mundane note, lazy evaluation is also commonly used for improving program performance. For example, in graphical systems where drawing is done only at the last minute so that “Oops. Looks like those pixels aren’t visible to the user after all” doesn’t impair performance.
I haven’t actually used Haskell yet, but from what I’ve seen, I think I’ll try to make time for it soon. (When I do, I’ll update this post) Here are the posts that brought me to that conclusion (In concert with what I’ve already linked, of course):
- Why Haskell is Beyond Ready for Prime Time (This is the more convincing one in my opinion)
- 37 Reasons to Love Haskell
Among other things, I love the idea of a code repository where you can search for functions by specifying the inputs and return types you need.