First-Class and Higher-Order Functions

Two of the most important concepts in functional programming are first-class functions and higher-order functions. Understanding these is essential for A-Level Computer Science and forms the basis of many functional programming techniques.

---

First-Class Functions

A language has first-class functions (also called first-class objects or first-class citizens) if functions can be treated like any other value. Specifically, functions can be:

1. Assigned to variables.
2. Passed as arguments to other functions.
3. Returned as results from other functions.
4. Stored in data structures (lists, dictionaries, etc.).

Examples in Python

# 1. Assigning a function to a variable
def greet(name):
    return f"Hello, {name}!"

say_hello = greet  # Assign function to variable
print(say_hello("Alice"))  # Output: Hello, Alice!

# 2. Passing a function as an argument
def apply(func, value):
    return func(value)

result = apply(greet, "Bob")
print(result)  # Output: Hello, Bob!

# 3. Returning a function from a function
def make_multiplier(factor):
    def multiplier(x):
        return x * factor
    return multiplier

double = make_multiplier(2)
triple = make_multiplier(3)
print(double(5))  # Output: 10
print(triple(5))  # Output: 15

# 4. Storing functions in a list
operations = [double, triple]
for op in operations:
    print(op(4))  # Outputs: 8, then 12

Examples in Haskell

-- Assigning a function to a name
double = (*2)

-- Passing a function as an argument
applyFunc f x = f x
applyFunc double 5    -- Result: 10

-- Returning a function
makeAdder n = (+ n)
addFive = makeAdder 5
addFive 3             -- Result: 8

In Haskell, all functions are first-class by default.

---

Higher-Order Functions

A higher-order function is a function that does at least one of the following:

1. Takes one or more functions as arguments.
2. Returns a function as its result.

Higher-order functions are powerful because they allow you to abstract common patterns of computation.

Examples

Higher-Order Function	What It Does
map	Applies a function to every element of a list
filter	Selects elements from a list that satisfy a predicate
reduce / fold	Combines all elements of a list into a single value
sort with key	Sorts elements using a comparison function

map in Python

numbers = [1, 2, 3, 4, 5]
squared = list(map(lambda x: x ** 2, numbers))
# squared = [1, 4, 9, 16, 25]

map in Haskell

squared = map (^2) [1, 2, 3, 4, 5]
-- squared = [1, 4, 9, 16, 25]

filter in Python