Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 57 ยท Functions

Higher-Order Functions: map, filter, folds

Learn Haskell higher-order functions: map, filter, foldr, foldl, foldl', zip, zipWith and iterate, with clear examples and runnable JavaScript stand-ins.

A higher-order function is a function that takes a function as an argument, returns one, or both. Haskell programs rarely write explicit loops. Instead they combine a handful of higher-order functions from the Prelude that capture the common shapes of list processing: transform every element, keep some elements, and combine everything into one value.

Learning these few functions well is the fastest way to start reading and writing idiomatic Haskell. They rely on currying and partial application, so make sure that lesson feels comfortable first.

Real Haskell is read-only on this site. The runnable examples are JavaScript stand-ins that mirror each function's behaviour.

Three jobs for list functions

map Transform every element.
filter Keep elements that pass a test.
fold Combine all elements into one value.

Most list loops are one of these three.

1 / 2

map

map applies a function to every element and returns a list of the results:

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

map (* 2) [1, 2, 3]            -- [2,4,6]
map length ["a", "bcd", "ef"]  -- [1,3,2]

Note that the type variables a and b may differ: length turns a String into an Int. A simple definition shows how little magic there is:

HASKELL
map _ []       = []
map f (x : xs) = f x : map f xs

filter

filter keeps the elements for which a predicate (a function returning Bool) is True:

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

filter even [1 .. 10]           -- [2,4,6,8,10]
filter (> 3) [1, 5, 2, 7]       -- [5,7]

You can chain them: map (* 2) (filter odd [1 .. 6]) gives [2,6,10].

JS map and filter stand-ins

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Folds: combining a list

A fold walks through a list and combines the elements with a function, starting from an initial value (the accumulator). sum, product, length, maximum and concat are all folds in disguise.

foldr: from the right

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

foldr (+) 0 [1, 2, 3]
-- = 1 + (2 + (3 + 0))
-- = 6

foldr f z replaces every (:) in the list with f and the final [] with z. That picture explains a lot:

HASKELL
[1, 2, 3]  =  1 : (2 : (3 : []))
foldr f z  =  f 1 (f 2 (f 3 z))

Because foldr is lazy in the rest of the list, it can work on infinite lists when f does not need its second argument. For example foldr (\x acc -> x > 10 || acc) False [1 ..] stops at the first element above 10 and returns True.

foldl: from the left

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

foldl (-) 10 [1, 2, 3]
-- = ((10 - 1) - 2) - 3
-- = 4

The accumulator comes first in the function's arguments for foldl, and second for foldr. Compare with foldr (-) 10 [1, 2, 3], which is 1 - (2 - (3 - 10)), giving -8. When the operator is not associative the two folds differ.

foldl' and strictness

The plain foldl builds a chain of delayed additions (thunks) before evaluating anything, which can use a lot of memory on big lists. foldl' from Data.List forces the accumulator at each step:

HASKELL
import Data.List (foldl')

foldl' (+) 0 [1 .. 1000000]

In recent versions of GHC, foldl' is also exported by the Prelude, and sum is already implemented with a strict left fold. For left-to-right accumulation, prefer foldl'. A deeper look comes in the lessons on laziness and strictness.

Rule of thumb: use foldr when building a list or when you want to stop early (laziness), and foldl' when producing a single summary value such as a total.

JS Folds in JavaScript

Press Run (or Ctrl + Enter) to see the console output here.

No output.

There are also foldr1 and foldl1, which use the first (or last) element as the starting value and fail on an empty list. Avoid them in production code; maximum [] has the same problem.

zip and zipWith

zip pairs up two lists and stops at the shorter one:

HASKELL
zip [1, 2, 3] "abc"       -- [(1,'a'),(2,'b'),(3,'c')]
zip [1, 2, 3] "ab"        -- [(1,'a'),(2,'b')]

zipWith combines the elements with a function instead of making pairs:

HASKELL
zipWith (+) [1, 2, 3] [10, 20, 30]   -- [11,22,33]
zipWith (\n s -> show n ++ s) [1, 2] ["st", "nd"]  -- ["1st","2nd"]

unzip goes the other way. A classic idiom pairs each element with its neighbour: zip xs (tail xs).

iterate

iterate f x builds the infinite list [x, f x, f (f x), ...]. Because Haskell is lazy, you take only what you need:

HASKELL
take 5 (iterate (* 2) 1)     -- [1,2,4,8,16]
takeWhile (< 100) (iterate (* 3) 1)  -- [1,3,9,27,81]

Related helpers worth knowing: takeWhile, dropWhile, span, any, all, concatMap and replicate.

JS zipWith and iterate with generators

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Putting it together

Here is a typical pipeline: sum of the squares of the odd numbers up to 10.

HASKELL
sumOddSquares :: Int
sumOddSquares = sum (map (^ 2) (filter odd [1 .. 10]))   -- 165

You will soon write the same thing with composition and $, which is the subject of the next lesson.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does foldr (:) [] [1, 2, 3] produce?

    foldr replaces each (:) with (:) and the final [] with [], so the list is rebuilt unchanged.
  2. 2. What is foldl (-) 10 [1, 2, 3]?

    foldl groups from the left: ((10 - 1) - 2) - 3 = 4. The foldr version gives -8.
  3. 3. Why prefer foldl' over foldl for summing a large list?

    The lazy foldl builds delayed computations that use memory; foldl' evaluates the accumulator as it goes.
  4. 4. What does zip [1, 2, 3] "ab" return?

    zip stops when the shorter list runs out.

Summary

  • map transforms each element, filter keeps those passing a predicate, folds combine a list into one value.
  • foldr f z replaces (:) with f and [] with z; it works lazily and can short-circuit.
  • foldl groups from the left; prefer the strict foldl' for totals.
  • zip pairs lists (stopping at the shorter), zipWith combines with a function.
  • iterate creates infinite lists, tamed by take and takeWhile thanks to laziness.

Next: Lambdas, Composition and the $ Operator.