Software Development

Understanding function composition and partial application

Independent consultant and developer Chip Camden uses practical examples to explain two principles of Functional Programming.

Let's say that we have a list (or array) of temperatures in Celsius, and we want to create a new list containing the same temperatures expressed in Fahrenheit. In most imperative programming languages, this kind of operation calls for a loop. For instance, in C# you might do something like this:


List<float> ctemps = new List<float>() {37, -5, 0, 48};

List<float> ftemps = new List<float>();

foreach (float temp in ctemps)

{

ftemps.Add((float)(temp * 1.8 + 32));

}

Languages that support a Functional Programming style provide a higher-order function, usually called "map," that returns a new list generated by mapping a function to each of the elements of an existing list. Thus, for example, in Ruby we could rewrite the above as:


ctemps = [37, -5, 0, 48]

ftemps = ctemps.map {|temp| temp * 1.8 + 32}

The map function requires two parameters: the list on which to operate (ctemps in the above example) and the function to map over each of its elements (the code block in braces above). This arrangement is more obvious in a pure functional language like Haskell:


let ctemps = [37.0, -5, 0, 48]

in map (\ x -> x * 1.8 + 32) ctemps

The expression in parentheses is a lambda, which corresponds to the code block given in the Ruby example. The backslash stands for the Greek character lambda (λ), and x is the assigned name for its parameter. We could have passed a named function instead of the lambda; the only reason why we used a lambda is because we don't have a named function that multiplies its parameter by 1.8 and then adds 32. We could write one:


let ctemps = [37.0, -5, 0, 48]

toF x = x * 1.8 + 32

in map toF ctemps

But in pure functional languages every operation is a function, including multiplication and addition. All the toF function is really doing is combining these functions, along with some specific parameters, into one function. The rest of this post will explain that statement.

Partial function application

As I mentioned, in Haskell multiplication is a function, like everything else; it takes two numeric arguments and returns their product. But in Haskell, no function really has more than one parameter.

Those readers who are unfamiliar with Functional Programming are now trying to discern the sound of one hand clapping.

All functions in Haskell are curried, which means that when you call a function that takes two parameters, what that function returns is another function that takes the other parameter. For example, let's say I have the following function:


mymult :: Int -> Int -> Int

mymult x y = x * y

This little function is a simplified version of multiplication, but it will serve to illustrate the point. The first line is our type signature; it says that this function takes an Int (integer) argument and returns a function that takes an Int argument and returns an Int. If we invoke it:


mymult 2 3

The expression mymult 2 returns a function that then takes 3 as an argument to invoke the rule that we've established. Why is this important? Because we can break that apart:


let mymult2 = mymult 2

in map mymult2 somelist

The map function expects as a parameter a function that takes only one parameter. Since mymult takes two parameters, we can partially apply it by supplying one of the arguments in order to create a function that we can pass to map. We don't even need to name it:


map (mymult 2) somelist

Better yet, we can ditch our custom function and just partially apply the multiplication operator:


map (2*) somelist

Now, why did I put the '*' after the 2? In Haskell, functions that are named with special symbols are infix by default. Haskell has a syntax for calling them in prefix fashion, as well as for calling prefix functions with infix notation, but we don't need to explore that here. Since multiplication is commutative, I could have said:


map (*2) somelist

If the operation were division or subtraction, though, then the order would matter.

Function composition

How does this help our little toF function? We've seen how we can pass a partially-applied binary operation to map, but in our case we need two operations: multiplication by 1.8 and addition of 32. We want to take the output of the first operation, and pipe it to the second one to get our result.

Well, that's what the "function composition" operator (.) is for. Joining two functions with a "." creates a new function that first invokes the right-hand function, then passes its result to the left-hand function. Thus, we can eliminate our toF function altogether:


let ctemps = [37.0, -5, 0, 48]

in map ((+32) . (*1.8)) ctemps

We can also compose two other functions, show (convert to String) and putStrLn (output to the terminal), to see our result:


main = do

putStrLn . show $

let ctemps = [37.0, -5, 0, 48]

in map ((+32) . (*1.8)) ctemps

We could have written that as putStrLn(show(...)). That's effectively the same thing, because we're evaluating it right away. In the case of map, though, as with all higher-order functions, we're building a pipeline that will be applied to values to be supplied at a later point. In that case, direct application of the result of the first function won't work:


