Higher-Order Functions

Higher-order functions (HOFs) are functions that take other functions as arguments or return functions as results. They are a powerful abstraction tool in functional programming.

See also: Functions and Equations, Lists and List Comprehensions, Pattern Matching and Recursion, Functors and Applicatives, Polymorphism, Evaluation Strategies

Core Concepts

Definition

A higher-order function is a function that satisfies at least one of these criteria:

• Takes one or more functions as arguments
• Returns a function as its result

Benefits

• Abstracts common patterns
• Reduces code duplication
• Enables functional composition
• Makes code more concise and readable

Common Higher-Order Functions on Lists

map

Applies a function to every element in a list:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

Examples:

map (+1) [1, 2, 3]      -- [2, 3, 4]
map reverse ["abc", "def"]  -- ["cba", "fed"]
map (^ 2) [1..5]        -- [1, 4, 9, 16, 25]

filter

Retains elements that satisfy a predicate:

filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
  | p x       = x : filter p xs
  | otherwise = filter p xs

Examples:

filter even [1..10]          -- [2, 4, 6, 8, 10]
filter (> 5) [1, 9, 2, 8, 3] -- [9, 8]
filter isPrime [1..20]       -- [2, 3, 5, 7, 11, 13, 17, 19]

Folds (foldr and foldl)

Folds reduce a list to a single value by applying a binary function:

Right Fold (foldr)

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)

Right fold associates to the right: f x1 (f x2 (f x3 ... (f xn acc)))

Examples:

foldr (+) 0 [1, 2, 3, 4]  -- 10 (1 + (2 + (3 + (4 + 0))))
foldr (:) [] [1, 2, 3]     -- [1, 2, 3] (1 : (2 : (3 : [])))
foldr max 0 [1, 5, 3, 2]   -- 5

Left Fold (foldl)

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

Left fold associates to the left: f (... f (f (f acc x1) x2) x3 ...) xn

Examples:

foldl (+) 0 [1, 2, 3, 4]  -- 10 (((0 + 1) + 2) + 3) + 4)
foldl (flip (:)) [] [1, 2, 3]  -- [3, 2, 1] (reverses the list)
foldl max 0 [1, 5, 3, 2]   -- 5

Differences Between foldl and foldr

1. Associativity:

   • foldl is left-associative
   • foldr is right-associative

2. Laziness:

   • foldr can work on infinite lists when the combining function is lazy in its second argument
   • foldl always needs to traverse the entire list

3. Stack Safety:

   • foldl can cause stack overflow on large lists (use foldl' from Data.List instead)
   • foldr can be more stack-efficient for operations that short-circuit

zipWith

Combines two lists element-wise using a binary function:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith _ [] _ = []
zipWith _ _ [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys

Examples:

zipWith (+) [1, 2, 3] [4, 5, 6]       -- [5, 7, 9]
zipWith (*) [1, 2, 3, 4] [10, 20, 30] -- [10, 40, 90]
zipWith (,) [1, 2, 3] ['a', 'b', 'c'] -- [(1,'a'), (2,'b'), (3,'c')]

Function Composition

Function composition combines two functions to form a new function:

(.) :: (b -> c) -> (a -> b) -> (a -> c)
(f . g) x = f (g x)

Examples:

(length . filter even) [1..10]     -- 5
(reverse . map toUpper) "h

tally x :: Int -> Maybe String
| x < 0 = Nothing
| x == 0 = ""
| Just $ unwords (replicate (div x 5)  ("||||\\") ) ++ [ replicate snd ( (divMod x 5) ) "|" | (divMod x 5) /= 0 ]

tally :: Int -> Maybe String
tally n
  | n <  0    = Nothing
  | n == 0    = Just ""
  | otherwise = Just $ unwords parts
  where
    (fives, rest) = n `divMod` 5
    clusters      = replicate fives "||||\\"
    remainder     = replicate rest "|"
    parts         = clusters ++ [remainder | rest /= 0]
 

 
data Rectangle = Rectangle Int Int
 
x = Rectangle 5 9
 
data Rectangle = Rectangle { 
	width :: Int
	height :: Int
}
 
fun x = 
	width