Repository files navigation

Despite the fact that Python is not pure-functional programminglanguage, it's multi-paradigm PL and it gives you enough freedom to takecredits from functional programming approach. There are theoretical andpractical advantages to the functional style:

• Formal provability
• Modularity
• Composability
• Ease of debugging and testing

Fn.py library provides you with missing "batteries" to get maximumfrom functional approach even in mostly-imperative program.

More about functional approach from my Pycon UA 2012 talks:FunctionalProgramming withPython.

fromfnimport_fromfn.opimportzipwithfromitertoolsimportrepeatassertlist(map(_*2,range(5)))== [0,2,4,6,8]assertlist(filter(_<10, [9,10,11]))== [9]assertlist(zipwith(_+_)([0,1,2],repeat(10)))== [10,11,12]

More examples of using_ you can find intestcasesdeclaration (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 likefrom fn import _ as X (and then write functions likeX * 2).

If you are not sure, what your function is going to do, you can print it:

fromfnimport_print (_+2)# "(x1) => (x1 + 2)"print (_+_*_)# "(x1, x2, x3) => (x1 + (x2 * x3))"

_ will fail withArityError (TypeError subclass) on inaccurate number of passed arguments. This is one more restrictions to ensure that you did everything right:

>>>fromfnimport_>>> (_+_)(1)Traceback (mostrecentcalllast):File"<stdin>",line1,in<module>File"fn/underscore.py",line82,in__call__raiseArityError(self,self._arity,len(args))fn.underscore.ArityError: (_+_)expected2arguments,got1

Attention: Persistent data structures are under active development.

Persistent data structure is a data structure that always preserves the previous version of itself when it is modified (more formal information onWikipedia). Each operation with such data structure yields a new updated structure instead of in-place modification (all previous versions are potentially available or GC-ed when possible).

Lets take a quick look:

>>>fromfn.immutableimportSkewHeap>>>s1=SkewHeap(10)>>>s2=s1.insert(20)>>>s2<fn.immutable.heap.SkewHeapobjectat0x10b14c050>>>>s3=s2.insert(30)>>>s3<fn.immutable.heap.SkewHeapobjectat0x10b14c158># <-- other object>>>s3.extract()(10,<fn.immutable.heap.SkewHeapobjectat0x10b14c050>)>>>s3.extract()# <-- s3 isn't changed(10,<fn.immutable.heap.SkewHeapobjectat0x10b11c052>)

If you think I'm totally crazy and it will work despairingly slow, just give it 5 minutes. Relax, take a deep breath and read about few techniques that make persistent data structures fast and efficient:structural sharing andpath copying.

To see how it works in "pictures", you can check great slides from Zach Allaun's talk (StrangeLoop 2013):"Functional Vectors, Maps And Sets In Julia".

And, if you are brave enough, go and read:

• Chris Okasaki, "Purely Functional Data Structures" (Amazon)
• Fethi Rabhi and Guy Lapalme, "Algorithms: A Functional Programming Approach" (Amazon)

Available immutable data structures infn.immutable module:

• LinkedList: most "obvious" persistent data structure, used as building block for other list-based structures (stack, queue)
• Stack: wraps linked list implementation with well-known pop/push API
• Queue: uses two linked lists and lazy copy to provide O(1) enqueue and dequeue operations
• Deque (in progress):"Confluently Persistent Deques via DataStructural Bootstrapping"
• Deque based onFingerTree data structure (see more information below)
• Vector: O(log32(n)) access to elements by index (which is near-O(1) for reasonable vector size), implementation is based onBitmappedTrie, almost drop-in replacement for built-in Pythonlist
• SkewHeap: self-adjusting heap implemented as a binary tree with specific branching model, uses heap merge as basic operation, more information -"Self-adjusting heaps"
• PairingHeap:"The Pairing-Heap: A New Form of Self-Adjusting Heap"
• Dict (in progress): persistent hash map implementation based onBitmappedTrie
• FingerTree (in progress):"Finger Trees: A Simple General-purpose Data Structure"

Use appropriate doc strings to get more information about each data structure as well as sample code.

To get more clear vision of how persistent heaps work (SkewHeap andPairingHeap), you can look at slides from my talk"Union-based heaps" (with analyzed data structures definitions in Python and Haskell).

Note. Most functional languages use persistent data structures as basic building blocks, well-known examples are Clojure, Haskell and Scala. Clojure community puts much effort to popularize programming based on the idea of data immutability. There are few amazing talk given by Rich Hickey (creator of Clojure), you can check them to find answers on both questions "How?" and "Why?":

• "The Value of Values"
• "Persistent Data Structures and Managed References"

Lazy-evaluated Scala-style streams. Basic idea: evaluate each newelement "on demand" and share calculated elements between all createditerators.Stream object supports<< operator that means pushingnew elements when it's necessary.

Simplest cases:

fromfnimportStreams=Stream()<< [1,2,3,4,5]assertlist(s)== [1,2,3,4,5]asserts[1]==2assertlist(s[0:2])== [1,2]s=Stream()<<range(6)<< [6,7]assertlist(s)== [0,1,2,3,4,5,6,7]defgen():yield1yield2yield3s=Stream()<<gen<< (4,5)assertlist(s)== [1,2,3,4,5]

Lazy-evaluated stream is useful for infinite sequences, i.e. fibonaccisequence can be calculated as:

fromfnimportStreamfromfn.itersimporttake,drop,mapfromoperatorimportaddf=Stream()fib=f<< [0,1]<<map(add,f,drop(1,f))assertlist(take(10,fib))== [0,1,1,2,3,5,8,13,21,34]assertfib[20]==6765assertlist(fib[30:35])== [832040,1346269,2178309,3524578,5702887]

fn.recur.tco is a workaround for dealing with TCO without heavy stack utilization. Let's start from simple example of recursive factorial calculation:

deffact(n):ifn==0:return1returnn*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 bign (more thansys.getrecursionlimit()) CPython will fail with

>>>importsys>>>fact(sys.getrecursionlimit()*2)...manymanylinesofstacktrace ...RuntimeError:maximumrecursiondepthexceeded

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:

deffact(n,acc=1):ifn==0:returnaccreturnfact(n-1,acc*n)

Why this variant is better? Cause you don't need to remember previous values to calculate final result. More abouttail call optimization on Wikipedia. But... Python interpreter will execute this function the same way as previous one, so you won't win anything.

fn.recur.tco gives you mechanism to write "optimized a bit" tail call recursion (using "trampoline" approach):

fromfnimportrecur@recur.tcodeffact(n,acc=1):ifn==0:returnFalse,accreturnTrue, (n-1,acc*n)

@recur.tco is a decorator that execute your function inwhile 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

The last variant is really useful, when you need to switch callable inside evaluation loop. Good example for such situation is recursive detection if given number is odd or even:

>>>fromfnimportrecur>>>@recur.tco...defeven(x):...ifx==0:returnFalse,True...returnodd, (x-1,)...>>>@recur.tco...defodd(x):...ifx==0:returnFalse,False...returneven, (x-1,)...>>>printeven(100000)True

Attention: be careful with mutable/immutable data structures processing.

fn.uniform provides you with "unification"of lazy functionality for few functions to work the same way in Python2+/3+:

• map (returnsitertools.imap in Python 2+)
• filter (returnsitertools.ifilter in Python 2+)
• reduce (returnsfunctools.reduce in Python 3+)
• zip (returnsitertools.izip in Python 2+)
• range (returnsxrange in Python 2+)
• filterfalse (returnsitertools.ifilterfalse in Python 2+)
• zip_longest (returnsitertools.izip_longest in Python 2+)
• accumulate (backported to Python < 3.3)

fn.iters is high-level recipes to work with iterators. Mostof them taken fromPythondocsand adopted to work both with Python 2+/3+. Such recipes asdrop,takelast,droplast,splitat,splitby I have alreadysubmitted asdocs patch which isreview status just now.

• take,drop
• takelast,droplast
• head (alias:first),tail (alias:rest)
• second,ffirst
• compact,reject
• every,some
• iterate
• consume
• nth
• padnone,ncycles
• repeatfunc
• grouper,powerset,pairwise
• roundrobin
• partition,splitat,splitby
• flatten
• iter_except
• first_true

More information about use cases you can find in docstrings for eachfunction insourcecode andintestcases.

fn.F is a useful function wrapper to provide easy-to-use partialapplication and functions composition.

fromfnimportF,_fromoperatorimportadd,mul# F(f, *args) means partial application# same as functools.partial but returns fn.F instanceassertF(add,1)(10)==11# F << F means functions composition,# so (F(f) << g)(x) == f(g(x))f=F(add,1)<<F(mul,100)assertlist(map(f, [0,1,2]))== [1,101,201]assertlist(map(F()<<str<< (_**2)<< (_+1),range(3)))== ["1","4","9"]

It also give you move readable in many cases "pipe" notation to deal with functions composition:

fromfnimportF,_fromfn.itersimportfilter,rangefunc=F()>> (filter,_<6)>>sumassertfunc(range(10))==15

You can find more examples for compositions usage infn._implementationsourcecode.

fn.op.apply executes given function with given positional argumentsin list (or any other iterable).fn.op.flip returns you functionthat will reverse arguments order before apply.

fromfn.opimportapply,flipfromoperatorimportadd,subassertapply(add, [1,2])==3assertflip(sub)(20,10)==-10assertlist(map(apply, [add,mul], [(1,2), (10,20)]))== [3,200]

fn.op.foldl andfn.op.foldr are folding operators. Each accepts function with arity 2 and returns function that can be used to reduce iterable to scalar: from left-to-right and from right-to-left in case offoldl andfoldr respectively.

fromfnimportop,_folder=op.foldr(_*_,1)assert6==op.foldl(_+_)([1,2,3])assert6==folder([1,2,3])

Use case specific for right-side folding is:

fromfn.opimportfoldr,callassert100==foldr(call,0 )([lambdas:s**2,lambdak:k+10])assert400==foldr(call,10)([lambdas:s**2,lambdak:k+10])

fn.func.curried is a decorator for building curried functions, for example:

>>>fromfn.funcimportcurried>>>@curried...defsum5(a,b,c,d,e):...returna+b+c+d+e...>>>sum5(1)(2)(3)(4)(5)15>>>sum5(1,2,3)(4,5)15

fn.monad.Option represents optional values, each instance ofOption can be either instance ofFull orEmpty. It provides you with simple way to write long computation sequences and get rid of manyif/else blocks. See usage examples below.

Assume that you haveRequest class that gives you parameter value by its name. To get uppercase notation for non-empty striped value:

classRequest(dict):defparameter(self,name):returnself.get(name,None)r=Request(testing="Fixed",empty="   ")param=r.parameter("testing")ifparamisNone:fixed=""else:param=param.strip()iflen(param)==0:fixed=""else:fixed=param.upper()

Hmm, looks ugly.. Update code withfn.monad.Option:

fromoperatorimportmethodcallerfromfn.monadimportoptionableclassRequest(dict):@optionabledefparameter(self,name):returnself.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 haveRequest class with optional attributestype,mimetype,url. You need to evaluate "request type" using at least one attribute:

fromfn.monadimportOptionrequest=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")

To installfn.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

"Roadmap":

• fn.monad.Either to deal with error logging
• C-accelerator for most modules

Ideas to think about:

• Scala-style for-yield loop to simplify long map/filter blocks

1. Check for open issues or open a fresh issue to start a discussionaround a feature idea or a bug.
2. Fork the repository on Github to start making your changes to themaster branch (or branch off of it).
3. Write a test which shows that the bug was fixed or that the featureworks as expected.

• Twitter:@kachayev
• Email: kachayev <at> gmail.com