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:
- The same input always produces the same output.
- 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
- Avoid accidental modifications: Data will not be changed arbitrarily by other code.
- Lower state management costs: There is no need to track a complex modification history.
- Improve concurrency safety: Multiple threads reading immutable data usually do not require additional synchronization.
- Facilitate state comparison: Old and new states can be stored and compared independently.
- 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.
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:
Compose the two functions:
When the input is 5:
Mathematically, function composition is usually written as:
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:
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:
- Base case: determines the termination condition for the recursion.
- Recursive case: decomposes the problem into smaller subproblems.
For example, calculating a factorial:
Base case:
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