map ((+32) (*1.8)) ctemps

That's wrong, because (*1.8) returns a function, and (+32) is expecting a number. You have to use function composition to get this to work.

Conclusion

If you've never been exposed to Functional Programming before, you may be experiencing a bit of vertigo, nausea, and numbness in the extremities that's a normal part of learning Haskell. There will be more, if you continue. But hopefully these disorienting episodes will lead to moments of enlightenment that will not only enable you to become proficient in Functional Programming, but will also make you a better programmer in any language.

About

Chip Camden has been programming since 1978, and he's still not done. An independent consultant since 1991, Chip specializes in software development tools, languages, and migration to new technology. Besides writing for TechRepublic's IT Consultant b...

17 comments
aikimark
aikimark

Chip Shouldn't that earlier example have been: [code] let ftemps = [37.0, -5, 0, 48] in map (\ x -> x * 1.8 + 32) ctemps [/code]

Mark Miller
Mark Miller

Your example of the for-loop and comparing it to how you'd do the same thing in Haskell brought to mind the concept of FP that was the most difficult for me to understand when I was first learning it in college: How to iterate and change state without using a loop structure. Maybe I'm getting ahead of you with this, and you're going to write about it at some point. You kind of gloss over it with your use of "map", but I understand that you are focusing on function composition here. The biggest roadblock I had to get past, and I imagine a lot of programmers will have this same one if they encounter FP, was reconciling what is a statement in an imperative language to what is a function in a functional language. In imperative languages you have functions, but they're incidental to the program's flow. A call happens, and then it returns, and your program goes to the next statement, which is usually below the one just executed. Along the way it may have changed some global state that changes the way the rest of the program behaves (though this is considered a bad practice). This is not how it typically works in FP (at least not without a macro wrapper around the linear code). Another big conceptual hurdle to get past is that in FP there isn't really a "program counter." There's just a function evaluator that operates recursively. This is a big difference. In imperative languages, program flow progresses automatically, one statement to the next. In FP you're generally expected to determine program flow yourself, though there is a general flow to how the function evaluator works. Anyway, back to loops. The obvious answer to the quandary of how to re-execute some code, and change state, without a loop structure is to use recursion, but the general way programmers are taught recursion is from the standpoint of an imperative language, where there is always the option to change state by changing the value of a variable. In a pure FP environment, variables are immutable. At least for me, this threw a huge monkey wrench in my conception of how I could use loops to accomplish a task. The thing to understand is that in pure FP, you call a function to change state. You don't change a variable's value. One might be tempted to think that in this scheme you call a function to change state, the function returns immediately, and the program moves on to something else. This is not how it works. What generally happens is you call a function the way an imperative language goes to the next line of code in a linearly written program. Though the way functions are executed takes some getting used to, this is how you move forward and "do something else." You return from a function when a process/subprocess ends, but the next thing executed after that...is another function. Subprocesses can seem like they're written kind of "backwards," like so: (do-last (do-third (do-second (do-first)))) Even though in reality the above expression would be evaluated from left to right, it executes from right to left, because typically (depending on the evaluation scheme used in the language), all of a function's arguments are evaluated before the enclosing function is executed. An exception would be if you enclosed a function in a lambda somewhere in there, in which case the lambda will not be executed right away, unless the programmer has written it to be executed on the spot.

seanferd
seanferd

For me, the examples really don't produce more disorientation than any other code examples, though. I found this to be rather clearly explained, in fact. The vertigo, well, VEBKAC in my case.

Sterling chip Camden
Sterling chip Camden

The Haskell "print" function could be used in place of "putStrLn . show", but I wanted to illustrate functional composition using non-symbolic functions.

Sterling chip Camden
Sterling chip Camden

The "let" is just setting up the list of Celsius temperatures that are then mapped in the "in" clause. If I wanted it assigned to ftemps, I could have included a let ftemps = around that, but then that would also need an "in" clause with some code that uses ftemps.

Sterling chip Camden
Sterling chip Camden

... that at bottom, most computers are essentially imperative with state modifications. Those of us who have worked in assembly languages tend to think in those terms, and knowing that the stateless functional/declarative abstraction is built on top of that, we keep on trying to see through the abstraction to what it's "really doing."

