Functional programming with Python
To work with lists many c/c++ programmer use a simple for-loop. I will try to explain how this can be made a little bit easier. For that I use the self-explaining script language python.
Here is a simple example to filter all odd integers from a list in simple python 2.x syntax.
def filter_odd(myList):
result = [] # initialize the result list
for num in myList: # iterate over the list
if num % 2 == 1: # modulo 2 return 1 for odd integers
result.append(num) # add to the result
return result
result = [] # initialize the result list
for num in myList: # iterate over the list
if num % 2 == 1: # modulo 2 return 1 for odd integers
result.append(num) # add to the result
return result
The function call will return a list containing only odd integers (you can use the result of the modulo operation directly without comparing with 1). Try it directly on a interactive python console (as an applet on secapps.com).
>> print filter_odd([1,2,3,4,5])
[1, 3, 5]
[1, 3, 5]
try it functional
The function filter_odd could be a more generic method, if the condition could be a variable or used as a parameter:
def condition_odd(num): # the condition as separate function
return num % 2 == 1
#condition_odd
def generic_filter(condition, myList):
result = []
for num in myList:
if condition(num): # the same condition like the first example, only as parameter
result.append(num)
return result
#generic_filter
return num % 2 == 1
#condition_odd
def generic_filter(condition, myList):
result = []
for num in myList:
if condition(num): # the same condition like the first example, only as parameter
result.append(num)
return result
#generic_filter
We can define a condition as a function and use it as a parameter in the generic_filter implementation to filter the values of list myList. Ok, you don't have to define a generic filter function, python offers the filter function in the standard language.
>> print filter_generic(condition_odd, [1,2,3,4,5])
[1, 3, 5]
>>print filter(condition_odd, [1,2,3,4,5])
[1, 3, 5]
[1, 3, 5]
>>print filter(condition_odd, [1,2,3,4,5])
[1, 3, 5]
The new implementation does not say what to do, it say how to use the condition on a list and has much less code compared to first example.
Passing a function as a parameter is a key aspect of functional programming. But the condition_odd function will only be used for the line with the filter call. The next step will show you, how to use this function parameter without defining it separately.
>> print filter(lambda x: x % 2 == 1, [1,2,3,4,5])
[1, 3, 5]
[1, 3, 5]
The first parameter is the lambda construct: Create a temporary, anonymous function with x as parameter and return the result of the term "x % 2 == 1". I don't have to define a function and I can use the filter in one line. Save namespace with one-time functions and code lines.
list comprehension
One-line solutions are fine to write short code, but it also has to be readable. If the reader doesn't know what filter and lambda means, it can be confusing.
An other alternative for the one-line filter solution, and more confusing in python, is list comprehension. You can write the above example:
>> print [x for x in [1,2,3,4,5] if x % 2 == 1]
[1, 3, 5]
[1, 3, 5]
The result contains items from the constant list, filtered with the term in the if-condition. [Updated] You have to use the exact syntax, not the simple variant like filter.
more functional helper: map and reduce
There are some other list functions. First the map function with calls for every item in the list a function. In a example we will double every integer from the list. This could also be written as a list comprehension.
>>print map(lambda x: x*2, [1,2,3,4,5])
[2, 4, 6, 8, 10]
>>print [x**2 for x in [1,2,3,4,5]]
[2, 4, 6, 8, 10]
[2, 4, 6, 8, 10]
>>print [x**2 for x in [1,2,3,4,5]]
[2, 4, 6, 8, 10]
Second function is reduce. It get a function and a list as parameter and will call the function with the first two items from the list. Then the result and the next item will be computed and so on. A simple exapmle will calculate the sum of a number list:
>>print reduce(lambda a, b: a + b, [1,2,3,4,5])
15
15
This simple example can also resolved with the build-in sum function.
two examples
Now we will try some real world examples - project eulers first problem: Find the sum of all the multiples of 3 or 5 below 1000. Simply to resolve with a for-loop:
- the condition term is x%3==0 or x%5==0
- filter the values beetween 0 and 1000
- calculate the sum
def eulerOne(myList):
mySum = 0
for num in range(1000):
if num%3==0 or num%5==0:
mySum += num
return mySum
mySum = 0
for num in range(1000):
if num%3==0 or num%5==0:
mySum += num
return mySum
But we want to do it with an one-liner, with functional programming or a list comprehension:
>>print reduce(lambda a,b:a + b, [x for x in range(1000) if x % 3 == 0 or x % 5 == 0])
233168
>>print sum([x for x in range(1000) if not (x%3 and x%5)])
233168
233168
>>print sum([x for x in range(1000) if not (x%3 and x%5)])
233168
The second line show a shorter version with sum and a little bit boolean algebra but it will not so clear readable.
As a second example filter all persons who older than 18:
>>persons = [{'age': 5, 'name': 'peter'}, {'age': 20, 'name': 'paul'}]
>>print [x['name'] for x in persons if x['age'] > 18]
['paul']
>>print map(lambda x:x['name'], filter(lambda x: x['age']>19, persons))
['paul']
>>print [x['name'] for x in persons if x['age'] > 18]
['paul']
>>print map(lambda x:x['name'], filter(lambda x: x['age']>19, persons))
['paul']
summary
Here the summary with the python doc-strings to the new learned functions:
- filter(function or None, sequence) -> list, tuple, or string
- Return those items of sequence for which function(item) is true. If
function is None, return the items that are true. If sequence is a tuple
or string, return the same type, else return a list. - map(function, sequence[, sequence, ...]) -> list
- Return a list of the results of applying the function to the items of
the argument sequence(s). If more than one sequence is given, the
function is called with an argument list consisting of the corresponding
item of each sequence, substituting None for missing values when not all
sequences have the same length. If the function is None, return a list of
the items of the sequence (or a list of tuples if more than one sequence).
- reduce(function, sequence[, initial]) -> value
- Apply a function of two arguments cumulatively to the items of a sequence,
from left to right, so as to reduce the sequence to a single value.
For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
((((1+2)+3)+4)+5). If initial is present, it is placed before the items
of the sequence in the calculation, and serves as a default when the
sequence is empty. - lambda - syntax
- normal function definition:
def name(arguments):
return expression
anonymous lambda function definition:
lambda arguments: expression
[Updated]: filter and map are still in python 3000 in the iterator variant, the reduce-function is moved in the functools module.
- Origins of Python's "Functional" Features
- Natural Language Processing with Python
- Python 3 for Absolute Beginners (Expert's Voice in Open Source)
Trackback URL for this post:
http://united-coders.com/trackback/11
Comments
timb - Sat, 04/18/2009 - 01:32
"The result contains items from the constant list, filtered with the term in the if-condition. But you can't call it with the pre-defined function"
I may be misunderstanding you, but you can filter with a function:
>>> [x for x in [1,2,3,4,5,6] if condition_odd(x)]
[1, 3, 5]
On another topic, requiring users to register in order to leave a comment is discouraging.
Compare your current flow:
1. Click register
2. Fill out form
3. Check email for verification key, click email link
4. Change one-time password
5. Navigate back to original post
6. Fill out comment form
It's too many hoops to jump through versus something like:
1. Fill out comment form
Nico Heid - Sat, 04/18/2009 - 09:45
on leaving comments:
I agree with you on the workflow. The comments are now available for everyone without registration. It was caused by wrong configuration and not intention. Sorry for that.
on the coding part:
Christian will look into it for sure, but may take a little time.
thanks again
Christian Harms - Sat, 04/18/2009 - 12:37
Yes, your are right. The difference between filter and a list comprehension with if-Condition is only the syntax. With the functional syntax you need only a function and the list, with the list comprehension you need the "for x in list" and the "if ".
The more benefit for the filter-variant I will post the follow-up article next week.
@Nico: Yes free comments or a integrationg like disqus would be fine ;-)
Anonymous - Sun, 04/19/2009 - 12:37
The function filter, map and lambda are still in python 3000 in the functools module, only reduce is skipped.
This is completely and utterly wrong.
lambdais a statement, not a function, and it doesn't move (statements aren't namespaced after all).filterandmap(as well aszip) stay in__builtins__, but they now return an iterator instead of a list. As a result,itertools.imap,itertools.ifilteranditertools.izipare redundant and have been removed.reduceon the other hand, was initially proposed for removal and ends up being moved tofunctools.Proof:
$ python3.0
Python 3.0.1 (r301:69556, Apr 1 2009, 11:42:54)
[GCC 4.0.1 (Apple Inc. build 5490)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> map
<class 'map'>
>>> filter
<class 'filter'>
>>> zip
<class 'zip'>
>>> import functools
>>> functools.reduce
<built-in function reduce>
>>> import itertools
>>> itertools.imap
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'module' object has no attribute 'imap'
>>> itertools.ifilter
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'module' object has no attribute 'ifilter'
>>> itertools.izip
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'module' object has no attribute 'izip'
>>>
Christian Harms - Mon, 04/20/2009 - 09:33
Thanx for correcting me - in my first article I had to check carefully all parts of the article. I will update the article.
Anonymous - Sun, 04/19/2009 - 17:28
Hi Christian,
I was really supprised to see your article today on "reddit-python" :) Hope things are still fine in KA...
In the intro to map/reduce you say "..we will square every integer from the list" but you then just multiplied each element by 2.
Maybe you missed one asterix:
print map(lambda x: x**2, [1,2,3,4,5])Greets from Munich,
Lothar K.
Christian Harms - Mon, 04/20/2009 - 10:00
Yes, very attentive - I have edit the word square to double ;-)
Greets to munich - nice to see you here with my first article. We will try with this blog to bring some interessting aspect of our daily study to the world ... do subscribe our litte blog - NOW!
Anonymous - Fri, 07/03/2009 - 14:28
This article has been shared on favSHARE.net.
IPv6 request crashed my google app engine application | unit (not verified) - Tue, 03/30/2010 - 06:46
[...] you want to calculate a number from a IPv6 address try this short functional python code: def [...]
Part 550i Bmw 318ti, Second Hand 325i Bmw 318ti (not verified) - Fri, 05/21/2010 - 13:05
[...] 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879Part 550i Bmw 318ti, Second Hand 325i Bmw 318tiPart 550i Bmw 318ti, Second Hand 325i Bmw 318ti318ti discount car parts brake caliper 318ti promotion back part 1994 740il mpg bmw 318ti sale used 330i 318ti bmw 550i bmw 318ti airbag warning light 530i parts used 740il bmw 318ti 318ti part 330xi bmw 540i 318ti for sale pa bmw 318ti radiator flush 318ti part good bmw 318ti sale transmission 1995 bmw 318ti muffler 318ti part used bmw 323is 1999 318ti replacement headlight assembly 1998 bmw 328i 330xi sale x3 735i bmw 318ti 1995 bmw 318ti hp 318ti rent pets bmw 318ti part discount compact 1997 bmw 318ti mpg 323is headlight lamp 318ti bmw 320i bmw 318ti car dealer 535i thermostat replacement bmw 318ti 2007 550i performance parts bmw 318ti bmw 318ti reliability coupe model bmw 318ti accessories 328ci parts 328i 323ci bmw 318ti 318ti portugal 1997 bmw 318ti door panel discount 320i seats bmw 318ti 318ti discount bmw 325xi 1999 bmw 318ti mpg change thermostat bmw 318ti 1995 bmw 318ti fuel economy 320i parts discount prices 318ti bmw 528i bumper bmw 318ti 328ci aftermarket performance parts bmw 318ti 1995 bmw 318ti 2nd hand parts l6 aftermarket bmw 318ti 1998 bmw 318ti horsepower ignition 318i bmw 318ti 2006 330 used parts bmw 318ti 2001 bmw 318ti reviews 630csi parts bmw 318ti bmw 318ti bulb sylvania sale 318ti used bmw bmw 318ti supercharger downing atlanta bmw 318ti sport racing bmw 318ti clubsport bmw 318ti engine 1998 318ti removal pull bmw 318ti euro tail lights sale used bmw series 318ti classified 1995 318ti mpg bmw 318ti fog light led 318ti used qrp engines 745li parts 2nd hand bmw 318ti 325 replacement headlight assembly bmw 318ti 323is 535i auto parts bmw 318ti 850i aftermarket parts 850csi bmw 318ti 323is replacement 318ti bmw 330xi 318ti rent homes bmw 318ti parts accessories discount prices 1985 735i used parts wiring harness bmw 318ti bmw 318ti abs codes aftermarket 3 series bmw 318ti 318ti removal door oem 850csi bmw 318ti 325i parts oem 330ci bmw 318ti 328 aftermarket fog light 1998 bmw 318ti bmw 318ti antenna mast 318ti bulb brake light oem 318ti radiator water pump bmw 318is bmw 318ti sedan aftermarket 2007 330i 1998 bmw 318ti 318ti coupon floor 1999 bmw 318ti parts kool vue replacement 1997 bmw 318ti fit 318is radiator offers bmw 318ti 1984 325e sale bmw 318ti 318ti discount bmw 323i 318ti odm 318ti substitute oil headlight 850csi floor mats bmw 318ti bmw 318ti carmax 1995 bmw 318ti parts direct oe oem 535is bmw 318ti bmw 318ti sport suspension 323is 1999 bmw 318ti headlight lens bulb 325i parts 528e bmw 318ti 318ti hid accessories 318ti bulb automotive 318ti performance online 535is auto repair bmw 318ti part finder 1995 bmw 318ti 318ti boiler sale bmw 318ti hatchback used compression ratio 318ti accessories oem 1995 bmw 318ti used parts 318ti alternative 635csi accessories bmw 318ti K20 Free Chevrolet | 323is Oem 328is | R1500 Space Gmc | B3500 Solid B3500 | Amigo Blub Rewards | [...]
K15 K1500 Tacoma Used Auto Parts Salvage Yards, 1990 Chevrol (not verified) - Fri, 05/21/2010 - 22:19
[...] 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061K15 K1500 Tacoma Used Auto Parts Salvage Yards, 1990 Chevrolet TacomaK15 K1500 Tacoma Used Auto Parts Salvage Yards, 1990 Chevrolet Tacomatacoma mall jobs toyota tacoma clutch 2009 tacoma sale texas trucks k15 k1500 tacoma for sale finder 2007 toyota tacoma towing 2001 toyota tacoma leveling kit tacoma help tacoma xenon hid 2006 toyota tacoma dimensions toyota tacoma motorcycle seat cover toyota tacoma replacement exhaust buy k5 blazer toyota tacoma 1999 ford ranger sport toyota tacoma toyota tacoma control arm tacoma rear bumper off road honda ridgeline toyota tacoma supra manual wiring diagram toyota tacoma tacoma accessories gmc k15 k1500 tacoma part scanlover k1500 tacoma discount used 1990 gmc tacoma tacoma custom audio toyota tundra dodge caravan tacoma 1999 toyota tacoma antenna toyota tacoma aftermarket floor mats nerf bars toyota tacoma bumper parts pick up sale toyota tacoma compact pickup tacoma pierce county health department 2009 tacoma parts k15 k1500 tacoma price toyota tacoma recall warranty c25 c1500 tacoma headlight cl55 amg road armor tacoma c35 g3500 tacoma headlight cutlass ciera cars taillight toyota tacoma 2009 toyota tacoma mileage discount dodge w100 tacoma exhaust manifold tacoma used fail used truck 1999 toyota tacoma 2000 toyota tacoma pre runner highlander part tail light guards 2010 toyota tacoma toyota tacoma sale owner ga bmw m3 sale seattle tacoma 2005 tacoma trd cold air intake c30 tacoma aftermarket 7.3 tacoma offroad 1998 toyota tacoma tires aftermarket grill toyota tacoma accessories 2005 tacoma wheels b toyota b tacoma b b xtreme floor mats c25 c2500 tacoma oem fits used toyota tacoma sale california c25 c2500 tacoma replacement high quality 2009 tacoma tail light c30 c2500 tacoma 1969 gmc 2004 tacoma truck tacoma map light sound transit 2000 toyota tacoma mirror kool vue 2002 toyota tacoma radio replacing headlight toyota tacoma oxygen sensor aftermarket toyota tacoma truck accessories 1994 tacoma intake metra 99 8214tg 2009 toyota tacoma best diesel tacoma buy tacoma headlight chrome bracket xrunner prerunner 2010 toyota tacoma 1990 chevrolet tacoma 1997 toyota tacoma body parts toyota tacoma fog lights used ford ranger florida toyota tacoma pre owned toyota tacoma maine camry custom parts cold air intake toyota tacoma c350 c3500 tacoma performance tacoma discount washington 1999 toyota tacoma magnaflow tacoma bumper parts discount c30 tacoma bulb volvo 240 bulb offers tacoma bulbs hid tacoma access cab buy chevrolet k30 tacoma 5.4 l tacoma land cruiser toyota certified used vehicles 1996 toyota tacoma wheels download k15 k1500 tacoma c20 a2550 tacoma download k15 k1500 tacoma flowmaster f 250 tacoma oem truck parts 2008 toyota tacoma performance parts c20 c2500 tacoma headlight door toyota tacoma headlight assembly exhaust manifold toyota tacoma tailgate camera truck accessories fender buys tacoma 1996 toyota tacoma engine extended cab 1996 toyota tacoma payload 2009 toyota tacoma incentives 1990 gmc tacoma repair manual 200 tacoma aftermarket parts grand prix racing tacoma buy tacoma trucks aftermarket seats tacoma bench seat toyota tacoma 4x4 parts coil springs Lexus Is250 Key | Montego Crown Molding | Squareback Episode Accessories | Gl450 Part Performance | Mercedes Benz Cls55 | [...]
The rotate google contest in 15 lines | united-coders.com (not verified) - Thu, 08/19/2010 - 13:46
[...] And to do this with a complete list of lines use a list comprehension (read more about functional programming in python). [...]
Google code jam solution for alien language | united-coders. (not verified) - Mon, 08/30/2010 - 10:46
[...] the complete solution uses the filter function again (read more about the functional part of python) to shrink the [...]