Functional Programming in Practice

A higher-order function is a function that either:

• Takes a function as an argument, or
• Returns a function as its result (or both)

Higher-order functions are central to functional programming. They allow the separation of a pattern of computation from the specific operation being applied.

Examples:

-- apply takes a function and a value; applies the function
apply f x = f x

-- twice applies a function two times
twice f x = f (f x)
twice (+3) 5  -- evaluates to 11  (5+3=8, 8+3=11)

-- compose returns a new function (composition)
compose g f = \x -> g (f x)

The standard higher-order functions map, filter, and fold are the most commonly examined.

map f list applies a function f to every element of a list and returns a new list containing the results.

map :: (a -> b) -> [a] -> [b]

Type: takes a function from a to b, a list of a, returns a list of b.

Examples:

map (*2) [1, 2, 3, 4]       -- [2, 4, 6, 8]
map even [1, 2, 3, 4]       -- [False, True, False, True]
map length ["cat", "dog", "elephant"]  -- [3, 3, 8]
map (+10) []                -- []

The original list is not modified — map returns a new list. This is functional programming's immutability in action.

filter pred list returns a new list containing only the elements of list for which the predicate function pred returns True.

filter :: (a -> Bool) -> [a] -> [a]

Examples:

filter even [1, 2, 3, 4, 5, 6]     -- [2, 4, 6]
filter (>10) [3, 15, 7, 22, 1]     -- [15, 22]
filter (/= 'a') "banana"            -- "bnn"
filter even []                      -- []

pred must be a function that takes one argument and returns Bool. Partial application is often used to create predicates: (>10) is \x -> x > 10.

fold (also called reduce) processes a list by repeatedly applying a function to an accumulator and each list element, ultimately producing a single value.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> [a] -> b

Parameters: function f, initial value (accumulator), list.

foldr (fold right) example — sum a list:

foldr (+) 0 [1, 2, 3, 4]
= 1 + (2 + (3 + (4 + 0)))
= 10

foldr example — build a list:

foldr (:) [] [1, 2, 3]   -- [1, 2, 3]  (reconstructs the list)

foldl example — product:

foldl (*) 1 [1, 2, 3, 4]
= ((((1 * 1) * 2) * 3) * 4)
= 24

fold generalises many common patterns: sum, product, maximum, count, string concatenation, and list construction.

In functional programming, a list is defined recursively as either:

• The empty list: []
• A head (first element) prepended to a tail (the rest of the list): head : tail

[1, 2, 3, 4]  is equivalent to  1 : 2 : 3 : 4 : []

Standard list operations:

Operation	Haskell	Result
Return head (first element)	head [1, 2, 3]	1
Return tail (all but first)	tail [1, 2, 3]	[2, 3]
Test for empty list	null []	True
Return length	length [1, 2, 3]	3
Construct empty list	[]	[]
Prepend item	4 : [3, 5]	[4, 3, 5]
Append item	[3, 5] ++ [7]	[3, 5, 7]

Recursive list processing pattern:

-- Manually reimplementing sum
mySum []     = 0
mySum (x:xs) = x + mySum xs

The pattern (x:xs) matches a non-empty list, binding x to the head and xs to the tail. This is how most recursive list functions are structured.

Worked example — double all even numbers in a list:

doubleEvens xs = map (*2) (filter even xs)

-- Or using composition:
doubleEvens = map (*2) . filter even

doubleEvens [1, 2, 3, 4, 5, 6]  -- [4, 8, 12]

Worked example — count elements satisfying a predicate:

countWhere pred xs = length (filter pred xs)

countWhere even [1, 2, 3, 4, 5]   -- 2
countWhere (>10) [5, 15, 3, 20]   -- 2

Worked example — sum of squares:

sumOfSquares xs = foldr (+) 0 (map (^2) xs)

sumOfSquares [1, 2, 3, 4]   -- 1 + 4 + 9 + 16 = 30

1. Confusing map and filter

map transforms every element — the output list has the same length as the input. filter selects elements — the output list may be shorter. A question asking to "keep only even numbers" requires filter; a question asking to "double all numbers" requires map.

2. Getting fold direction wrong

foldr processes the list from right to left (last element first, accumulator on the right). foldl processes from left to right. For associative operations like + and *, both give the same result. For non-associative operations (e.g. subtraction, list construction), the direction matters.

3. Calling head or tail on an empty list

head [] and tail [] are errors in Haskell — undefined for the empty list. Correct recursive functions must handle the base case [] before applying head/tail.

4. Confusing the : and <ins> operators

: prepends a single element to a list: 4 : [3, 5] = [4, 3, 5]. </ins> concatenates two lists: [4] <ins> [3, 5] = [4, 3, 5]. Using </ins> with a single element on the left works but is less efficient; : is O(1), ++ is O(n).