[Tutor] Text processing and functional programming?

[Danny Yoo]

On Wed, 13 Aug 2003, Clay Shirky wrote:

> So because list comprehensions are a single construct that does the job
> of several functions, and because I got here just as 2.3 was launching
> and so don't have a history of using map, filter and lambda, I wonder if
> there is a guide to FP that explains them in terms of list
> comprehensions?

Hi Clay,


Conceptually, map() transforms a sequence of objects by applying a
function on each element.  If map() weren't built in, we could conceivably
implement it like this:

###
def map(function, sequence):
    """Transforms a sequence with a particular function."""
    mapped_elements = []
    for element in sequence:
        mapped_elements.append(function(element))
    return mapped_elements
###


(If we're sadistic, we can even reimplement map() by using list
comprehensions!

###
def map(function, sequence):
    return [function(x) for x in sequence]
###
)



With map() now defined, here's an example of it in action:

###
>>> def square(x): return x * x
...
>> map(square, range(20))
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256,
 289, 324, 361]
###

If you've seen other FP languages, the above won't look too weird.  But if
your experience is with something like Pascal, then the above will look
very weird.


Most people aren't yet comfortable passing functions as arguments to other
functions.  It's not a feature that is quite mainstream, though GUI
programmers know about this: it's the core of how "callbacks" work.  As a
result, not many people used map(), even if using it might improve the
clarity of the code.


In Python 2.0, a language enhancement was proposed --- list comprehensions
--- to make this sort of mapping behavior a little easier to work with.

    http://www.python.org/peps/pep-0202.html

The equivalent list comprehension might look something like this:

###
>>> [square(x) for x in range(20)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256,
 289, 324, 361]
###

List comprehensions can take in an arbitrary expression, so we can also do
it this way:

###
>>> [x*x for x in range(20)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256,
 289, 324, 361]
###

In contrast, map() only deals with function objects, and not arbitrary
expressions.  Trying to do something like:

    map(x * x, range(20))               ## <--  this doesn't work

just doesn't work.  However, all is not lost: we're able to dynamically
generate a function object with 'lambda':

    map(lambda x: x*x, range(20))

That's what lambda's used for, to allow us to wrap an arbitrary expression
as a function.  Nothing fancier than that.  It might have been nice to
avoid the intimidating keyword "lambda", but oh well.  *grin*


Since Python has list comprehensions as part of the language core now,
it's often preferable to use them instead of the traditional map()
builtin: most programmers will feel comfortable with list comprehensions
because the syntax isn't that daunting.


I still think, though, that it's worthwhile to know how to use functional
programming techniques, sooner or later, because there are some very cool
things that are possible with them.  Functional programmers often focus on
writing small, well-defined functions, and more importantly, know how to
make functions that can create other functions.  Here's a small example:

###
>>> def make_mapper(function):
...     def new_function(L):
...         return [function(x) for x in L]
...     return new_function
...
>>> square_list = make_mapper(square)
>>> square_list(range(10))
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
###


With something like make_mapper(), it suddenly becomes a lot more
convenient to make functions that know how to deal with sequences, given
that we have a function that can deal with a single object.

###
>>> take_all_lengths = map_maker(len)
>>> take_all_lengths(['This', 'is', 'a', 'test'])
[4, 2, 1, 4]
>>> mass_url_reader = map_maker(urllib.urlopen)
>>> docs = mass_url_reader(['http://python.org/topic/learn',
...                         'http://slashdot.org'])
###

The potential for abuse is enormous.  *grin* But it's also very liberating
to be able to do this processes on lists with the same ease that we can
apply functions on single objects.


If all we knew were list comprehensions, we wouldn't be able to create
functions like take_all_lengths() or mass_url_reader() with the same kind
of ease.  Defining them without knowing FP techniques is perfectly doable:

###
def take_all_lengths(L):
    return [len(x) for x in L]

def mass_url_reader(L):
    return [urllib.urlopen(x) for x in L]
###

So it's not hard, but it's just a bit more work.


Anyway, I hope this gives a taste of functional programming techniques!
I was sorta half asleep while writing this, so if any of it looks weird,
it's probably me.  *grin*


Please feel free to ask more questions; we'll be happy to talk about this
more.  Good luck!