BT
x Your opinion matters! Please fill in the InfoQ Survey about your reading habits!

Fn.py: Enjoy Functional Programming in Python

Posted by Alexey Kachayev on Feb 25, 2013 |

Despite the fact that Python is not a pure-functional programming language, it's multi-paradigm and it gives you enough freedom to take advantage of the functional programming approach. There are theoretical and practical advantages to the functional style (you can find this list in Python documentation):

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

Although this list is descriptive enough, I really like description of advantage of functional programming that was given by Michael O. Church in his article “Functional programs rarely rot”. I’ve talked about using functional approach in Python at Pycon UA 2012: Functional Programming with Python and I mentioned there many problems that you’ll probably discover soon trying to write readable and maintainable functional code in Python.

Library fn.py was created in order to deal with these problems. While it’s impossible to resolve all problems, the library provides you with missing "batteries" to get maximum value from functional approach even in mostly-imperative program. What will you find under the hood?

Scala-style lambdas definition

Syntax for creating lambda functions in Python is really verbose, just compare:

Python

map(lambda x: x*2, [1,2,3])

Scala

List(1,2,3).map(_*2)

Clojure

(map #(* % 2) '(1 2 3))

Haskell

map (2*) [1,2,3]

Fn.py provides special _ object to simplify lambda syntax (inspired by Scala).

from fn import _

assert (_ + _)(10, 5) = 15
assert list(map(_ * 2, range(5))) == [0,2,4,6,8]
assert list(filter(_ < 10, [9,10,11])) == [9]

There are many other cases where you can use _: all arithmetic operations, attributes resolving, method calling, slicing. 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))"

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.

Lazy-evaluated stream is a powerful abstraction to deal with infinite sequences. Let’s see how the fibonacci sequence can be calculated in functional programming languages:

Haskell

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Clojure

(def fib (lazy-cat [0 1] (map + fib (rest fib))))

Scala

def fibs: Stream[Int] = 
     0 #:: 1 #:: fibs.zip(fibs.tail).map{case (a,b) => a + b} 

Now you can do the same thing in Python:

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]

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 optimization 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. The same approach is used for example in Clojure and main idea is to expand sequence of functional calls into while loop.

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

Functional style for error-handling

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. It represents optional values, each instance of Option can be either instance of Full or Empty (inspired by Scala Option). It provides you with a simple way to write long computation sequences and get rid of many if/else blocks.

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 one 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")

Something else?

I described only the small part of library functionality. Also you can find and use:

  • 22 additional itertools recipes to extend functionality of built-in module
  • iterators unification for Python 2 and Python 3 (range, map, filter etc) which is really useful when working on cross-version library
  • easy syntax for functional composition and partial function application
  • additional operators to work with high-ordered functions (apply, flip etc)

Work in progress

Since publishing this library on Github I’ve got many reviews, ideas and suggestions from communities as well as patches and fixes. I continue working on enhancements for existing functionality and new features. In closest roadmap:

  • More operators to work with iterables, i.e. foldl, foldr
  • More monads, i.e. fn.monad.Either to deal with error logging
  • C-accelerator for most modules
  • Curried function builder to simplify lambda arg1: lambda arg2: ...
  • More documentations, more tests, more examples

Links

If you want to find more information about library you can use following resources:

About the Author

Alexey Kachayev is a snappy programmer-fanatic, open-source community activist, frequent speaker at different technology conferences, CTO at Kitapps Inc. Alexey is most experienced in Python, Erlang, Clojure and functional programming (Haskell, Lisp). His main interests are distributed applications, cloud computing, real-time web, compilers theory. Alexey contributed to CPython interpretator and Storm (real-time data processor).

Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Tell us what you think

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread
Community comments

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Discuss

Educational Content

General Feedback
Bugs
Advertising
Editorial
InfoQ.com and all content copyright © 2006-2014 C4Media Inc. InfoQ.com hosted at Contegix, the best ISP we've ever worked with.
Privacy policy
BT