Sterling chip Camden
Sterling chip Camden

I think functional programming might be easier to understand for someone who doesn't have a long history with imperative programming. With more than 30 years in the latter, I found the former rather a shock at first -- although it elucidates and confirms some suspicions about programming that I've had for a very long time.

Mark Miller
Mark Miller

I heard a CS professor commiserate about this once. He taught a course that used Python, but his students only considered C++ and Java to be "real" languages. He said as he went through the course his students kept asking him, "What's really going on (underneath)?" Underneath what? Python. I don't know if this is true or not, but the students may have only known C++ or Java coming in, and they only understood computing in those terms. They were probably trying to reconcile what Python was doing to what (I guess) C was doing. This is just my own theory, but they probably felt uncomfortable with the approach the professor was taking, because they were used to the idea that they had to understand the internal model of the machine they were working with to really understand what was going on. They had internalized the idea that you couldn't take a language at face value. The different parts of the language were just a representational notation (perhaps not too accurate) for processes going on under the covers. Like in C/C++, when you use "i++", what's really going on there? It'll work the way we all expect in the typical use of it in a loop (just to increment the variable), but once you combine it with other numeric factors, all bets are off. You can have certain notions of it, which are valid, but the way the compiler interprets that expression may not match your notions. So for the students (just my guess), there was a deep ingrained belief that there had to be a deep focus on the language, and what was going on with its runtime, or the way it interpreted something internally. They were missing a focus on the ideas that the professor was trying to get them to model. This is really inculcated by the industry, from my experience. The way in which this damages real notions of computing is that it causes people to lose the forest for the trees. From a scientific perspective, the machine and the language are just a means for modeling an idea. So there's no cognitive dissonance in using one language or another (though some languages are not that great to work with, because they're badly designed). As long as they're a good medium for modeling the idea, what does one care what's going on under the covers? This was the disconnect between the professor and his students. He was trying to teach computing from a scientific perspective. His students were trying to learn it from an engineering perspective. So much of what's called CS now is actually focused on engineering issues, which is focused on materials and structure to build something that solves a problem (hopefully in an elegant way) in a way that's robust. And of course that's what the industry is focused on as well (though the idea of elegance is often lost altogether). Science, in short, is about modeling phenomena and then seeing relationships between models. It's about discovery. The engineering perspective is important, but good science is needed to back it up, so that engineering methods can improve. To your point, yes, we definitely need the development of other computer architectures. Even though it's now highly optimized, we're still using a version of the machine architecture von Neumann invented in the 1940s, and the reason he designed it the way he did was because the materials they had were too slow for anything better. There was at one time, as I'm sure you're aware, two different companies that made machines that executed Lisp at the hardware level (Lisp Machines, Inc, and Symbolics). Other companies made Lisp machines for a time. I remember seeing an old ad for one made by Texas Instruments. So other machine architectures have been made in the last 30 years. What I heard killed off LMI and Symbolics was that once they developed their machine architecture these companies sat on their laurels. The more traditional computer architecture surpassed them in performance eventually, because they optimized it.

Charles Bundy
Charles Bundy

We're still using Von Neumann architecture... I swear FP ties me in knots! Your article on the other hand did not (knots that is..) great read!

Mark Miller
Mark Miller

I remember Dijkstra said that students who had Basic as their first language were irretrievably brain damaged. I think that was too pessimistic. I agree that it's better to not start with imperative programming, though programming educators might disagree. I know a lady who started programming in Scheme as her first language, and she seems to have taken to it like a duck to water. Her husband, who is a pretty advanced programmer, told her it was good that she had never programmed before she went into it. One thing that helps her, I think, is she had a background in mathematics beforehand. On the other hand, I just saw an article talking about "Essential Lisp," which is supposed to be very well researched as an introductory CS text, and the approach the authors found was best with students was to teach them Lisp using an imperative style first, and then get into the pure functional stuff later. Maybe this is because most of the students had only had experience with imperative languages. I know that it was really tough for me to learn Lisp when I was first introduced to it, and I had programmed in Basic for about 7 years, and Pascal for about 1 year, before I got to it. I remember I totally bombed the first assignment (n Queens).

Sterling chip Camden
Sterling chip Camden

