What are higher order functions? Can you provide an example in Haskell?

Higher-order functions are functions that can take other functions as arguments or return them as results, or both. In functional programming languages like Haskell, higher-order functions are a powerful and flexible feature that enables the creation of more modular, reusable, and concise code.

To illustrate higher-order functions in Haskell, let’s first consider a simple example: the ‘map‘ function. The ‘map‘ function takes a function and a list as its arguments and applies the given function to each element of the list, returning a new list with the results.

Here’s the type signature and a possible implementation of ‘map‘ in Haskell:

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

In this type signature, ‘a‘ and ‘b‘ are type variables, and ‘(a -> b)‘ indicates a function that takes an argument of type ‘a‘ and returns a value of type ‘b‘. Thus, ‘map‘ can work with functions and lists of various types as long as they match the given type signature.

Let’s look at an example using ‘map‘ in Haskell. Suppose we want to square every element in a list of integers. We could accomplish this by defining a function ‘square‘ and then using ‘map‘ to apply it to a list of integers:

square :: Int -> Int
square x = x * x

squaredList :: [Int] -> [Int]
squaredList xs = map square xs

In this case, we can even write the ‘squaredList‘ function more concisely using partial function application:

squaredList :: [Int] -> [Int]
squaredList = map square

Another example of a higher-order function in Haskell is ‘filter‘, which takes a predicate function (returns ‘True‘ or ‘False‘) and a list, and returns a new list containing only those elements that satisfy the predicate:

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

Using ‘filter‘, we can easily define a function that returns a list of even numbers:

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

evenNumbers :: [Int] -> [Int]
evenNumbers = filter isEven

In summary, higher-order functions in Haskell are functions that can accept other functions as arguments or return them. They allow for more modular, reusable, and concise code. Some common examples of higher-order functions in Haskell include ‘map‘, ‘filter‘, and ‘fold‘ functions.