Functional Programming Concepts for the Lay Programmer – Part 1

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.

List Comprehensions

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.”

Monads

As one answer on StackOverflow put it, “Monads are simply a way [of] wrapping things and provid[ing] methods to do operations on the wrapped stuff without unwrapping it.” It’s a clear definition… but its doesn’t really give you that “Aha!” moment I was looking for. If you have any experience at all with Javascript, the explanations and examples in jQuery is a Monad should do just that. In short, Monads are useful for changing the set of verbs and how they behave.

The final realization of how useful they can be (and my first recognition of how nifty it can get when you mix functional and imperative styles in a compatible language came from another StackOverflow answer (same question) which showed how, in F#, you can use a monad to do Javascript-style asynchronous HTTP I/O without having to explicitly write callbacks.

Lazy Evaluation

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.

Haskell

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):

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.

Creative Commons License
This work, unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.

This entry was posted in Geek Stuff. Bookmark the permalink.

One Response to Functional Programming Concepts for the Lay Programmer – Part 1

  1. Pingback: Functional Programming Concepts for the Lay Programmer – Part 2 | Stephan Sokolow's Blog

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

By submitting a comment here you grant this site a perpetual license to reproduce your words and name/web site in attribution under the same terms as the associated post.