There's so much to potentially learn about that we have to apply a focus to it. Otherwise, I might stop in the middle of writing some code to spend a few hours exploring the history of the shape of the letter 'l' in my DejaVu Sans Mono font (not that I haven't done that before).

Charles Bundy
Charles Bundy

" i am not sure that I agree that a language is JUST a means of modelling an idea." http://plato.stanford.edu/entries/language-thought/ I think Mark and Chip's point is that the professor in question was trying to get across a language paradigm. By focusing on the underlying machine (ala Wizard of Oz) the students were veering off into the weeds instead of focusing on the paradigm at hand e.g. do I solve this problem using functions, procedures, logic et-al. Good that they are curious, but in this case not certain it's perceptive on their part (unless of course the compiler is producing buggy code. Took a course using Modula-2, and spent more time debugging the professor's damn compiler than learning object based methods!) Speaking of computer architecture, on the way home from a soccer game last night my daughter wanted to stop off at the bookstore to get a magazine and something hot to drink. Lo and Behold I found the following book by Jane Smiley - http://en.wikipedia.org/wiki/The_Man_Who_Invented_The_Computer Treasure turns up at the oddest time :)

Mark Miller
Mark Miller

I was complaining about a disparity in educational focus. It's not that important things are not being taught and explored. It's that a whole discipline that could contribute to this process has been marginalized for a long time. From a scientific perspective, yes, the model is the idea. As Dr. Dijkstra once said, we have the capability where we no longer have to worry about getting the computer to do what we want. We can describe our ideas formally, in whatever form we deem appropriate, and we can have it be the computer's job to execute the ideas. If the focus is on modeling how a car accelerates, or how we hear sound and what makes up sound waves, then yes, focusing on "How is the language doing this?" is a distraction, because the important thing to learn in this case is how programming helps us understand something else. If, on the other hand, the focus is on how the medium (the language) is constructed, and how this informs the construction of other media (languages), then the student's question would be an important thing to explore. I realize I'm coming at this from a different perspective, and I understand that the reason such questions might be asked, and accepted, is because students are curious to understand the "whole stack." They're more fascinated with the machine. They'd like to feel a full mastery of the system, rather than being at the mercy of somebody else's rules. I still maintain, though, that this is an engineering focus, not a scientific focus. Scientific thinking is different in that the goal, in this case, is to "construct to know," rather than "construct to use." The professor I spoke of specializes in media computation, so the focus was to get students looking at how they can use computation to understand the different elements that go into media. It's an introductory course. Now, will his students someday need to understand data processing, and get into the guts of the medium they're using? Yeah, probably. The point is that we don't have to make the underlying machine the only thing that's important. In fact that can be a distraction. It just depends on what the object of real study is at the moment.

Sterling chip Camden
Sterling chip Camden

https://secure.wikimedia.org/wikipedia/en/wiki/Lisp_machine The question about what's going on behind the scenes is a perceptive one, but it's not necessarily germane to learning a programming language. A programming language is supposed to be an abstraction above the hardware, and the compiler should optimize the best use cases for the language so that the programmer doesn't need to know how it's implemented under the covers. When performance constraints intrude, then the language implementation should document that a particular strategy has unavoidable performance penalties. But the programmer using the language should be thinking in terms of the language, not in terms of its underlying implementation. Exceptions for poor implementations granted.

VBJackson
VBJackson

Mark, Granted that I was a Computer Engineering major, not a CS major, but i am not sure that I agree that a language is JUST a means of modelling an idea. When the students asked "what was going on?", I would consider that not only a valid, but a PERCEPTIVE question. They are asking, how does the this language that we expect to model a process actually perform the modeling? Is it an acurate representation of the process? How is the compiler/interpreter going from the representation embodied in the language construct to an actual set of instructions that a CPU can execute? As far as developing alternate architectures, I am only aware of 3 basic categories of processor: Analog, Von Neuman, and Harvard or split bus. I would be very interested to find out how they designed an architecture to actually process Lisp statements. Do you have any references of it?

Sterling chip Camden
Sterling chip Camden

Very early in my programming career I sensed the conflict between mathematics and imperative programming. The statement in BASIC: x = x + 1 offended my mathematical sensibilities. That can't be true! Thought I. Soon, I came to understand the imperative nature of the statement, and the idea of state changes. Little did I know that I would need to undo all of that years later in order to understand FP.

Editor's Picks