Back to series
· 10 min read

Functional Programming (FP)


I. What Is Functional Programming

Functional Programming (FP) is a programming paradigm that treats computation as the evaluation of mathematical functions.

It emphasizes expressing computational logic through functions, organizing data transformation, business rules, and program behavior into composable functions.

Unlike imperative programming, which mainly describes how a program executes, functional programming focuses more on the computational relationships between expressions and on how input data is transformed into output results.

For example, calculating the total price of a set of products.

Imperative implementation:

prices = [100, 200, 300]

total = 0
for price in prices:
    total += price

print(total)

The program explicitly describes:

  • Creating an accumulator variable.
  • Iterating over the data.
  • Modifying the accumulator variable.
  • Outputting the final result.

Functional-style implementation:

from functools import reduce

prices = [100, 200, 300]

total = reduce(lambda acc, price: acc + price, prices, 0)

print(total)

Here, the data reduction process is expressed through a function, progressively combining the multiple values in the list into a single result.

Both approaches accomplish the calculation. The core of functional programming is not simply using map, reduce, or Lambda, but rather establishing a stricter design approach around functions, data, and side effects.

II. The Core Ideas of Functional Programming

Functional programming contains several interrelated concepts.

Core Concept English Name Main Role
Pure Function Pure Function Ensures the same input yields the same output
Immutability Immutability Avoids modifying data in place
First-class Function First-class Function Treats functions as ordinary values
Higher-order Function Higher-order Function Accepts or returns other functions
Referential Transparency Referential Transparency Expressions can be replaced by equivalent results
Function Composition Function Composition Combines multiple functions into a larger computation
Declarative Programming Declarative Programming Describes goals and data transformation relationships
Lazy Evaluation Lazy Evaluation Evaluates expressions only when needed
Side-effect Control Side-effect Control Isolates state modification and external interaction
Recursion Recursion Expresses repeated computation through function calls

Among these, pure functions, immutability, and side-effect control are the foundation for understanding functional programming.

III. Pure Functions

3.1 Definition of a Pure Function

A pure function is one of the most important concepts in functional programming.

A function that satisfies the following two conditions can generally be called a pure function:

  1. The same input always produces the same output.
  2. Executing the function produces no observable side effects.

For example:

def add(a, b):
    return a + b

No matter how many times it is called:

add(10, 20)
add(10, 20)
add(10, 20)

The result is always 30.

The function depends only on the parameters passed in, does not read external mutable state, and does not modify the external environment.

3.2 Non-pure Functions

Below is a function that depends on external state:

counter = 0

def increment():
    global counter
    counter += 1
    return counter

Calling it:

print(increment())
print(increment())

Output:

1
2

The same function called at different times produces different results.

The reason is that the function depends on the external variable counter and modifies that variable.

Another example:

import random

def generate_number():
    return random.randint(1, 100)

Even though it does not modify external variables, the function depends on the internal state of the random number generator, so it cannot simply be regarded as a pure function.

3.3 Types of Side Effects

A side effect refers to any observable influence on the external environment beyond the return value that occurs during the execution of a function.

Common side effects include:

Type Example
Modifying external variables Modifying global variables
Modifying shared objects Modifying a passed-in list or dictionary
File operations Writing files, deleting files
Network operations Sending HTTP requests
Database operations Inserting, updating, deleting data
Logging output Writing to a logging system
Random behavior Using a random number generator
Time dependency Reading the current time
Exceptional states Modifying external system state

For example:

def add_item(items, item):
    items.append(item)
    return items

This function modifies the list passed in by the caller, so it has side effects.

It can be rewritten to create a new list:

def add_item(items, item):
    return items + [item]

The original list is not modified, making the function's behavior easier to predict.

3.4 Advantages of Pure Functions

Pure functions have the following advantages:

Predictability

The same input produces the same output, without needing to consider external state.

Testability

They do not depend on databases, file systems, or global variables, making unit testing simpler.

