REVISED: Monday, February 12, 2024
1. INTRODUCTION
A function is called higher order if it takes a function as an argument or returns a function as a result. In Haskell, we refer to functions that take other functions as arguments and return new functions as combinators.
Higher order functions taking functions as arguments include map and filter.
The term curried is normally used for higher order functions that take their arguments one at a time and return a function as a result.
Haskell higher order functions can be used to define Embedded Domain Specific Languages (EDSLs).
2. MAP
map applies a function to every element of a list.
2.1. MAP DEFINED USING LIST COMPREHENSION
Defining map using list comprehension makes it easy to see how map applies a function f x to every element of a list of xs:
-- Functions passed to other functions are written with their type declarations surrounded by parentheses; i.e., (a -> b).
-- 1st argument is a function that takes an "a" and returns a "b".
map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]
2.2. MAP DEFINED USING RECURSION
Haskell programmers never use loops. Instead they either use recursion to do looping, or they use functions like map that take other functions as arguments.
Defining map using recursion:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
3. FILTER
filter selects every element from a list that satisfies a condition or predicate.
3.1. FILTER DEFINED USING LIST COMPREHENSION
Given:
p x is a condition or predicate function.
xs is a list of xs.
x is an element drawn from the list of xs.
<- is pronounced "drawn from."
| pipe is pronounced "such that."
, comma before the condition or predicate is pronounced "such that."
filter defined using list comprehension:
filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [x | x <- xs , p x]
3.2. FILTER DEFINED USING RECURSION
filter :: (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x:xs)
| px = x : filter p xs
| otherwise = filter p xs
4. CURRIED
Functions with multiple arguments are defined in Haskell by currying. Currying is the process of transforming a function that takes multiple arguments into a function that takes just a single argument and returns another function if any arguments are still needed.
In Haskell, all functions are considered curried. All functions in Haskell take just single arguments.
Curried functions can be partially applied. Partial application in Haskell involves passing less than the full number of arguments to a function that takes multiple arguments.
5. EMBEDDED DOMAIN SPECIFIC LANGUAGES (EDSLs)
Higher order functions can be used in Haskell to define EDSLs which can be used to do many things including processing lists and building parsers. A Haskell EDSL is a language embedded inside of Haskell. An EDSL uses the library of functions provided by Haskell, often called combinators, because they combine their arguments into terms inside the EDSL. In essence, EDSLs are just Haskell libraries.
6. USER DEFINED
User defined higher order functions often use partial application. Partial application in Haskell involves passing less than the full number of arguments to a function that takes multiple arguments. This results in a new function taking the remaining number of parameters.
6.1. RECEIVE A FUNCTION
The function area is missing the value for the radius r. The radius function computes the area of the circle using a hard coded value of 5 for the radius r. This is done by the function radius argument func receiving the function area with argument 5 as shown below.
-- C:\Users\Tinnel\areaCircle.hs
import Data.List
import System.IO
-- Area of Circle
area :: Floating a => a -> a
area r = pi * r ^ 2 -- The function area is missing the value for the radius r.
radius :: Num a => (a -> t) -> t -- func receives area function (a -> t).
radius func = func 5 -- radius argument 5, the constant t, is passed into function area.
areaCircle :: Double
areaCircle = radius area -- areaCircle stores results of function radius with r of 5.
Prelude> areaCircle
78.53981633974483
Prelude>
6.2. RETURN A FUNCTION
-- C:\Users\Tinnel\onePlus9.hs
import Data.List
import System.IO
addFunc :: Num a => a -> a -> a -- When you type :t addFunc
addFunc x y = x + y
{-
The -> kleisli arrow operator is right associative, and function application is left associative, meaning the type signature of addFunc actually looks like this:
addFunc :: Num a => a -> (a -> a)
This means that addFunc actually takes one argument and returns a function that takes another argument and returns an Int. In other words, addFunc is a function that takes a number and returns a function that takes a number and returns the sum of the two numbers.
-}
add9 :: Integer -> Integer
add9 = addFunc 9
onePlus9 :: Integer
onePlus9 = add9 1
Prelude> onePlus9
10
Prelude>
7. CONCLUSION
Haskell higher order functions allow for powerful abstractions. They make it easier to think in terms of functions and design the ultimate abstraction Embeded Domain Specific Languages (EDSLs).
8. REFERENCES
8. REFERENCES
Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.
Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.
Goerzen, J. & O'Sullivan, B. & Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.
Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.
Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.
Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.
