Higher-Order Functions – Haskell

In Haskell, functions are more than just sequences of instructions; they are fundamental building blocks that can be manipulated like any other data. One of the most powerful concepts in functional programming, especially in Haskell, is the higher-order function. Higher-order functions are functions that can take other functions as arguments or return functions as results. This concept allows for extremely flexible and reusable code, enabling us to write more abstract, modular, and expressive programs.

In this article, we’ll dive into what higher-order functions are, why they’re useful, and some examples of how to use them effectively in Haskell.

What Are Higher-Order Functions?

A higher-order function is a function that either:

1. Takes one or more functions as input.
2. Returns a function as output.

Higher-order functions treat functions as first-class citizens, meaning functions can be passed around, stored in variables, and manipulated like any other data. This enables us to write more generalized and reusable code.

In Haskell, higher-order functions are everywhere. Some of the most commonly used functions, such as map, filter, and foldl, are higher-order functions that enable powerful transformations on data structures.

Why Use Higher-Order Functions?

Higher-order functions offer several advantages:

• Code Reusability: Higher-order functions allow you to write generic, reusable code by abstracting behavior.
• Modularity: By passing in functions as arguments, you can create modular code that separates core logic from specific implementations.
• Expressiveness: Higher-order functions enable concise and readable code, especially when used with function composition.

Common Higher-Order Functions in Haskell

Let’s explore some commonly used higher-order functions in Haskell and understand how they work.

1. map

The map function takes a function and a list, then applies the function to each element in the list, returning a new list with the results. It has the following type signature:

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

The map function takes two things:

1. A function that transforms a value of type a into a value of type b (written as (a -> b)).
2. A list of values of type a (written as [a]).

The result is a new list where each value from the original list has been transformed by the function into a value of type b. This new list has the type [b].

Breaking Down the Type Signature

• (a -> b): This represents a function that takes an input of type a and produces an output of type b.
• [a]: This is a list where each item is of type a.
• [b]: This is the result—a new list where each item is of type b, generated by applying the given function to each element of the original list.

Here’s an example of how map works:

double :: Int -> Int
double x = x * 2

map double [1, 2, 3, 4]  -- Result: [2, 4, 6, 8]

In this example, map takes the double function and applies it to each element in the list [1, 2, 3, 4], producing [2, 4, 6, 8].

2. filter

The filter function takes a predicate/condition (a function that returns True or False) and a list, returning a list of elements that satisfy the predicate. It has the following type signature:

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

The filter function is used to pick out certain elements from a list based on a condition. It takes two things:

1. A predicate (conditional) function that checks a condition for each element in the list (written as (a -> Bool)). This function takes an item of type a and returns True or False (a Bool).
2. A list of elements of type a (written as [a]).

The result is a new list that includes only the elements for which the predicate function returned True.

Breaking Down the Type Signature

• (a -> Bool): This is the predicate function, which takes a value of type a and returns a Bool (True or False).
• [a]: This is the list of elements we want to filter, where each element is of type a.
• Result [a]: This is the resulting list, containing only those elements from the original list that passed the condition (for which the predicate returned True).

Here’s an example of how filter works:

isEven :: Int -> Bool
isEven x = x `mod` 2 == 0

filter isEven [1, 2, 3, 4, 5, 6]  -- Result: [2, 4, 6]

Here, filter applies isEven to each element in the list and returns only the elements that satisfy the condition, resulting in [2, 4, 6].

3. foldl and foldr

foldl and foldr are two functions for reducing lists to a single value. They each take a binary function, an initial accumulator value, and a list. The difference between them is in the direction they process the list:

• foldl processes the list from the left, or beginning.
• foldr processes the list from the right, or end.

Their type signatures are:

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

The foldl function is used to reduce a list to a single value by combining its elements in a specific way. It takes three things:

1. A binary function (written as (b -> a -> b)) that combines each element of the list with an accumulated result.
2. An initial value of type b to start the accumulation process.
3. A list of elements of type a to process.

The result is a single value of type b, which is produced by applying the function to each element in the list, moving from the left (beginning) to the right (end) of the list.

Breaking Down the Type Signature

• (b -> a -> b): This is the binary function that takes two arguments—a running total (of type b) and the next list item (of type a)—and produces a new running total (also of type b).
• b: This is the initial value of the accumulator, used as the starting point.
• [a]: This is the list of elements to be processed, where each element is of type a.
• Result b: This is the final accumulated result after processing the entire list.

