Functional programming in python

AN OVERVIEW OF FUNCTIONAL PROGRAMMING IN PYTHON Edward D. Weinberger, Ph.D, F.R.M. Adjunct Professor NYU Tandon School of Engineering edw@wpq-inc.com

ULTIMATE PURPOSE To avoid dysfunctional programming!

OUTLINE • Functional programming: definition and advantages • Functional programming: key concepts • Python support for functional programming: the basics and beyond • Potential pitfalls and best practices

FUNCTIONAL PROGRAMMING DEFINED “A programming paradigm that treats computation as the evaluation of mathematical functions, avoiding changes of state and mutable data”

IMPLICATIONS OF DEFINITION • Output values of functions must depend only on inputs, not on internal state variables • Calling a function twice with the same inputs results in the same output

“IMPERATIVE PROGRAMMING” NO-NO’s • For/While Loops • Internal “state” variables (e.g. variables assigned in __init__() and updated by other methods) • Re-assignment (mutability) of variables

OBVIOUS QUESTION: Why bother???

IMPERATIVE VERSION OF QUICKSORT def quicksort(array): indexes_stack = list() idx = (0, len(array) - 1) indexes_stack.append(idx) for idx in indexes_stack: elem_idx = idx[0] pivot_idx = idx[1] while pivot_idx > elem_idx: pivot = array[pivot_idx] elem = array[elem_idx] if elem > pivot: array[pivot_idx] = elem array[elem_idx] = array[pivot_idx - 1] array[pivot_idx - 1] = pivot pivot_idx -= 1 else: elem_idx += 1 boundar_low = idx[0] boundar_high = idx[1] if pivot_idx > 1 and boundar_low < pivot_idx - 1: indexes_stack.append((boundar_low, pivot_idx - 1)) if pivot_idx < len(array) -1 and pivot_idx + 1 < boundar_high: indexes_stack.append((pivot_idx + 1, boundar_high)) return array

FUNCTIONAL VERSION OF QUICKSORT def quicksort(lst): if len(lst) == 0: return lst pivots = list(filter(lambda x: x == lst[0], lst)) small = quicksort(list(filter(lambda x: x < lst[0], lst))) large = quicksort(list(filter(lambda x: x > lst[0], lst))) return small + pivots + large

OTHER ADVANTAGES (besides ease of reading/debugging) • May facilitate • Compiler optimization • Parallelization • Faster execution via memorization • Lazy evaluation • Academic studies of formal proofs of program correctness have made progress under functional programming assumptions

FUNCTIONAL PROGRAMMING: A FEW KEY CONCEPTS

PURE FUNCTIONS • Functions that • always return the same result, given the same argument, so sin(x) is pure, today() is impure • do not have “side effects” • Cannot use internal state to determine what result to return • Python functions may or may not be pure

REFERENTIAL TRANSPARENCY • Describes a function/expression that can be replaced by its value without changing the behavior of a program in which it is embedded (e.g. sin(x)+5) • Generally, an expression can only be referentially transparent if any functions used are pure

“HIGHER ORDER” FUNCTIONS • Functions that take other functions as inputs and/or outputs • Python examples: • Python’s sorted function takes a key parameter, the name of a function that returns a sort key • A GUI button object’s __init__() might be passed the name of the function to be executed when the button is clicked

PYTHON SUPPORT FOR FUNCTIONAL PROGRAMMING

SUPPORT FOR FP IN “EVERY DAY” PYTHON • Recursion • Lambda expressions • All functions are “first class functions”, i.e. function names can be • passed as arguments • assigned to variables • appear as elements of lists • etc.

PYTHON ITERABLES AND ITERATORS • An iterable is an object that defines either a __getitem__() or an __iter__() method • The built-in function iter(iterable) returns an iterator (also returned by generators) • Iterators define a (private) __next__() method, called by the built-in function next(), raising the StopIteration error when nothing is next