Cacheability

For the same input, computed results can be cached to avoid repeated computation.

Parallelizability

Pure functions avoid race conditions caused by shared-state modification, making safe parallel execution easier.

Composability

Dependencies between functions are clear, making it possible to build complex computation pipelines.

Note that pure functions do not mean a program cannot access databases or networks at all. Real systems usually isolate pure computation logic from external interactions and handle side effects at system boundaries.

IV. Immutability

4.1 Definition of Immutability

Immutability means that after a data object is created, its state is no longer modified in place.

A distinction should be made between:

  • Variable rebinding.
  • Modification of an object's own state.

For example:

name = "Alice"
name = "Bob"

Here, the variable name is rebound to another string object; the original string is not modified.

Strings are immutable objects in Python.

Now consider a list:

numbers = [1, 2, 3]
numbers.append(4)

Here, the original list object is modified directly, which is a mutable operation.

4.2 Mutable and Immutable Data

Data Type Mutability in Python
int Immutable
float Immutable
str Immutable
tuple Immutable container
list Mutable
dict Mutable
set Mutable

Note: Although a tuple is an immutable container, if it contains mutable objects such as lists, the inner objects can still be modified.

data = (1, [2, 3])

data[1].append(4)

print(data)

Output:

(1, [2, 3, 4])

Therefore, an immutable container does not mean the entire object structure is deeply immutable.

4.3 Handling Immutable Data

The functional style tends to create new data rather than directly modifying the original data.

numbers = [1, 2, 3]

new_numbers = numbers + [4]

print(numbers)
print(new_numbers)

Output:

[1, 2, 3]
[1, 2, 3, 4]

This approach reduces the problems caused by multiple functions sharing the same mutable object.

4.4 Advantages of Immutability

  1. Avoid accidental modifications: Data will not be changed arbitrarily by other code.
  2. Lower state management costs: There is no need to track a complex modification history.
  3. Improve concurrency safety: Multiple threads reading immutable data usually do not require additional synchronization.
  4. Facilitate state comparison: Old and new states can be stored and compared independently.
  5. Support time-travel debugging: Historical states are retained, making it easier to trace problems back.

Immutability does not mean the entire object must be copied every time. Real languages and runtimes can use techniques such as structural sharing and persistent data structures to reduce copying overhead.

5. First-Class Functions

5.1 What Is a First-Class Function

If a programming language treats functions as first-class citizens, it usually means that functions can be treated like ordinary data:

  • Assigned to variables.
  • Passed as function arguments.
  • Returned as function return values.
  • Stored in data structures.
  • Created and used at runtime.

Languages such as Python, JavaScript, Go, and Rust all support first-class function capabilities in different forms.

5.2 Assigning Functions to Variables

def add(a, b):
    return a + b

operation = add

print(operation(10, 20))

operation holds a reference to the function object and can be called just like the original function.

5.3 Functions as Parameters

def calculate(a, b, operation):
    return operation(a, b)

def add(x, y):
    return x + y

def multiply(x, y):
    return x * y

print(calculate(10, 20, add))
print(calculate(10, 20, multiply))

Output:

30
200

calculate does not care whether addition or multiplication is actually performed; it is only responsible for organizing the calculation process.

5.4 Functions as Return Values

def create_multiplier(factor):
    def multiply(value):
        return value * factor

    return multiply

double = create_multiplier(2)
triple = create_multiplier(3)

print(double(10))
print(triple(10))

Output:

20
30

Here, create_multiplier returns a function object.

This capability is an important foundation for higher-order functions and closures.

6. Higher-Order Functions

6.1 Definition of Higher-Order Functions

A higher-order function is a function that satisfies any one of the following conditions:

  • It takes one or more functions as parameters.
  • It returns a function as its result.

For example:

def apply_twice(func, value):
    return func(func(value))

def square(x):
    return x * x

print(apply_twice(square, 2))

