Haskell Higher Order Functions

A higher order function is a function that can take a function as a parameter and/or can return a function as its end result. In this post we will discuss a few popular Haskell higher order functions.

Filter

As the name suggests this function filters out data that satisfy some condition.

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

p is a predicate function that checks whether a condition is true or not.

Prelude> filter (==3) [1,2,3]
[3]
Prelude> filter (==3) [1,2,33]
[]

Map

Map applies a function to every element of a given list

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

function f takes one parameter of type a and the elements input list that map function takes has to have type [a]

Prelude> map (*5) [1,2,3]
[5,10,15]

Lambda

Lambdas are the functions that are made on the go in the program and are anonymous. These functions are written as \x -> body

Prelude> map (\x->x*5) [1,2,3]
[5,10,15]
Prelude> (\x->x [11,2,3,4]) head
11

Foldl

If we check the type of foldl function in ghci, we get the following.

Prelude> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

Foldable is a class in Haskell. A data structure is foldable when its an instance of Foldable class, i.e. it implements all the functions in Foldable class. Foldable data structures can be folded into a summary value.

foldl function takes three arguments. The first one is a function of type (b -> a -> b). The second argument is called the accumulator. The third argument is in the context t (think of this as a wrapper). foldl folds (t a) left associatively with the help of the function argument and the accumulator.

Prelude> foldl (+) 4 [1,2,3]
10
Prelude> foldl (+) 3 (Just 5)
8

In the first example t a is [1,2,3]. The first argument is (+) (of type say Int->Int ->Int ). foldl first takes 4 (the accumulator) and 1 and feeds it to (+), then again feeds the result (i.e. 5) as the accumulator and the second element, 2, to (+). This goes on until the list is empty. For the second example t a is Just 5.

Foldr

Prelude> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

foldr works just like foldl. But there are two differences.

1. The accumulator is the second argument to the function argument.
2. Folding is done starting from the last element if (t a) (makes more sense when (t a) is a list).

Prelude> foldr (+) 4 [1,2,3]
10
Prelude> foldr (+) 3 (Just 5)
8

The difference between foldl and foldr can be explained with the following example.

Prelude> foldl (-) 0 [1,2,3,4,5]
-15
Prelude> foldr (-) 0 [1,2,3,4,5]
3

The foldl and foldr happens the following way —

1. foldl : (((((0-1)-2)-3)-4)-5)
2. foldr : (1-(2-(3-(4-(5-0)))))

scanl and scanr functions are like foldl and foldr resepectively, but they return a list of all the intermediate results instead of just returning the folded end result.

($)

($) :: (a -> b) -> a -> b
 f $ x = f x

In Haskell when we write a (func x y z) it is same as writing (((func x) y) z). So, function written with spaces are left associative. If ($) applies lefthand side of it to the righthand side. So, if we want to write (func (x (y z)), we can write it like func $ x $ y z. So, mainly its just work as same as parentheses. Python users are familiar with this already.

Prelude> (+) 100 $ foldl (+) 2 $ map (*5) [1,2,3,4,5]
177
Prelude> (+) 100 ( foldl (+) 2 ( map (*5) [1,2,3,4,5]))
177

(.)

This function is used for function composition. The function definition is as simple as the following.

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

Let us see examples

Prelude> let addmul = ((+3).(*2))
Prelude> addmul 4
11
Prelude> let plus3 = (+3)
Prelude> let plus2 = (+2)
Prelude> let plus1 = (+1)
Prelude> (plus1 . plus2 . plus3) 4
10