Skip to main content

Functional Programming

Introduction​

This chapter looks at Python's functional programming features: lambda expressions (small, unnamed inline functions), higher-order functions (functions that take or return other functions), and recursion (a function that calls itself to solve a smaller instance of the same problem).

These techniques complement Python's object-oriented features rather than replacing them — functions are first-class citizens in Python, so they can be passed around, stored in variables, and returned from other functions just like any other value.

Concepts​

Lambda expressions​

is_even = lambda n: n % 2 == 0

print(is_even(4))    # True
print(is_even(7))    # False

Higher-order functions​

def negate(f):
    def negated(*args):
        return not f(*args)
    return negated

is_odd = negate(is_even)
print(is_odd(3))   # True
print(is_odd(4))   # False

Recursion​

def nth(n, items):
    if n == 0:
        return items[0]
    return nth(n - 1, items[1:])

my_list = [100, 101, 102, 103, 104, 105, 106]
print(nth(4, my_list))   # 104

Built-in higher-order functions​

numbers = [1, 2, 3, 4, 5]

print(list(map(lambda n: n * 2, numbers)))          # [2, 4, 6, 8, 10]
print(list(filter(lambda n: n % 2 == 0, numbers)))  # [2, 4]

from functools import reduce
print(reduce(lambda acc, n: acc + n, numbers))       # 15

Examples​

is_even = lambda n: n % 2 == 0

def negate(f):
    def negated(*args):
        return not f(*args)
    return negated

is_odd = negate(is_even)

print(is_even(10), is_odd(10))
print(is_even(7), is_odd(7))


def nth(n, items):
    if n == 0:
        return items[0]
    return nth(n - 1, items[1:])

my_list = [100, 101, 102, 103, 104, 105, 106]
print(nth(4, my_list))

Challenges​

1. An "is even" lambda​

  • Write a lambda expression that acts as an "is even" predicate — it takes a number and returns True/False.
  • Call it with an even number and an odd number to confirm the result.
💡 Show Answer
is_even = lambda n: n % 2 == 0

print(is_even(4))    # True
print(is_even(7))    # False

2. A negate() higher-order function​

  • Define a higher-order function negate(f) that takes a predicate function f and returns a new function producing the opposite (inverted) result.
  • Define is_odd in terms of is_even and negate.
  • Verify is_odd returns the correct result for both odd and even numbers.
💡 Show Answer
is_even = lambda n: n % 2 == 0

def negate(f):
    def negated(*args):
        return not f(*args)
    return negated

is_odd = negate(is_even)

print(is_odd(3))    # True
print(is_odd(4))    # False

3. Recursive nth() function​

  • Write a function nth(n, items) that returns the nth item of a list, using recursion (no loops or mutable state).
  • Use list slicing (items[0] for the first item, items[1:] for the rest) to implement the recursion.
💡 Show Answer
def nth(n, items):
    if n == 0:
        return items[0]
    return nth(n - 1, items[1:])

my_list = [100, 101, 102, 103, 104, 105, 106]
print(nth(4, my_list))   # 104

4. A recursive binary tree​

  • Define a Node class holding a piece of data, a pointer to a left node, and a pointer to a right node.
  • Define a BinaryTree class holding a pointer to the head node, with add() and display() methods.
  • Optionally, implement remove() too.
💡 Show Answer
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class BinaryTree:
    def __init__(self):
        self.head = None

    def add(self, data):
        if self.head is None:
            self.head = Node(data)
        else:
            self._add_recursive(self.head, data)

    def _add_recursive(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = Node(data)
            else:
                self._add_recursive(node.left, data)
        else:
            if node.right is None:
                node.right = Node(data)
            else:
                self._add_recursive(node.right, data)

    def display(self):
        self._display_recursive(self.head)
        print()

    def _display_recursive(self, node):
        if node is not None:
            self._display_recursive(node.left)
            print(node.data, end=" ")
            self._display_recursive(node.right)


tree = BinaryTree()
for value in [5, 3, 8, 1, 4, 7, 9]:
    tree.add(value)

tree.display()   # 1 3 4 5 7 8 9