Execution result:

16

apply_twice takes the function square as a parameter, so it is a higher-order function.

6.2 map: Mapping Transformation

map applies a function to each element in an iterable, producing transformed results.

numbers = [1, 2, 3, 4]

result = map(lambda x: x * 2, numbers)

print(list(result))

Output:

[2, 4, 6, 8]

Its computation logic can be represented as:

flowchart LR
    A["Original data"] --> B["Read elements one by one"]
    B --> C["Apply transformation function"]
    C --> D["Generate transformed result"]
    D --> E["Form result sequence"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style E fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

6.3 filter: Conditional Filtering

filter selects data based on a condition function.

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

result = filter(lambda x: x % 2 == 0, numbers)

print(list(result))

Output:

[2, 4, 6]

6.4 reduce: Reduction Computation

reduce gradually reduces multiple elements to a single result.

```python from functools import reduce numbers = [1, 2, 3, 4] result = reduce(lambda acc, x: acc + x, numbers, 0) print(result) ```

Output:

```text 10 ```

Reduction process:

```mermaid flowchart TD A["Initial accumulator: 0"] --> B["Read the first element: 1"] B --> C["Accumulate to: 1"] C --> D["Read the second element: 2"] D --> E["Accumulate to: 3"] E --> F["Read the third element: 3"] F --> G["Accumulate to: 6"] G --> H["Read the fourth element: 4"] H --> I["Final result: 10"] style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976 style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155 style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155 style D fill:#E5F4EC,stroke:#A3CBB5,color:#334155 style E fill:#F3EDFC,stroke:#C4B2E3,color:#334155 style F fill:#E5F4EC,stroke:#A3CBB5,color:#334155 style G fill:#F3EDFC,stroke:#C4B2E3,color:#334155 style H fill:#E5F4EC,stroke:#A3CBB5,color:#334155 style I fill:#FFF5DE,stroke:#E8D29A,color:#334155 linkStyle default stroke:#A3B8AC,stroke-width:1.5px ```

map, filter and reduce are common data-processing tools in functional programming, but they are not the whole of functional programming.

7. Function Composition

7.1 What Is Function Composition

Function composition is the process of connecting multiple simple functions to build more complex computational logic.

Suppose there are two functions:

f(x)=x+10
g(x)=x\times 2

Compose the two functions:

h(x)=g(f(x))

When the input is 5:

h(5)=g(15)=30

Mathematically, function composition is usually written as:

(g\circ f)(x)=g(f(x))

Note the order of execution here: f runs first, then g.

7.2 Implementing Function Composition in Code

```python def add_ten(x): return x + 10 def multiply_two(x): return x * 2 def compose(f, g): return lambda x: g(f(x)) operation = compose(add_ten, multiply_two) print(operation(5)) ```

Output:

```text 30 ```

The composition function can be abstracted further:

```python def compose(*functions): def composed(value): result = value for func in reversed(functions): result = func(result) return result return composed ```

This implementation assumes arguments are passed in left-to-right reading order, while execution applies the functions from right to left.

7.3 Advantages of Function Composition

  • Split complex business logic into multiple small functions.
  • Each function is responsible for only one clear transformation.
  • Existing functions can be reused.
  • Reduce dependencies between functions.
  • Make it easier to test and debug in isolation.

Function composition is especially well suited to scenarios such as data processing, text processing, compiler pipelines, and request handling.

8. Referential Transparency

8.1 What Is Referential Transparency

If an expression can be replaced by the value it evaluates to without changing the program's behavior, then that expression has referential transparency.

For example:

```python def add(a, b): return a + b result = add(10, 20) * 2 ```

Because add(10, 20) always yields 30, it can be equivalently replaced with:

```python result = 30 * 2 ```

The program's result does not change.

8.2 The Value of Referential Transparency

Referential transparency makes programs easier to:

  • Expression substitution.
  • Code refactoring.
  • Result caching.
  • Parallel computation.
  • Compiler optimization.
  • Mathematical reasoning.

8.3 The Relationship Between Referential Transparency and Pure Functions

The two are closely related, but they cannot simply be regarded as completely identical concepts.

Pure functions emphasize a function's inputs, outputs, and side-effect characteristics.

Referential transparency emphasizes whether an expression can be replaced equivalently by its result.

In the usual context of functional programming, pure function calls are an important foundation for achieving referential transparency.

However, when observing program behavior, semantic boundaries still need to be made explicit. For example, rounding errors in floating-point operations, exceptions, non-terminating computations, and resource consumption can all affect whether expression substitution is truly equivalent.

9. Lazy Evaluation

9.1 What Is Lazy Evaluation

Lazy evaluation means that an expression is not evaluated immediately; instead, it is executed only when its result is actually needed.

Its opposite is strict evaluation, also called eager evaluation.

For example:

numbers = [x * 2 for x in range(1000000)]

A list comprehension immediately generates the entire list.

In contrast, a generator expression:

numbers = (x * 2 for x in range(1000000))

does not immediately compute all elements; instead, it generates them one by one during iteration.

for number in numbers:
    print(number)

9.2 Execution Process of Lazy Evaluation

flowchart TD
    A["Define computation expression"] --> B["Create lazy computation object"]
    B --> C{"Is the current result needed?"}
    C -->|"No"| D["Do not execute computation for now"]
    D --> C
    C -->|"Yes"| E["Execute the corresponding computation"]
    E --> F["Produce the current result"]
    F --> G{"Are more results needed?"}
    G -->|"Yes"| E
    G -->|"No"| H["End computation"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style D fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style E fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style F fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style G fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style H fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

9.3 Advantages of Lazy Evaluation

Reduced memory usage

There is no need to store all intermediate results at once.

Support for infinite sequences

You can define theoretically infinite data sequences and generate elements only when needed.

Avoiding unnecessary computation

If certain results will never be used, the corresponding computations do not need to be performed.

Building computation pipelines

Multiple transformation operations can be chained on demand, avoiding the creation of large numbers of intermediate collections.

9.4 Costs of Lazy Evaluation

Lazy evaluation is not necessarily faster than eager evaluation.

Potential problems include:

  • Computation is deferred until the usage stage, so errors may be exposed later.
  • The same lazy expression may be evaluated repeatedly, depending on the implementation.
  • Debugging the call chain becomes more complex.
  • Dependence on external mutable state can make behavior difficult to predict.
  • Caching intermediate results may also increase memory consumption.

Note that Python's generators and iterators support on-demand computation, but Python is not a language that adopts a fully lazy evaluation strategy.

10. Recursion and Functional Programming

Recursion is a common way of expressing control flow in functional programming.

It handles smaller-scale problems by having a function call itself.

10.1 Basic Structure of Recursion

A recursive function usually contains two parts:

  1. Base case: determines the termination condition for the recursion.
  2. Recursive case: decomposes the problem into smaller subproblems.

For example, calculating a factorial:

n!=n\times(n-1)!

Base case:

0!=1

Python implementation:

def factorial(n):
    if n == 0:
        return 1

    return n * factorial(n - 1)

print(factorial(5))

Output:

120

10.2 Recursive Execution Process

flowchart TD
    A["factorial(5)"] --> B["factorial(4)"]
    B --> C["factorial(3)"]
    C --> D["factorial(2)"]
    D --> E["factorial(1)"]
    E --> F["factorial(0)"]
    F --> G["Return 1"]
    G --> H["Return 1"]
    H --> I["Return 2"]
    I --> J["Return 6"]
    J --> K["Return 24"]
    K --> L["Return 120"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style E fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style F fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style G fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style I fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style J fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style K fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style L fill:#FFF5DE,stroke:#E8D29A,color:#334155
    linkStyle default stroke:#A3B8AC,stroke-width:1.5px