David Mertz, Ph.D.
Applied Metaphysician, Gnosis Software, Inc.
Earlier installments of this columns touched on many basic concepts of functional programming (FP). This column continues the discussion by illustrating additional capabilities, especially those contained in Xoltar Toolkit: Currying, higher-order functions, and other specialized concepts.
Python is a freely available, very-high-level, interpreted language developed by Guido van Rossum. It combines a clear syntax with powerful (but optional) object-oriented semantics. Python is available for almost every computer platform you might find yourself working on, and has strong portability between platforms.
Never content with partial solutions, one reader--Richard Davies--raised the issue of whether we might move bindings all the way into individual expressions. Let's take a quick look at why we might want to do that, and also show a remarkably elegant way of expressing this that a comp.lang.python contributor provided.
Let us first recall the
Bindings class of the functional
module. Using the attributes of that class, we were able to
assure that a particular name means only one thing within a
given block scope:
>>> from functional import * >>> let = Bindings() >>> let.car = lambda lst: lst >>> let.car = lambda lst: lst Traceback (innermost last): File "<stdin>", line 1, in ? File "d:\tools\functional.py", line 976, in __setattr__ raise BindingError, "Binding '%s' cannot be modified." % name functional.BindingError: Binding 'car' cannot be modified. >>> let.car(range(10)) 0
Bindings class does what we want within a module or
def scope, but there is no way to make it work
within a single expression. In ML-family languages, however,
it is natural to create bindings within a single expression:
-- car (x:xs) = x -- *could* create module-level binding list_of_list = [[1,2,3],[4,5,6],[7,8,9]] -- 'where' clause for expression-level binding firsts1 = [car x | x <- list_of_list] where car (x:xs) = x -- 'let' clause for expression-level binding firsts2 = let car (x:xs) = x in [car x | x <- list_of_list] -- more idiomatic higher-order 'map' technique firsts3 = map car list_of_list where car (x:xs) = x -- Result: firsts1 == firsts2 == firsts3 == [1,4,7]
Greg Ewing observed that we can accomplish the same effect using Python's list-comprehensions; we can even do it in a way that is nearly as clean as Haskell's syntax:
>>> list_of_list = [[1,2,3],[4,5,6],[7,8,9]] >>> [car_x for x in list_of_list for car_x in (x,)] [1, 4, 7]
This trick of putting an expession inside a single-item tuple in a list-comprehension does not provide any way of using expression-level bindings with higher-order functions. To use the higher-order functions, we still need to use block-level bindings, as with:
>>> list_of_list = [[1,2,3],[4,5,6],[7,8,9]] >>> let = Bindings() >>> let.car = lambda l: l >>> map(let.car,list_of_list) [1, 4, 7]
Not bad, but if we want to use
map(), the scope of the
binding remains a little broader than we might want.
Nonetheless, it is possible to coax list comprehensions into
doing our name bindings for us, even in cases where a list is
not what we finally want:
# Compare Haskell expression: # result = func car_car # where # car (x:xs) = x # car_car = car (car list_of_list) # func x = x + x^2 >>> [func for x in list_of_list ... for car in (x,) ... for func in (car+car**2,)] 2
What we have done is peform an arithmetic calculation on the
first element of the first element of
list_of_list while also
naming the arithmetic calculation (but only in expression
scope). As an "optimization" we might not bother to create a
list longer than one element to start with, since we choose
only the first element with the ending index
>>> [func for x in list_of_list[:1] ... for car in (x,) ... for func in (car+car**2,)] 2
Three of the most general higher-order functions are built into
filter(). What these
functions do--and the reason we call them "higher-order"--is
take other functions as (some of) their arguments. Other
higher-order functions, but not these builtins, return function
Python has always given users the ability to construct their own higher-order functions by virtue of the first-class status of function objects. A trivial case might look like:
>>> def foo_factory(): ... def foo(): ... print "Foo function from factory" ... return foo ... >>> f = foo_factory() >>> f() Foo function from factory
The Xoltar Toolkit (see Resources), which I discussed also in
early installments of this column, comes with a nice collection
of higher-order functions. Most of the functions that Xoltar's
functional module provides are ones that have been developed
in various traditionally functional languages, and whose
usefulness has proved itself over many years.
Possibly the most famous and most important higher-order
function is traditionally called
curry() is named
after the logician Haskell Curry, whose first-name is also used
to name the abovementioned programming language. The insight
that underlies "currying" is that it is possible to treat
(almost) every function as a partial function of just one
argument. All that is necessary for currying to work is to
allow the return value of functions to themselves be functions,
but with the returned functions "narrowed" or "closer to
completion." The way this works is quite similar to the
closures that I wrote about in an earlier column--each
successive call to a curried return function "fills in" more of
the data involved in a final computation (data attached to a
Let's illustrate currying first with a very simple example in
Haskell, then with the same example repeated in Python using
computation a b c d = (a + b^2+ c^3 + d^4) check = 1 + 2^2 + 3^3 + 5^4 fillOne = computation 1 -- specify "a" fillTwo = fillOne 2 -- specify "b" fillThree = fillTwo 3 -- specify "c" answer = fillThree 5 -- specify "d" -- Result: check == answer == 657
Now in Python:
>>> from functional import curry >>> computation = lambda a,b,c,d: (a + b**2 + c**3 + d**4) >>> computation(1,2,3,5) 657 >>> fillZero = curry(computation) >>> fillOne = fillZero(1) # specify "a" >>> fillTwo = fillOne(2) # specify "b" >>> fillThree = fillTwo(3) # specify "c" >>> answer = fillThree(5) # specify "d" >>> answer 657
The parallel with closures can be illustrated further by
presenting the same simple tax-calculation program used in the
earlier installment (this time using
from functional import * taxcalc = lambda income,rate,deduct: (income-(deduct))*rate taxCurry = curry(taxcalc) taxCurry = taxCurry(50000) taxCurry = taxCurry(0.30) taxCurry = taxCurry(10000) print "Curried taxes due =",taxCurry print "Curried expression taxes due =", \ curry(taxcalc)(50000)(0.30)(10000)
Unlike with closures, we need to curry the arguments in a
specific order (left to right). But note that
also contains an
rcurry() class that will start at the other
end (right to left).
taxcalc(50000,0.30,10000). But in a different level it makes
rather clear the concept that every function can be a function
of just one argument--a rather surprising idea to those new to
Beyond the "fundamental" operation of currying,
provides a grab-bag of interesting higher-order functions.
Moreover, it is really not hard to write your own higher-order
functions--either with or without
functional. The ones in
functional provide some interesting ideas, at the least.
For the most part, higher-order functions feel like "enhanced"
versions of the standard
lot of the time the pattern in these functions is roughly "take
a function or functions and some lists as arguments, then apply
the function(s) to list arguments." There are a surprising
number of interesting and useful ways to play on this theme.
Another pattern is "take a collection of functions and create a
function that combines their functionality." Again, numerous
variations are possible. Let us look at some of what
also() both create a function
based on a sequence of component functions. The component
functions can then be called with the same argument(s). The
main difference between the two is simply that
expects a single list as an argument, while
also() takes a
list of arguments. In most cases, these are useful for
function side effects, but
sequential() optionally lets you
choose which function provides the combined return value:
>>> def a(x): ... print x, ... return "a" ... >>> def b(x): ... print x*2, ... return "b" ... >>> def c(x): ... print x*3, ... return "c" ... >>> r = also(a,b,c) >>> r <functional.sequential instance at 0xb86ac> >>> r(5) 5 10 15 'a' >>> sequential([a,b,c],main=c)('x') x xx xxx 'c'
conjoin() are similar to
also() in terms of creating new functions
that apply argument(s) to several component functions. But
disjoin() asks whether any component functions return true
(given the argument(s)), and
conjoin() asks whether all
components return true. Logical shortcutting is applied, where
possible, so some side effects might not occur with
joinfuncs() is similar to
also(), but returns
a tuple of the components' return values rather than selecting
a main one.
Where the previous functions let you call multiple functions
with the same argument(s),
you call the same function against a list of arguments. In
general structure, these are a bit like the builtin
filter() functions. But these particular
higher-order functions from
functional ask boolean questions
about collections of return values. For example:
>>> from functional import * >>> isEven = lambda n: (n%2 == 0) >>> any([1,3,5,8], isEven) 1 >>> any([1,3,5,7], isEven) 0 >>> none_of([1,3,5,7], isEven) 1 >>> all([2,4,6,8], isEven) 1 >>> all([2,4,6,7], isEven) 0
A particularly interesting higher-order function for those with
a little bit of mathematics background is
composition of several functions is a "chaining together" of
the return value of one function to the input of the next
function. The programmer who composes several functions is
responsible for making sure the outputs and inputs match
up--but then, that is true any time a programmer uses a return
value. A simple example makes it clear:
>>> def minus7(n): return n-7 ... >>> def times3(n): return n*3 ... >>> minus7(10) 3 >>> minustimes = compose(times3,minus7) >>> minustimes(10) 9 >>> times3(minus7(10)) 9 >>> timesminus = compose(minus7,times3) >>> timesminus(10) 23 >>> minus7(times3(10)) 23
I hope this latest look at higher-order functions will picque readers' interest in a certain style of thinking. By all means, play with it. Try to create some of your own higher-order functions; some might well prove useful and powerful. Let me know how it goes, perhaps a later installment of this ad hoc series will discuss the novel and fascinating ideas that readers continue to provide.
The earlier installments of this series on functional programming in Python can be found at:
Bryn Keller's "xoltar toolkit" which includes the module
functional adds a large number of useful FP extensions to
Python. Since the
functional module is itself written
entirely in Python, what it does was already possible in Python
itself. But Keller has figured out a very nicely integrated
set of extensions, with a lot of power in compact definitions.
The toolkit can be found at:
A good starting point for functional programming is the Frequently Asked Questions for comp.lang.functional :
The author has found it much easier to get a grasp of functional programming via the language Haskell than in Lisp/Scheme (even though the latter is probably more widely used, if only in Emacs). Other Python programmers might similarly have an easier time without quite so many parentheses and prefix (Polish) operators.
An excellent introductory book is:
Haskell: The Craft of Functional Programming (2nd Edition), Simon Thompson, Addison-Wesley (1999).
A book with a somewhat more applied feel which is an equally introduction to Haskell is:
The Haskell School of Expression: Learning Functional Programming Through Multimeia, Paul Hudak, Cambridge University Press (2000).
Since conceptions without intuitions are empty, and intuitions without conceptions, blind, David Mertz wants a cast sculpture of Milton for his office. Start planning for his birthday. David may be reached at [email protected]; his life pored over at http://gnosis.cx/publish/. Suggestions and recommendations on this, past, or future, columns are welcomed.