Functional Programming
map/filter, lru_cache, recursion, and tail recursion.
10 questions
JuniorTheoryVery commonWhat is a higher-order function?
What is a higher-order function?
A function that takes one or more functions as arguments and/or returns a function. It is possible because functions are first-class objects in Python. Examples: map, filter, sorted(key=...), and decorators.
Common mistakes
- ✗Confusing arity (number of parameters) with being higher-order
- ✗Thinking recursion makes a function higher-order
- ✗Believing only built-ins, not
deffunctions, can be higher-order
Follow-up questions
- →How does a decorator use the higher-order property to wrap a function?
- →Why can you pass a function to
sortedvia thekeyparameter?
JuniorTheoryCommonWhat do map, filter, and reduce do?
What do map, filter, and reduce do?
map(f, seq) applies f to each element; filter(pred, seq) keeps elements where pred is truthy — both return lazy iterators in Python 3. reduce(f, seq[, init]), from functools, folds a sequence to one value.
Common mistakes
- ✗Expecting
map/filterto return lists rather than lazy iterators in Python 3 - ✗Calling
reducewithoutfrom functools import reducein Python 3 - ✗Thinking
filterkeeps elements where the predicate is False
Follow-up questions
- →How does a generator expression often replace
mapandfiltertogether? - →What role does the optional
initargument play inreduce?
JuniorTheoryCommonWhat is functional programming, and how does Python support it?
What is functional programming, and how does Python support it?
A paradigm treating computation as evaluating functions, favouring pure functions and immutability over mutable state. Python supports it partially: first-class functions, lambda, comprehensions, functools, itertools.
Common mistakes
- ✗Calling Python a pure functional language when it merely supports functional features
- ✗Equating functional style with using
lambdaonly, ignoring pure functions and immutability - ✗Forgetting that comprehensions and
functools/itertoolsare core functional tools
Follow-up questions
- →What makes a function pure, and why does purity aid testing and reasoning?
- →Which Python features push you away from a purely functional style?
JuniorTheoryCommonWhat is recursion, and what two cases does it need?
What is recursion, and what two cases does it need?
Recursion is a function calling itself. It needs a base case (a terminating condition that returns without recursing) and a recursive case (calling itself on a smaller input toward the base). No base case means it loops forever.
Common mistakes
- ✗Omitting or mis-defining the base case, causing infinite recursion
- ✗Not shrinking the input toward the base case on each call
- ✗Confusing recursion with an ordinary loop that has no termination rule
Follow-up questions
- →What error does CPython raise when recursion runs too deep?
- →How can you rewrite a recursive function as an iterative loop?
MiddleTheoryCommonWhat does the itertools module provide, and why use it?
What does the itertools module provide, and why use it?
Lazy, memory-efficient iterator building blocks. count, cycle and repeat are infinite; chain joins iterables; islice slices lazily without materializing; groupby, product and combinations handle grouping and combinatorics. They stream their input instead of building lists.
Common mistakes
- ✗Calling
list()on an infinite iterator likecount()orcycle() - ✗Expecting
groupbyto group globally without sorting the input first - ✗Thinking
itertoolsresults are reusable lists rather than one-shot iterators
Follow-up questions
- →Why must input be pre-sorted for
itertools.groupbyto group as expected? - →How does
islicediffer from regular slicingseq[a:b]on a generator?
MiddleTheoryCommonWhat does functools.lru_cache do?
What does functools.lru_cache do?
A decorator that memoizes a function — caching results keyed by the call arguments and returning the stored result on repeats, evicting least-recently-used entries past maxsize. Arguments must be hashable.
Common mistakes
- ✗Caching impure functions whose results depend on side effects or external state
- ✗Decorating a function with unhashable arguments like lists or dicts
- ✗Forgetting that
maxsizebounds the cache and evicts old entries
Follow-up questions
- →Why must the cached function's arguments be hashable?
- →How does
lru_cachespeed up a naive recursive Fibonacci function?
MiddleTheoryOccasionalWhat is currying, and how does functools.partial relate?
What is currying, and how does functools.partial relate?
Currying turns a multi-argument function into a chain of single-argument functions, each returning the next. Partial application — functools.partial(f, a) — fixes some arguments and returns a callable taking the rest.
Common mistakes
- ✗Conflating currying (one arg at a time) with calling all arguments at once
- ✗Believing
functools.partialmutates the original function instead of wrapping it - ✗Thinking currying and partial application are unrelated to specialising functions
Follow-up questions
- →How would you implement currying manually with nested functions or closures?
- →When is
functools.partialclearer than writing alambda?
MiddleTheoryOccasionalWhat does the operator module provide, and when is it used?
What does the operator module provide, and when is it used?
Function versions of Python's operators and lookups — add, mul, lt, plus itemgetter, attrgetter, methodcaller. They are faster, picklable replacements for tiny lambdas, used mainly as key= in sorted/max or in functools.reduce, e.g. sorted(rows, key=itemgetter(1)).
Common mistakes
- ✗Thinking
operatordoes low-level/hardware work rather than wrapping Python operators - ✗Confusing it with operator overloading via dunder methods
- ✗Assuming
itemgetter/attrgettermutate rather than just read
Follow-up questions
- →Why is
operator.itemgetter(1)preferred overlambda r: r[1]as a sort key? - →Why can
itemgetterbe pickled when an equivalent lambda cannot?
MiddleTheoryOccasionalWhat is tail recursion, and how do you write it?
What is tail recursion, and how do you write it?
Tail recursion is when the recursive call is the function's last action, with nothing left to compute after it returns — usually achieved with an accumulator parameter carrying the running result, e.g. fact(n-1, acc*n).
Common mistakes
- ✗Calling
return n * fact(n-1)tail-recursive despite the pending multiplication - ✗Confusing the call's position in the body with it being the last action
- ✗Believing an accumulator removes the need for a base case
Follow-up questions
- →How does an accumulator turn a non-tail factorial into a tail-recursive one?
- →Why does tail recursion help only in languages that implement TCO?
SeniorTheoryRareDoes CPython optimize tail calls?
Does CPython optimize tail calls?
No. CPython performs no tail-call optimization — a deliberate choice to keep full tracebacks — so even tail-recursive calls grow the stack and hit the recursion limit (default ~1000, sys.setrecursionlimit).
Common mistakes
- ✗Assuming CPython performs TCO like Scheme or some functional languages
- ✗Thinking
sys.setrecursionlimitenables optimization rather than just raising the cap - ✗Believing tail-recursive code is immune to
RecursionErrorin CPython
Follow-up questions
- →Why did CPython's designers reject TCO in favour of full tracebacks?
- →How does a trampoline let you run deep tail recursion without growing the stack?
