Map, Filter, and Reduce (Fold)

Map, filter, and reduce (called fold in Haskell) are the three most important higher-order functions in functional programming. They provide powerful, concise ways to transform and process lists without writing explicit loops.

---

Map

Map applies a function to every element of a list, producing a new list of the same length with the transformed values.

Concept

map f [a, b, c, d] = [f(a), f(b), f(c), f(d)]

Python

# Double every number
numbers = [1, 2, 3, 4, 5]
doubled = list(map(lambda x: x * 2, numbers))
# doubled = [2, 4, 6, 8, 10]

# Convert temperatures from Celsius to Fahrenheit
celsius = [0, 20, 37, 100]
fahrenheit = list(map(lambda c: c * 9/5 + 32, celsius))
# fahrenheit = [32.0, 68.0, 98.6, 212.0]

# Get lengths of strings
words = ["hello", "world", "hi"]
lengths = list(map(len, words))
# lengths = [5, 5, 2]

Haskell

-- Double every number
doubled = map (*2) [1, 2, 3, 4, 5]
-- doubled = [2, 4, 6, 8, 10]

-- Convert to uppercase
import Data.Char (toUpper)
upper = map toUpper "hello"
-- upper = "HELLO"

-- Square every number
squares = map (^2) [1..5]
-- squares = [1, 4, 9, 16, 25]

Key Properties of Map

• The output list has the same number of elements as the input list.
• The order of elements is preserved.
• Each element is independently transformed — the function does not see other elements.

---

Filter

Filter selects elements from a list that satisfy a given predicate (a function that returns True or False), producing a new list containing only those elements.

Concept

filter p [a, b, c, d] = [elements where p(element) is True]

Python

# Keep only even numbers
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
evens = list(filter(lambda x: x % 2 == 0, numbers))
# evens = [2, 4, 6, 8, 10]

# Keep strings longer than 3 characters
words = ["hi", "hello", "hey", "greetings", "yo"]
long_words = list(filter(lambda w: len(w) > 3, words))
# long_words = ["hello", "greetings"]

# Remove negative numbers
values = [-5, 3, -1, 7, -2, 9]
positives = list(filter(lambda x: x >= 0, values))
# positives = [3, 7, 9]

Haskell

-- Keep only even numbers
evens = filter even [1..10]
-- evens = [2, 4, 6, 8, 10]

-- Keep numbers greater than 5
big = filter (>5) [1..10]
-- big = [6, 7, 8, 9, 10]

-- Keep lowercase letters
import Data.Char (isLower)
lowers = filter isLower "Hello World"
-- lowers = "elloorld"

Key Properties of Filter

• The output list has fewer or equal elements compared to the input.
• The order of elements is preserved.
• Elements are not modified — they are either included or excluded.

---

Reduce (Fold)

Reduce (called fold in Haskell) combines all elements of a list into a single value by repeatedly applying a function. It takes an initial accumulator value and a combining function.

Concept

reduce f init [a, b, c, d] = f(f(f(f(init, a), b), c), d)

Python (functools.reduce)

from functools import reduce

# Sum all numbers
numbers = [1, 2, 3, 4, 5]
total = reduce(lambda acc, x: acc + x, numbers, 0)
# total = 15