Bytebook Compiler

Functions & Modules

Lambda, map/filter & Recursion

Small anonymous functions with lambda, functional tools map, filter, sorted and reduce, and recursive functions with base cases, memoisation and recursion limits.

4 min read5 runnable examples4-question quiz

lambda

A lambda is a one-expression anonymous function: lambda parameters: expression.

Python
square = lambda x: x * x
add = lambda a, b: a + b
print(square(9), add(3, 4))

students = [("Asha", 88), ("Ravi", 95), ("Meera", 79)]
print(sorted(students, key=lambda s: s[1], reverse=True))
print(max(students, key=lambda s: s[1])[0])
Output
81 7
[('Ravi', 95), ('Asha', 88), ('Meera', 79)]
Ravi
Try it Yourself

Use lambdas for short throwaway functions, usually as a key= argument. If it needs a name or more than one line, write a def.

map, filter and reduce

Function Does Comprehension equivalent
map(f, xs) applies f to every item [f(x) for x in xs]
filter(pred, xs) keeps items where pred is true [x for x in xs if pred(x)]
functools.reduce(f, xs) folds items into one value a loop with an accumulator
Python
from functools import reduce

nums = [1, 2, 3, 4, 5, 6]
print(list(map(lambda x: x ** 2, nums)))
print(list(filter(lambda x: x % 2 == 0, nums)))
print(reduce(lambda acc, x: acc * x, nums))          # 6! = 720
print(list(map(int, "10 20 30".split())))            # the classic input idiom
print(list(map(str.upper, ["c", "dsa", "python"])))
Output
[1, 4, 9, 16, 25, 36]
[2, 4, 6]
720
[10, 20, 30]
['C', 'DSA', 'PYTHON']
Try it Yourself

map and filter return lazy iterators; wrap them in list() to see all values.

Recursion

Recursion in Python works exactly as in C: a base case and a recursive case.

Python
def factorial(n):
    return 1 if n <= 1 else n * factorial(n - 1)

def power(base, exp):
    if exp == 0:
        return 1
    half = power(base, exp // 2)
    return half * half * (base if exp % 2 else 1)

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))     # recurse into sub-lists
        else:
            result.append(item)
    return result

def permutations(s):
    if len(s) <= 1:
        return [s]
    return [s[i] + p for i in range(len(s)) for p in permutations(s[:i] + s[i + 1:])]

print(factorial(20))
print(power(2, 64))
print(flatten([1, [2, [3, 4], 5], [[6]], 7]))
print(permutations("abc"))
Output
2432902008176640000
18446744073709551616
[1, 2, 3, 4, 5, 6, 7]
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Try it Yourself

Memoisation with lru_cache

Naive recursive Fibonacci recomputes the same values exponentially many times. functools.lru_cache remembers results, turning it into O(n):

Python
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_fast(n):
    return n if n < 2 else fib_fast(n - 1) + fib_fast(n - 2)

calls = 0
def fib_counted(n):
    global calls
    calls += 1
    return n if n < 2 else fib_counted(n - 1) + fib_counted(n - 2)

fib_counted(20)
print("calls for naive fib(20):", calls)
print("fib(90) with lru_cache:", fib_fast(90))
Output
calls for naive fib(20): 21891
fib(90) with lru_cache: 2880067194370816120
Try it Yourself

This is dynamic programming in one decorator line; the idea is explained fully in Dynamic Programming.

Recursion limit

Python limits recursion depth (about 1000 by default) to protect the stack:

Python
import sys
print(sys.getrecursionlimit())

def countdown(n):
    return 0 if n == 0 else countdown(n - 1)

print(countdown(500))
print(countdown(5000))
Output
1000
0
Traceback (most recent call last):
  File "main.py", line 8, in <module>
    print(countdown(5000))
          ~~~~~~~~~^^^^^^
  File "main.py", line 5, in countdown
    return 0 if n == 0 else countdown(n - 1)
                            ~~~~~~~~~^^^^^^^
  File "main.py", line 5, in countdown
    return 0 if n == 0 else countdown(n - 1)
                            ~~~~~~~~~^^^^^^^
  File "main.py", line 5, in countdown
    return 0 if n == 0 else countdown(n - 1)
                            ~~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
Try it Yourself

For deep recursion, rewrite the function with a loop (or, carefully, raise the limit with sys.setrecursionlimit).

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    What does list(map(lambda x: x + 1, [1, 2, 3])) return?

  2. 2

    What does list(filter(lambda w: len(w) > 3, ["hi", "hello", "hey", "howdy"])) return?

  3. 3

    What does @lru_cache do to a recursive function?

  4. 4

    What happens when recursion goes deeper than Python's limit?

Esc
↑↓ move↵ open