Let’s use foldl to sum up a list of numbers:

sumList :: [Int] -> Int
sumList = foldl (+) 0

sumList [1, 2, 3, 4]  -- Result: 10

Here, foldl starts with an initial value of 0 and applies (+) to each element in the list, accumulating the result to get 10.

4. zipWith

The zipWith function combines two lists by applying a function to corresponding elements. Its type signature is:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

The zipWith function takes three things:

1. A function that combines two elements (written as (a -> b -> c)). This function takes one element from the first list and one element from the second list and produces a new element.
2. A first list of elements of type a (written as [a]).
3. A second list of elements of type b (written as [b]).

The result is a new list where each element is of type c. This new list is created by applying the function to each corresponding pair of elements from the two input lists. The length of the resulting list will be as long as the shorter of the two input lists.

Breaking Down the Type Signature

• (a -> b -> c): This is a function that takes two inputs, one of type a (from the first list) and one of type b (from the second list), and returns a value of type c.
• [a]: This is the first list, where each element has type a.
• [b]: This is the second list, where each element has type b.
• Result [c]: This is the resulting list, where each element is the result of applying the function to corresponding pairs from the two lists.

For example, we can use zipWith to add corresponding elements of two lists:

result = zipWith (+) [1, 2, 3] [4, 5, 6]  -- Result: [5, 7, 9]

Here, zipWith applies (+) to each pair of elements from the two lists, producing [5, 7, 9].

Creating Your Own Higher-Order Functions

You can easily create your own higher-order functions by accepting functions as arguments or returning functions as results. Here’s an example of a higher-order function that applies a function twice to a given value:

applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)

Now you can use applyTwice with any function that takes a single argument:

result = applyTwice (* 2) 3  -- Result: 12

In this case, applyTwice (* 2) 3 first applies (* 2) to 3, giving 6, and then applies (* 2) again to 6, giving 12.

Higher-Order Functions and Function Composition

In Haskell, you can compose functions using the (.) operator, which takes two functions and combines them into a single function. This is particularly powerful when working with higher-order functions, allowing you to build complex operations by chaining simpler ones.

For example, if you want to create a function that doubles each element in a list and then filters out odd numbers, you can do so using composition:

processList :: [Int] -> [Int]
processList = filter even . map (* 2)

result = processList [1, 2, 3, 4, 5]  -- Result: [4, 8]

Here, processList first doubles each element in the list (using map (* 2)) and then filters out odd numbers, resulting in [4, 8].

Practical Examples of Higher-Order Functions

Higher-order functions are incredibly useful for transforming data, applying different rules, and making code more modular. Here are some real-world scenarios where they shine:

1. Transforming Data in a Pipeline

Suppose you’re working with a list of temperatures in Celsius and you want to:

1. Convert each temperature to Fahrenheit.
2. Filter out temperatures below 50°F.
3. Find the average.

This can be done with higher-order functions:

toFahrenheit :: Float -> Float
toFahrenheit c = (c * 9/5) + 32

average :: [Float] -> Float
average temps = sum temps / fromIntegral (length temps)

processTemperatures :: [Float] -> Float
processTemperatures = average . filter (> 50) . map toFahrenheit

result = processTemperatures [0, 10, 20, 30]  -- Result: 59.0 (average of [50, 68, 86])

This creates a data-processing pipeline that’s easy to read and modify, thanks to the use of higher-order functions.

2. Building Custom Operations

Let’s create a higher-order function that applies a list of functions to a value. This could be useful when you want to apply a series of transformations to data:

applyAll :: [a -> a] -> a -> a
applyAll fs x = foldl (\acc f -> f acc) x fs

result = applyAll [(* 2), (+ 3), (`div` 5)] 10  -- Result: 4

Here, applyAll takes a list of functions and applies each one in sequence to the value 10.

Summary

Higher-order functions are a fundamental aspect of Haskell’s functional programming style, allowing us to work with functions in flexible and expressive ways. They enable:

• Reusable and modular code by allowing functions to be passed as arguments and returned as results.
• Concise and expressive transformations of data through functions like map, filter, and fold.
• Powerful data-processing pipelines that can be easily composed and modified.

Learning to use higher-order functions well is a key step to mastering Haskell. Once you’re comfortable with them, you’ll find that they open up new ways to think about and solve problems, making your Haskell code clean, abstract, and highly reusable.

💡 Helpful References

Learn You a Haskell - Higher Order Functions 
https://learnyouahaskell.github.io/higher-order-functions.html