ITERABLE/ITERATOR EXAMPLE >>> aList = [1, 2] #need not be a list >>> aListIter = iter(aList) #possibly >>> next(aListIter)# lazy evaluation 1 >>> next(aListIter)# 2 >>> next(aListIter) StopIteration Traceback …

Returns an iterator which is the result of applying <function> (of one argument) to successive individual items supplied by <iterable> EXAMPLE: >>> list(map(lambda x: x*x,[1,3,5,7])) [1, 9, 25, 49] map(<function>, <iterable>)

MAP RETURNS AN ITERATOR >>> seq = map(lambda x: x*x, [1, 3, 5, 7]) >>> seq <map at 0x…> >>> next(seq) 1 >>> next(seq) 9

applies <function> (of two arguments) to the first two items supplied by <iterable>, thus “reducing” them to a single value. This result is supplied, along with the third item from <iterable> thus “reducing” all three items to a single value Note: reduce must be imported from the built-in library functools reduce(<function>, <iterable>)

WORKING WITH reduce >>> from functools import reduce >>> reduce(lambda x,y: x*y, range(1, 6)) 120 #The product of ((1*2)*3)*4)*5

Constructs an iterator for those elements of <iterable> for which <function> returns True Equivalent to the generator expression (for item in <iterable> item if <function>(item) ) filter(<function>, <iterable>)

WORKING WITH filter >>> isEven = lambda x: (x%2 == 0) >>> yetAnotherList = [12, 43, 33, 32, 31] >>> it = filter(isEven, yetAnotherList) >>> next(it) 12 >>> next(it) 32 >>> list(filter(isEven, yetAnotherList)) [12, 32]

AN EXTENDED EXAMPLE min_order = 100 invoice_totals = list( map(lambda x: x if x[1] >= min_order else (x[0], x[1] + 10), map(lambda x: (x[0],x[2] * x[3]), orders)))

WHAT ELSE IS THERE TO KNOW? • More jargon (see Wikipedia) • The operator, functools and itertools libraries • Various ideas about pitfalls/best practices

PITFALLS/BEST PRACTICES IN FUNCTIONAL PROGRAMMING

BIGGEST PITFALL: “It’s the new kid on the block! • After 60+ years, • Imperative programming (IP) is well understood • Lots of hardware and compiler support for IP • IP code has large code base

RECURSION IS PROBLEMATIC • Recursion is always relatively slow and memory intensive because of the many subroutine calls usually required • Python, in particular, only grudgingly supports recursion • Implementation not particularly fast • Finite recursion depth, even for tail recursion

FP “Update as you copy” PARADIGM PROBLEMATIC • The alternative to updating mutable variables is “update as you copy” • “Update as you copy” leads to memory bloat • Can be difficult to keep track of what’s going on if nested objects are being copied/updated

PURE FUNCTIONS AND I/O DON’T REALLY MIX • Python functions such as input()are not even close to referentially transparent! • Internal state variables needed for buffered reads/writes

BEST PRACTICES SPECIFIC TO FUNCTIONAL PROGRAMMING • Use map, reduce, filter, and other library functions in place of recursion if possible • Cleanly separate pure functions from intrinsically impure functions (such as I/O) • Combine related functions in a class and use inheritance (yes, FP and OO do mix!)

BEST PRACTICES APPLICABLE TO ALL PYTHON PROGRAMMING • “short and sweet” functions, doing one thing well (1 or 2 ISO/ANSI 24x80 screens) • Take advantage of Python’s polymorphism • Don’t pack too much into a single line of code • Use descriptive variable names

BEST PRACTICES PER “THE ZEN OF PYTHON” • “… practicality beats purity” • “Readability counts” • “If an implementation is hard to explain, it’s a bad idea” • “If an implementation is easy to explain, it might be a good idea”

RECAP • Functional programming: definition and advantages • Functional programming: key concepts • Python support for functional programming: the basics and beyond • Potential pitfalls and best practices

Functional programming in python

More Related Content

What's hot

Similar to Functional programming in python

Recently uploaded

Functional programming in python