Functional Programming with Python
kachayev.github.io
kachayev.github.io
Over the years, I have found that python code that people write to solve problems will fall in roughly four categories: a) completely ignorant and inefficient code; b) concise, idiomatic python code with a focus on readability; c) fancy functional code where the author is showing off their FP savvy (peppered with recursion and m/r); and d) raw, boring C-influenced code that looks primitive and boring to read, but is incredibly efficient and algorithmically sound. As much as I used to love going for b), I then prided myself for writing c). But last few years I have realized how under performing c) is for most serious work, so I tend to avoid it and try to strike a balance between d) and b), but preferably the latter. To write code in c) and tell yourself, well the data size will never be so great that the stack will blow, or memory will suffer, is in many ways just like avoiding null checks all together and saying to yourself your data will always have perfect integrity... e.g. any sane person will tell you that you cannot rely on this mindset in the long run.
So, for me at least it comes down to this: to try to pretend that you can write FP code effectively in Python is an exercise in futility. FP is more than writing a map and reduce. If thats your basis of reasoning, yeah I agree take that and run with it - I find m/r to be a neat syntax to use here and there in your program but its really challenging to write a whole program in python that is composed of several chained map / reduce functions to a large extent because things are not oriented around generators by default.. I'm not saying its impossible, just that it goes against the grain. I also argue that recursion and guard expressions (and lazy evaluation) are at the heart of the FP paradigm and if you want to do it right, then its just retarded to sit and do this in Python when there is no tail recursion.. how are you going to appreciate this concept when its so limiting?? If you want to muse yourself and marvel at pretty code, write it like this and have fun with it, but please pick another language if you want to actually ship production code.
And ... so sorry to piss on the parade.
>>> monomials = [lambda x: x(star)(star)i for i in [1,2,3]] #(not sure how to escape stars for exponentiation properly, whatever)
Those all end up being the same monomial because the integer i is captured by address and not given a new binding for every iteration. Very surprising, and an accident waiting to happen for anyone used to dealing with integers by value (hard to say that with a straight face).
The hackish workaround is "lambda x,i=i: x(star)(star)i" but I'd forget it all the time.
expr, res = "28+32+++32++39", 0
for t in expr.split("+"):
if t != "":
res += int(t)
print res
from operator import add
expr = "28+32+++32++39"
print reduce(add, map(int, filter(bool, expr.split("+"))))
(Moka(expr)
.do(string.split, '+')
.keep(lambda x: x != "")
.map(int)
.reduce(moka.add))
The problem with loops and control structures is that they don't tell, at a glance, what data structure you're operating on and what transformations you're doing. It gets exponentially worse with else clauses and nesting. It just feels bureaucratic to program like that.
In a functional style, you have more expressive primitives to work with (map, reduce, filter, fold, ...). That turns the code more concise by focusing on the data structures rather than variable mangling.
That said, I find the syntax of most languages (even functional-orientated ones) a chore. This is an area that could improve a lot.
expr = '28+32+++32++39'
print sum(int(i) for i in expr.split('+') if i is not '')1. `is` really shouldn't be used for string comparison. It checks object identities rather than string equality, which is broken here for two reasons: first, because it depends on the interpreter to keep one true copy of `''` (which CPython seems to do, but doesn't have to by the spec), and, second, it doesn't even work consistently in CPython anyway if `expr` is a Unicode string, since `'' is not u''`. (Try replacing `expr` with `u'28+32+++32++39'` and you'll get an error.)
2. If an object is known to be a string, test non-emptiness by testing the string itself: `bool('') == False`, whereas `bool('any other string') == True`. It's more concise and is equally clear to someone comfortable with Python.
I agree that the given example of functional programming is pretty ugly (though it might've been chosen just to illustrate the author's specific points), but I think the version below is really quite nice and won't break on the string comparison.
expr = '28+32+++32++39'
print sum(int(i) for i in expr.split('+') if i)More subtly, a generator (or list comprehension) implies the order in which the results are generated and an implicit but observable changing state. If I'm trying to write (or, at least, express, since we are talking about Python) parallelism, map would be a better choice.
This is definitely not true -- generator expressions can be expressed using lazy list semantics. By your logic every Haskell list comprehension would be stateful.
I would encourage you to write the denotational or operational semantics of your expressions in these matters rather than simply going by intuition.
That does not change the fact the results are given in a certain order. Lazy list semantics means the data will be calculated as it's needed, therefore, the calculation cannot be parallelized.
This is why parmap equivalents take iterables in Python, not arrays. It doesn't matter if you have lazy or eager semantics, only if your semantics are side-effecting.
It's more general than `sum(generator)` - you could write `reduce(mul, ...)` or anything else, while with sum you'll get sum and nothing more. Also, I have no problem with `reduce(some_fun, (x for x in iterable))`, which works too.
Generally, while `map` in python is much better written as list comprehension or generator expression, reduce has no equivalent short of explicit loop with accumulator variable.
Other functional languages like Haskell handle this "mess" quite well.
(putStrLn . show . sum . map read . filter (not . null) . split '+') "28+32+++32++39"
(putStrLn . show . sum) [read x | x <- (split '+' "28+32+++32++39"), not (null x)]
(Note that I had to define 'split' by hand; it is a gaping hole in the otherwise very comprehensive Data.List library.)
Have you looked at Data.List.Split (`cabal install split`)? splitOn from that package should do what you want. Admitadly, this should be part of Data.List in the standard library.
Interesting. Could you give an example? I find Haskell to have pretty much the most consistent, non-idiosyncratic and clean syntax of any language I know.
{6}({9}putStrLn . {8}show . {7}sum) {5}[{2}read x | x <- ({1}splitOn "+" "3++4"), {4}not ({3}null x)]
"3++4++9" "+" split harvest [ string>number ] map sum present print
"3++4++9"{1} "+"{2} split{3} harvest{4} [ string>number{5} ]{6} map{7} sum{8} present{9} print{10} (putStrLn{9} . show{8} . sum{7} . map{5} read{6} . filter{4} (not{3} . null{2}) . split '+'{1}) "28+32+++32++39"
expr{1} = '28+32+++32++39'
print{8} sum{7}(int(i){6} for i in expr.split('+'){2} if{5} i is not ''{4})
Haskell programs, on the other hand, are clearly written backwards :-)
=, =>, =>>, >>=, ->, |, <|>, ., :, ::, $, `...`, and such.
As for the rest, well, I guess I feel fine about their place in the syntax (for example the pipe (|) in the list comprehension: what else should be used? It's trying to look like set notation). What would be a less noisy alternative in your opionion? More English words/keywords instead of ASCII symbols?
- functional is accumulative in thinking. I can evaluate each step gradually without doing anything more than function composition. In imperative programming its coupled.
- functional is side-effect free, can't mis-assign res.
- functional is abstract friendly, I can pass the predicate I want, same for accumulation/combination.
I kinda agree that the imperative code is somehow easier to read (3 little chunks of lines instead of 3 nested composition) but to write, test or adapt the functional way as some advantages.
In Fexl (http://fexl.com), you can reduce the nesting by using the ';' ("pivot") syntax. So instead of this:
print (fold add 0 (map int (filter valid_int (split "+" exp)))
print; fold add 0; map int; filter valid_int; split "+" exp
\int=(\str valid_int str (int str) 0)
print; fold add 0; map int; split "+" exp f = X.split('+') | where(X) | foreach(int) | sum
print f(expr)
The understandability-complexity of the Moka style scales linearly with the number of components, because it is written "one-dimensionally". The problem with the imperative style is that its understandability-complexity is superlinear in the number of components because any variable in a nested loop can interact with any other variable.
I also like your use of "keep" as opposed to "filter". I can never remember if "filter" means "filter out" or "filter in"!
I love functional programming. Nonetheless, I strongly believe in using the natural idioms of your language: they are more widely used, more widely optimized, and more often thought about.
I think you would find that the functional style is not idiomatic in Python most of the time. This can hurt readability, performance, and interoperability.
Overall, I would encourage people to do what is natural -- it is often also what's correct. For example, Python generators expressions are lazy sequence semantic constructions and are both functional in semantics and better than the equivalent map/reduce semantics.
I understand the appeal of functional programming, really I do, but why can't we accept that sometimes just because you can doesn't mean you should?
- compiled code, fast
- cleaner, nicer, conciser syntax
- type safety built in
- pattern matching
- numpy equivalents are now available
- purity (see John Carmack talking about how it helps when codebases get large)
To switch from python to haskell easily within minutes, realize that a python function is simply do notation in haskell. So replace assignment (=) with arrow (<-) and write with "func v1 v2 = do".
Then pure functions are those without do and no assignment written lisp/scheme style. "$" means you can get rid of the parentheses.
After that, declaring types is equivalent to expressing how syntax tree can be written. You can use these to plan out how you attack your problem and then let compiler help you when writing out your functions. You could even just write out types and outsource the function writing to someone else (similar to your oo architects can parcel out code writing).
So, all python, golang, and ruby programmers - you really should check out haskell and realize it's superiority. They've taken your niche.
(If anyone wants to pay me to code in haskell, send me an email at haskellpostgresprogrammer@gmail.com, looking for telecommute work)
However the "What did we miss?" slide tells it like it is. FP in Python is never going to be like FP in, e.g., Haskell. Moreover, the libraries you use are going to have objects and mutable state everywhere which ends up being very frustrating.
If you're not forced not to use FP, I recommend just going with Haskell (or OCaml or Scala or whatever according to your taste).
If you're writing some kind of server, I'd nominate Erlang for serious consideration. The OTP framework is fantastic and rock solid.
* `operator.attrgetter`, `getattr()`, `setattr()`, `object.__getattribute__` [1][2]
* `operator.itemgetter`, `object.__getitem__` [3][4]
* `collections.abc` [5][6]
[1] http://docs.python.org/2/library/operator.html#operator.attr...
[2] http://docs.python.org/2/reference/datamodel.html#object.__g...
[3] http://docs.python.org/2/library/operator.html#operator.item...
[4] http://docs.python.org/2/reference/datamodel.html?#object.__...
[5] http://docs.python.org/2/library/collections.html#collection...
reduce(operator.add, ...)
sum(...)
...all loops can be represented as folds
d0m's Moka example (https://news.ycombinator.com/item?id=6150944) is closer to composable. I would suggest the following modification. Instead of chaining methods, have a function "chain" which composes functions. We could then write
chain(do(string.split, '+'),
keep(lambda x: x != ""),
map(int),
reduce(moka.add))
non_blanks_to_int = chain(keep(lambda x: x != ""),
map(int))
chain(do(string.split, '+'),
non_blanks_to_int,
reduce(moka.add))
Come to my FP days talk in Cambridge, UK, Thursday 24th October, 2013 if you want to hear more about this!
parts=s.split('+')
keep=(s for s in parts if s)
ints=(int(s) for s in keep)
sum(ints)
That split returns a list, but the other steps are lazy.
I can agree with you in terms of readability, even as a mathematician. For example, the list comprehension syntax mirrors the mathematician's "set-builder notation," so it feels very natural.
However, consider something like a "max", "min", or "argmax" function. Like map and reduce, you can implement this in terms of reduce, but I don't see how you can implement it in terms of a list comprehension. Or consider something like an RPN calculator, which could be implemented as a single reduce call whose initial value is an empty stack and whose input list is the list of RPN tokens.
It seems that list comprehensions can do less in a very objective sense and couldn't be used to replace reduce without other supporting characters. Python has those supporting characters, of course, so there's a good 80/20 argument for favoring list comprehensions over a more opaque call to reduce.
But I also just had an experience I haven't had much since I was extremely new: the experience of going back to something I wrote last week and not being able to decipher it. I'm going to keep it up, partly because I like it and also because I have some hope (unjustified?) that map will give me better performance than looping. I wish there was a way to enable tail recursion though--seriously, I promise I'll ask for clear stack traces when I need them.
List comprehensions beat map in CPython. As a fellow pythonista, I can guarantee you that using the builtin higher-order functions excessively will cause you nothing but pain. The feeling of being lost when you revisit code will be common.
I had a coworker who undertook a plan similar to yours, except he gave himself less rigid constraints. He is a very smart guy but he fell into the tar pit of code masturbation and couldn't finish the project he took on. He simply couldn't manage the complexity of his application in his quest to be As Functional As Possible. The project was never completed and after wasting many man hours, the company was forced to purchase $25,000+ worth of software to compensate. It didn't reflect well on him.
Python has functional programming support, but it's not intended to be the dominant paradigm. Python 3 even removed reduce as a builtin. The high order functions are still useful, but definitely not all the time. The principles of functional programming, such as limiting side effects and statefulness, are always useful. But Python has awful lambdas and no lexical scoping (fixed in 3). Python's functional support will always be hobbled as Guido doesn't support it.
Since you seem to have a healthy interest in functional programming, I'd suggest looking at Clojure. If you want to challenge yourself, it's a good choice as you'd have to learn lisp (macros, code is data, s-exprs, etc) and the JVM ecosystem, while being almost totally constrained to writing functional code. Haskell is even more strict and is a pure functional language, forbidding state entirely and relying on monads for things like I/O. I almost like it as much as Clojure. Erlang and Ocaml are also worth checking out.
from collections import namedtuple
TailCall = namedtuple('TailCall', ['function', 'args'])
def tail_recurse(fn, args):
next_call = fn(*args)
while isinstance(next_call, TailCall):
next_call = next_call.function(*next_call.args)
return next_call
def count_to_4(start):
"""Dummy tail-recursive function"""
if start == 4:
return 4
else:
return TailCall(count_to_4, [start + 1])
print tail_recurse(count_to_4, [-6]) ipython nbconvert --to slides <notebook.ipynb>
from operator import add
expr = "28+32+++32++39"
print reduce(add, map(int, filter(bool, expr.split("+"))))
"28+32+++32++39".split(/([\+]+)/g).reduce((r,v) => r+v, 0);