Higher-Order Functions

A higher-order function takes a function as an argument or returns one. You've already used map and filter; this lesson shows how to write your own and introduces a few more from the standard library.

Taking functions as arguments

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

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

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

main :: IO ()
main = do
  print (applyTwice (* 3) 5)
  print (applyTwice ("ha" ++) "!")
  print (myMap show [1, 2, 3])
  print (myFilter (/= ' ') "a b c")

45
"haha!"
["1","2","3"]
"abc"

The parentheses in (a -> a) -> a -> a matter: the first argument is itself a function.

Returning functions

multiplier :: Int -> (Int -> Int)
multiplier n = \x -> x * n

compose3 :: (c -> d) -> (b -> c) -> (a -> b) -> a -> d
compose3 f g h = f . g . h

main :: IO ()
main = do
  let triple = multiplier 3
  print (map triple [1, 2, 3])
  print (compose3 show (+ 1) (* 2) 10)

[3,6,9]
"21"

Thanks to currying, multiplier n x = x * n defines exactly the same function — every multi-argument function "returns a function".

More standard higher-order functions

import Data.List (sortBy, groupBy, maximumBy)
import Data.Ord (comparing, Down (..))
import Data.Function (on)

main :: IO ()
main = do
  let people = [("Ada", 36), ("Alan", 41), ("Grace", 85), ("Linus", 36)]
  print (zipWith3 (\a b c -> a + b + c) [1, 2] [10, 20] [100, 200])
  print (iterate (* 2) 1 !! 10)
  print (takeWhile (< 40) (map (^ 2) [1 ..]))
  print (sortBy (comparing snd) people)
  print (sortBy (comparing (Down . snd)) people)
  print (maximumBy (comparing snd) people)
  print (map (map fst) (groupBy ((==) `on` snd) (sortBy (comparing snd) people)))
  print (flip (-) 1 10)

[111,222]
1024
[1,4,9,16,25,36]
[("Ada",36),("Linus",36),("Alan",41),("Grace",85)]
[("Grace",85),("Alan",41),("Ada",36),("Linus",36)]
("Grace",85)
[["Ada","Linus"],["Alan"],["Grace"]]
9

• comparing f builds a comparison function from a "key" function; Down reverses the order.
• on applies a function to both arguments before comparing: (==) on snd compares pairs by their second element.
• flip swaps the first two arguments of a function.
• iterate f x is the infinite list [x, f x, f (f x), ...].

Practice

Write countIf :: (a -> Bool) -> [a] -> Int, then use it to count the words longer than three letters in "the quick brown fox jumps".

countIf :: (a -> Bool) -> [a] -> Int
countIf p = length . filter p

main :: IO ()
main = print (countIf ((> 3) . length) (words "the quick brown fox jumps"))

3