Implementation of missing features to enjoy functional programming in Python
Project description
Fn.py: enjoy FP in Python
Despite the fact that Python is not pure-functional programming language, it’s multi-paradigm PL and it gives you enough freedom to take credits from functional programming approach. There are theoretical and practical advantages to the functional style:
Formal provability
Modularity
Composability
Ease of debugging and testing
Fn.py library provides you with missing “batteries” to get maximum from functional approach even in mostly-imperative program.
More about functional approach from my Pycon UA 2012 talks: Functional Programming with Python.
Scala-style lambdas definition
from fn import _
from fn.op import zipwith
from itertools import repeat
assert list(map(_ * 2, range(5))) == [0,2,4,6,8]
assert list(filter(_ < 10, [9,10,11])) == [9]
assert list(zipwith(_ + _)([0,1,2], repeat(10))) == [10,11,12]
More examples of using _ you can find in test cases declaration (attributes resolving, method calling, slicing).
Attention! If you work in interactive python shell, your should remember that _ means “latest output” and you’ll get unpredictable results. In this case, you can do something like from fn import _ as X (and then write functions like X * 2).
If you are not sure, what your function is going to do, you can print it:
from fn import _
print (_ + 2) # "(x1) => (x1 + 2)"
print (_ + _ * _) # "(x1, x2, x3) => (x1 + (x2 * x3))"
_ will fail with ArityError (TypeError subclass) on inaccurate number of passed arguments. This is one more restrictions to ensure that you did everything right:
>>> from fn import _
>>> (_ + _)(1)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "fn/underscore.py", line 82, in __call__
raise ArityError(self, self._arity, len(args))
fn.underscore.ArityError: (_ + _) expected 2 arguments, got 1
Streams and infinite sequences declaration
Lazy-evaluated scala-style streams. Basic idea: evaluate each new element “on demand” and share calculated elements between all created iterators. Stream object supports << operator that means pushing new elements when it’s necessary.
Simplest cases:
from fn import Stream
s = Stream() << [1,2,3,4,5]
assert list(s) == [1,2,3,4,5]
assert s[1] == 2
assert list(s[0:2]) == [1,2]
s = Stream() << range(6) << [6,7]
assert list(s) == [0,1,2,3,4,5,6,7]
def gen():
yield 1
yield 2
yield 3
s = Stream() << gen << (4,5)
assert list(s) == [1,2,3,4,5]
Lazy-evaluated stream is useful for infinite sequences, i.e. fibonacci sequence can be calculated as:
from fn import Stream
from fn.iters import take, drop, map
from operator import add
f = Stream()
fib = f << [0, 1] << map(add, f, drop(1, f))
assert list(take(10, fib)) == [0,1,1,2,3,5,8,13,21,34]
assert fib[20] == 6765
assert list(fib[30:35]) == [832040,1346269,2178309,3524578,5702887]
High-level operations with functions
fn.F is a useful function wrapper to provide easy-to-use partial application and functions composition.
from fn import F, _
from operator import add, mul
# F(f, *args) means partial application
# same as functools.partial but returns fn.F instance
assert F(add, 1)(10) == 11
# F << F means functions composition,
# so (F(f) << g)(x) == f(g(x))
f = F(add, 1) << F(mul, 100)
assert list(map(f, [0, 1, 2])) == [1, 101, 201]
assert list(map(F() << str << (_ ** 2) << (_ + 1), range(3))) == ["1", "4", "9"]
You can find more examples for compositions usage in fn._ implementation source code.
fn.op.apply executes given function with given positional arguments in list (or any other iterable). fn.op.flip returns you function that will reverse arguments order before apply.
from fn.op import apply, flip
from operator import add, sub
assert apply(add, [1, 2]) == 3
assert flip(sub)(20,10) == -10
assert list(map(apply, [add, mul], [(1,2), (10,20)])) == [3, 200]
Itertools recipes
fn.iters module consists from two parts. First one is “unification” of lazy functionality for few functions to work the same way in Python 2+/3+:
map (returns itertools.imap in Python 2+)
filter (returns itertools.ifilter in Python 2+)
reduce (returns functools.reduce in Python 3+)
zip (returns itertools.izip in Python 2+)
range (returns xrange in Python 2+)
filterfalse (returns itertools.ifilterfalse in Python 2+)
zip_longest (returns itertools.izip_longest in Python 2+)
accumulate (backported to Python < 3.3)
Second part of module is high-level recipes to work with iterators. Most of them taken from Python docs and adopted to work both with Python 2+/3+. Such recipes as drop, takelast, droplast, splitat, splitby I have already submitted as docs patch which is review status just now.
take, drop
takelast, droplast
head, tail
consume
nth
padnone, ncycles
repeatfunc
grouper, powerset, pairwise
roundrobin
partition, splitat, splitby
flatten
iter_except
More information about use cases you can find in docstrings for each function in source code and in test cases.
Functional style for error-handling
fn.monad.Option represents optional values, each instance of Option can be either instance of Full or Empty. It provides you with simple way to write long computation sequences and get rid of many if/else blocks. See usage examples below.
Assume that you have Request class that gives you parameter value by its name. To get uppercase notation for non-empty striped value:
class Request(dict):
def parameter(self, name):
return self.get(name, None)
r = Request(testing="Fixed", empty=" ")
param = r.parameter("testing")
if param is None:
fixed = ""
else:
param = param.strip()
if len(param) == 0:
fixed = ""
else:
fixed = param.upper()
Hmm, looks ugly.. Update code with fn.monad.Option:
from operator import methodcaller
from fn.monad import optionable
class Request(dict):
@optionable
def parameter(self, name):
return self.get(name, None)
r = Request(testing="Fixed", empty=" ")
fixed = r.parameter("testing")
.map(methodcaller("strip"))
.filter(len)
.map(methodcaller("upper"))
.get_or("")
fn.monad.Option.or_call is good method for trying several variant to end computation. I.e. use have Request class with optional attributes type, mimetype, url. You need to evaluate “request type” using at least on attribute:
from fn.monad import Option
request = dict(url="face.png", mimetype="PNG")
tp = Option \
.from_value(request.get("type", None)) \ # check "type" key first
.or_call(from_mimetype, request) \ # or.. check "mimetype" key
.or_call(from_extension, request) \ # or... get "url" and check extension
.get_or("application/undefined")
Trampolines decorator
fn.recur.tco is a workaround for dealing with TCO without heavy stack utilization. Let’s start from simple example of recursive factorial calculation:
def fact(n):
if n == 0: return 1
return n * fact(n-1)
This variant works, but it’s really ugly. Why? It will utilize memory too heavy cause of recursive storing all previous values to calculate final result. If you will execute this function with big n (more then sys.getrecursionlimit()) CPython will fail with
>>> import sys
>>> fact(sys.getrecursionlimit() * 2)
... many many lines of stacktrace ...
RuntimeError: maximum recursion depth exceeded
Which is good, cause it prevents you from terrible mistakes in your code.
How can we optimize this solution? Answer is simple, lets transform function to use tail call:
def fact(n, acc=1):
if n == 0: return acc
return fact(n-1, acc*n)
Why this variant is better? Cause you don’t need to remember previous values to calculate final result. More about tail call optimizaion on Wikipedia. But… Python interpreter will execute this function the same way as previous one, so you won’t win nothing.
fn.recur.tco gives you mechanism to write “optimized a bit” tail call recursion (using “trampoline” approach):
from fn import recur
@recur.tco
def fact(n, acc=1):
if n == 0: return False, acc
return True, (n-1, acc*n)
@recur.tco is a decorator that execute your function in while loop and check output:
(False, result) means that we finished
(True, args, kwargs) means that we need to call function again with other arguments
(func, args, kwargs) to switch function to be executed inside while loop
Attention: be careful with mutable/immutable data structures processing.
Installation
To install fn.py, simply:
$ pip install fn
Or, if you absolutely must:
$ easy_install fn
You can also build library from source
$ git clone https://github.com/kachayev/fn.py.git
$ cd fn.py
$ python setup.py install
Work in progress
“Roadmap”:
Add to fn.op module foldl, foldr
Add to fn.iters module findelem, findindex
C-accelerator for most modules
Ideas to think about:
“Pipeline” notation for composition (back-order): F() >> list >> partial(map, int)
Curried function builder to simplify lambda arg1: lambda arg2: ...
Scala-style for-yield loop to simplify long map/filter blocks
Contribute
Check for open issues or open a fresh issue to start a discussion around a feature idea or a bug.
Fork the repository on Github to start making your changes to the master branch (or branch off of it).
Write a test which shows that the bug was fixed or that the feature works as expected.
History
27.01.2012
iters.accumulate - backported version for Python < 3.3
first implementation for monad.Option with tests and README samples
23.01.2012
fn.Stream slice is another fn.Stream
fn.Stream got new public method cursor to get position on next evaluated element
21.01.2012
Update documentation with special fn._ use cases for interactive shells
Move zipwith from fn.iters to fn.op
fn._ dump to string
18.01.2012
Added 22 itertools recipes to fn.iters
Documentation is converted to RST
17.01.2012
Unit tests coverage for fn.stream.Stream
_StreamIterator works fine both in Python 2/3
16.01.2012
Finished underscore module functionality
Test cases for all implemented modules/functions
Update in Readme file with several fixes
Get rid of F.flip classmethod in pref. for simple building blocks
Optimized version for fn.op.flip operator
14.01.2012
Simplest Stream implementation
Code samples for streams, labdas (_) and functions compositions
Plan, contribute section in readme file
13.01.2012
Full list of ideas on paper
Repository is created
Initial commit
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.