Haskell 2: Functions and Laziness

An 80–100 minute interactive course for programmers who have completed Haskell 1 or can use lists, tuples, pattern matching, and recursion. Build higher-order functions, trace folds, and make lazy pipelines.

1

Map and Filter

Why this matters

A lot of list recursion repeats the same walk through the list. Higher-order functions let us name that walk once and supply the part that changes: what to do with each item.

🎯 You will learn to

  • Analyze the difference between transforming values and selecting values.
  • Apply map and filter to a score list without changing the original.

This is Part II of the Haskell course. You should be comfortable with functions, lists, tuples, and (x:xs) patterns. Allow about 80–100 minutes; after Function Composition is a good stopping point.

A Function as an Argument

A higher-order function accepts a function or returns a function. Haskell functions are first-class values: we can give them names, pass them around, and return them.

map    :: (a -> b)    -> [a] -> [b]
filter :: (a -> Bool) -> [a] -> [a]

map f transforms every item with f. filter p keeps the original items for which predicate p returns True. Both preserve the order of the items they produce; neither changes the input list.

Two useful predicates: even n returns whether an integer is divisible by 2, and null xs returns whether a list is empty. Each returns a Boolean, so either can serve as the decision passed to filter.

Thinking Time!

The first two lines of main use the same predicate and the same input. Predict both outputs before selecting Run. Does map even produce even numbers, Boolean values, or an error?

After running, explain why one output has four items while the other has two. The function’s result means “replacement value” to map and “keep this item?” to filter.

Your Turn

Fix qualifiedScores. It must keep scores at least 10, double each kept score, and return them in their original order. Keep repeated scores. For example, [9,10,12] should become [20,24]; an empty list should stay empty.

The named helpers already describe the two decisions. Combine them, then add a boundary example of your own to main. Before testing, explain which operation must see the original scores.

Starter files
Main.hs
module Main where

qualifies :: Int -> Bool
qualifies score = score >= 10

doublePoints :: Int -> Int
doublePoints score = score * 2

qualifiedScores :: [Int] -> [Int]
qualifiedScores scores = map doublePoints scores

main :: IO ()
main = do
  print (map even [1,2,3,4])
  print (filter even [1,2,3,4])
  print (qualifiedScores [9,10,12])

Step 1 — Knowledge Check

Min. score: 80%

1. What is map null [[],[1],[2,3]]?

  • [True]

    Map retains every function result, including False. It does not use those results to decide which output items to keep.

  • [True,False,False]
  • [False,True,True]

    Null returns True for the empty list and False for each nonempty list. This answer reverses that predicate.

The three calls to null return True, False, and False. Map can change the element type: here it turns lists into Booleans.

2. A function should keep every name with more than four letters. Which type must its filter predicate have?

  • String -> String

    That type describes a string transformation. Filter needs a decision about whether to keep the original string.

  • String -> Bool
  • String -> Int

    Length returns a number, but filter still needs that number compared against the cutoff to obtain a Boolean.

The predicate receives one name and returns a keep-or-drop decision. The output of filter still contains the original names.

2

Lambdas and Lexical Scope

Why this matters

Sometimes the behavior passed to map is too small to need a separate name. Sometimes that behavior also needs a setting chosen earlier. Lambdas and closures handle both cases.

🎯 You will learn to

  • Analyze which binding a name refers to inside a lambda.
  • Create a function that retains the settings supplied when it was created.

Small Functions, Right Where We Need Them

triple x = x * 3
-- The same transformation without a function name:
-- \x -> x * 3

The backslash introduces a lambda, x is its parameter, and the expression after -> is its result. For example, map (\x -> x * 3) [2,4] produces [6,12].

A lambda can also use a name from its surrounding definition. In makeScorer multiplier bonus = \score -> multiplier * score, the inner function uses multiplier from outside its own parameters. A closure keeps a function together with the environment its free names need. A free name is a name used by the function but bound outside its own parameters or local definitions.

Haskell uses lexical scope: the definition’s nesting determines those bindings. An inner parameter with the same spelling shadows an outer name. Capturing a binding does not force its value immediately; Haskell can evaluate it later when needed.

Thinking Time!

Predict scopeProbe 99 from the starter. Does the lambda add 1 to 99 or to 7? Commit to a result, run it, and point to the binder for each occurrence of outer.

Your Turn

Fix makeScorer so that makeScorer multiplier bonus returns a function computing multiplier * score + bonus. For example, the scorer made with 2 and 3 maps [0,4] to [3,11].

Store two differently configured scorers in local names in main, then call them on the same score. Explain why creating the second scorer cannot change the first one’s settings. Keep scopeProbe as a reminder that a repeated name is not necessarily the same binding.

Starter files
Main.hs
module Main where

scopeProbe :: Int -> Int
scopeProbe outer = (\outer -> outer + 1) 7

makeScorer :: Int -> Int -> (Int -> Int)
makeScorer multiplier bonus = \score -> multiplier * score

main :: IO ()
main = do
  print (scopeProbe 99)
  print (map (makeScorer 2 3) [0,4])

Step 2 — Knowledge Check

Min. score: 80%

1. What is choose 40 6 9? 

choose x y = \x -> x + y

  • 46

    The inner x shadows the first parameter. Applying the returned function to 9 binds its x to 9.

  • 15
  • 49

    The lambda captures y = 6. Its x comes from the later argument 9, not from the outer x = 40.

The lambda uses its own x = 9 and the surrounding y = 6. The outer x = 40 is unused.

2. What is the result of this expression? 

let bonus = 3
    addBonus = \x -> x + bonus
in let bonus = 100 in addBonus 4

  • 104

    A caller’s local name does not replace a free name’s binding in an already defined function.

  • 7
  • A duplicate-binding error

    The inner let creates a nested scope, so it may shadow the outer bonus without redefining that outer binding.

The body of addBonus refers to bonus in its definition’s scope, where it is 3. The inner bonus = 100 does not alter that binding.

3

Currying and Partial Application

Why this matters

A function can be configured now and supplied its data later. Reading the remaining function type tells us exactly which arguments are still missing.

🎯 You will learn to

  • Analyze the type left after a function receives some of its arguments.
  • Apply an operator section with the intended operand order.

One Argument at a Time

These two interfaces calculate the same ticket price, but receive their arguments differently:

ticketCost :: Int -> Int -> Int
ticketCost fee count = fee + 4 * count

pairCost :: (Int, Int) -> Int
pairCost (fee, count) = fee + 4 * count

The arrow groups to the right: Int -> Int -> Int means Int -> (Int -> Int). Application groups to the left: ticketCost 2 3 means (ticketCost 2) 3. So ticketCost 2 is a function awaiting a count. This is partial application. The curried interface makes it possible; pairCost instead expects one complete pair.

Currying represents a multiple-input operation as successive single-argument functions. Haskell’s ticketCost fee count = ... already has curried form. The built-ins curry pairCost and uncurry ticketCost convert between these interfaces.

Thinking Time!

An operator in parentheses is a function: (+) 2 5 is 7. A section fixes an operand: (* 3) multiplies its argument by 3, while (10 -) subtracts its argument from 10.

Predict map (10 -) [2,12] before running. Are the results [8,-2] or [-8,2]? Explain which operand is already fixed.

Your Turn

Fix discountAll amount scores to subtract amount from each score. Keep the order and repeats; do not clamp negative results. For example, discounting [2,12] by 10 should produce [-8,2].

Keep its curried interface so that discountAll 10 can be reused as a list transformation. One syntax wrinkle: (-10) is the number negative ten, not a subtract-ten function. A lambda or the built-in subtract 10 expresses that function. subtract amount score means score - amount.

Add a call that passes discountAll 3 directly to map over a list of score lists. Determine its type before running.

Starter files
Main.hs
module Main where

ticketCost :: Int -> Int -> Int
ticketCost fee count = fee + 4 * count

pairCost :: (Int, Int) -> Int
pairCost (fee, count) = fee + 4 * count

discountAll :: Int -> [Int] -> [Int]
discountAll amount scores = map (amount -) scores

main :: IO ()
main = do
  print (ticketCost 2 3, pairCost (2,3))
  print (curry pairCost 2 3, uncurry ticketCost (2,3))
  print (map (10 -) [2,12])
  print (discountAll 10 [2,12])

Step 3 — Knowledge Check

Min. score: 80%

1. Given award :: Int -> Int -> [Int] -> [Int], what is the type of award 2?

  • (Int, [Int]) -> [Int]

    The original curried interface does not turn the remaining arguments into a tuple. Its arrows stay in place.

  • Int -> [Int] -> [Int]
  • [Int] -> [Int]

    Only one Int argument has been supplied. The second Int argument is still needed before the list argument.

Applying a function to one argument removes the first input arrow from its type. Award 2 still takes an Int and then a list.

2. Which function keeps numbers strictly greater than 5?

  • filter (5 >)

    This tests 5 > x, keeping numbers below 5. A section retains the operator’s operand positions.

  • filter (> 5)
  • filter (>= 5)

    This also keeps 5. Strictly greater excludes the boundary value itself.

The section (> 5) is equivalent to a function that takes x and evaluates x > 5.

4

Function Composition

Why this matters

Small transformations become more useful when their outputs connect to one another. Composition lets the code show that connection, while types help us check whether the pieces fit.

🎯 You will learn to

  • Analyze the order of operations in a composed function.
  • Apply composition and $ without changing which values qualify.

Functions That Fit Together

countEvens = length . filter even
-- countEvens xs means length (filter even xs)

The composition operator (.) builds a new function: (f . g) x = f (g x). Read the data transformation from the rightmost function toward the left. Its type is (b -> c) -> (a -> b) -> a -> c: the output type of g must be the input type of f.

The application operator ($) applies a function with very low precedence: f $ expression means f (expression). For example, sum $ map (* 2) [1,2] means sum (map (* 2) [1,2]). A dot connects functions; a dollar applies a function to the value expression that follows. Neither operator makes a program eager.

Here sum adds the numbers in a finite list, with sum [] = 0. Another list transformation, reverse, puts a finite list’s items in reverse order: reverse [1,2,3] is [3,2,1].

Thinking Time!

In the starter, bonusTotal adds 3, keeps results at least 10, and sums them. Predict its result for [8,10,12]. Does the original score 8 contribute anything? Write the intermediate list after each transformation, then run.

Your Turn

Repair bonusTotal. The rule is: select original scores at least 10, add 3 to each selected score, and return their sum. Thus [8,10,12] must produce 28. Repeated scores contribute separately, and no qualifying scores means a total of 0.

Rearrange the existing functions into the needed composition. Then write an equivalent expression in a comment using parentheses, and another using $. Explain why changing parentheses for $ leaves the computation unchanged while changing the order of map and filter does not.

Starter files
Main.hs
module Main where

countEvens :: [Int] -> Int
countEvens = length . filter even

bonusTotal :: [Int] -> Int
bonusTotal = sum . filter (>= 10) . map (+ 3)

main :: IO ()
main = do
  print (countEvens [1,2,4])
  print (sum $ map (* 2) [1,2])
  print (bonusTotal [8,10,12])

Step 4 — Knowledge Check

Min. score: 80%

1. What does (reverse . take 2) [1,2,3] return?

  • [3,2]

    That result reverses the whole input before taking two. The composition passes the input to take 2 first.

  • [2,1]
  • [3,2,1]

    The take 2 stage discards the third item before reverse receives a list.

The expression is reverse (take 2 [1,2,3]). Taking two gives [1,2], and reversing that gives [2,1].

2. Given f :: String -> Int and g :: Int -> Bool, what is the type of g . f?

  • String -> Bool
  • Int -> Int

    Int is the intermediate connection between the functions. It is neither the pipeline’s starting type nor its result type.

  • Bool -> String

    Composition does not reverse either function. Data still travels from a String through f and then through g.

F turns the String input into an Int that g accepts. G returns the final Bool.

5

Left Folds

Why this matters

Some list tasks carry a result forward as each item is incorporated. A fold makes that accumulating rule explicit and gives the empty input a deliberate meaning.

🎯 You will learn to

  • Analyze a left fold by expanding its accumulator updates.
  • Create a reducer whose accumulator represents the prefix processed so far.

A Result Built from a Prefix

foldl :: (b -> a -> b) -> b -> [a] -> b
-- foldl step seed [x,y] = step (step seed x) y

The reducer takes the accumulator first, then an item, and returns the next accumulator. Its type b can differ from the element type a. For example, a fold could consume characters and build an integer count.

For a concrete sum, foldl (+) 0 [4,6] expands to (0 + 4) + 6. For an empty list, the result is just the seed 0. These are equations about grouping; they do not claim that every intermediate value is evaluated immediately.

Thinking Time!

Predict foldl (-) 20 [3,2]. Is it (20 - 3) - 2, or 20 - (3 - 2)? Expand the expression before running the starter. Addition hides this distinction; subtraction exposes it.

Your Turn

Fix digitsToNumber to turn a finite list of decimal digits into its integer value. Inputs contain only digits 0 through 9. [3,0,7] means 307, leading zeroes are allowed, and [] means 0. The result type is Integer, so large results do not wrap like a bounded Int.

Derive the reducer from this invariant: the accumulator is the number represented by the prefix already consumed. If that prefix represents 30, what must happen when the next digit is 7? Change the reducer, then write the accumulator values for [1,0,2] in a comment before testing.

Retrieval pause: why does map alone not produce this one-number result? Explain using the type of map from memory before revisiting Step 1.

Starter files
Main.hs
module Main where

digitsToNumber :: [Integer] -> Integer
digitsToNumber = foldl (\acc digit -> acc + digit) 0

main :: IO ()
main = do
  print (foldl (-) 20 [3,2] :: Int)
  print (digitsToNumber [3,0,7])

Step 5 — Knowledge Check

Min. score: 80%

1. Which seed lets foldl (*) seed reproduce the number in every one-element list?

  • 0

    Zero makes every product zero. It is the identity for addition, not multiplication.

  • 1
  • The first list item

    Using the first item as the seed while also processing it in the list would multiply that item twice.

One times x is x, so a seed of 1 preserves every single-item product. It also supplies the conventional empty product.

2. Earlier we used map and filter separately. What is length (map even [2,3,4])?

  • 2

    Two input values are even, but map keeps all three Boolean results. Filter even would produce two items.

  • 3
  • 1

    There is one odd value, but the predicate’s truth value does not decide list length for map.

Map produces [True,False,True], which has three items. A reduction should start from the right list transformation.

6

Right Folds

Why this matters

Choosing a fold is partly a choice about how results fit together. A right fold exposes the current item and the folded remainder, a shape that often matches recursive list construction.

🎯 You will learn to

  • Analyze the argument order and grouping of foldr.
  • Apply a fold that combines nested lists while preserving their order.

The Item and the Folded Remainder

foldr :: (a -> b -> b) -> b -> [a] -> b
-- foldr step seed [x,y] = step x (step y seed)

Here the reducer takes the item first, then the folded remainder. Compare this with foldl, whose reducer receives the accumulator first. For foldr (:) [] [4,6], expansion gives 4 : (6 : []): the original order is preserved.

“Right fold” describes this right-associated expression. It does not promise that Haskell must evaluate the last item first. The reducer decides what it needs; the next step explores why that matters.

Thinking Time!

Predict both subtraction results in main. Write their parentheses before doing arithmetic. Will changing only foldl to foldr preserve the result? Run and compare your expansions.

Your Turn

Fix stitch so it combines a finite list of lists into one list, retaining both the outer order and the order inside each list. For example, [[1,2],[],[3,1]] becomes [1,2,3,1]. Empty inner lists contribute no items; an empty outer list returns [].

Its polymorphic type [[a]] -> [a] means the same function must work for integers, characters, or any other element type. No comparison or arithmetic on the elements is required.

Use the right-fold expansion to decide how ++ can combine one current sublist with the already stitched remainder. The checks accept equivalent implementations; explain the grouping of your solution rather than guessing which fold name will pass.

Starter files
Main.hs
module Main where

stitch :: [[a]] -> [a]
stitch = foldl (\acc part -> part ++ acc) []

main :: IO ()
main = do
  print (foldl (-) 0 [1,2,3] :: Int)
  print (foldr (-) 0 [1,2,3] :: Int)
  print (stitch [[1,2],[],[3,1]] :: [Int])

Step 6 — Knowledge Check

Min. score: 80%

1. Which expression is the expansion of foldr (-) 10 [3,2]?

  • (10 - 3) - 2

    This is the left-fold expansion: seed first, then successive items. Foldr places each item before its folded remainder.

  • 3 - (2 - 10)
  • (3 - 2) - 10

    Foldr groups the expression to the right. Combining 3 and 2 first changes the subtraction.

The first reducer call has 3 as its first argument and the fold of [2] as its second. That remainder is 2 - 10.

2. Why can the same stitch :: [[a]] -> [a] work for integer lists and Boolean lists?

  • It joins lists without comparing their items.
  • Its input lists may freely mix unrelated element types.

    Within one call, all the inner lists share the same element type a. Different calls may choose different types.

  • Its type variable permits only numeric items.

    The type variable is not limited to numbers. The same structural operation can join lists of many element types.

The implementation combines list structure without using arithmetic or Boolean operations on its elements. Its element type can therefore vary between calls.

7

Lazy Lists

Why this matters

An unbounded stream can still answer a finite question. To use it safely, we need to reason about what the consumer demands, not just whether the input looks infinite.

🎯 You will learn to

  • Analyze whether obtaining a result needs an entire list or only a prefix.
  • Create a bounded selection that works on finite and infinite lists.

Demand Drives Evaluation

Haskell is lazy: it evaluates expressions when their values are needed. [1..] describes an unbounded list, while take 3 [1..] only needs [1,2,3]. Printing the entire unbounded list or computing its length cannot finish.

A list’s first item and its tail are separate demands. error "message" raises an exception if its value is demanded. We can deliberately put one in an unused tail to check our reasoning.

Thinking Time!

Predict head (7 : error "tail demanded"). Does it return 7 or raise the exception? Explain which part head needs, then run the starter.

In contrast, length (7 : error "tail demanded") needs the tail. Keep that contrast in your notes; the starter runs the bounded example.

Your Turn

Fix firstMatches n predicate items. It must return up to the first n matching items in input order. It must stop once it has enough matches, even when the input continues forever. For n <= 0, return [] without inspecting the input. If a finite input runs out, return the matches found so far.

For example, firstMatches 3 even [1..] should produce [2,4,6]. A finite input [1,2,3] only has one even item, so requesting three gives [2].

Decide whether the bound applies before or after selection. Then test a prefix whose unused tail is error "too far". Needing no more matching items should also mean needing no more input.

Folds and Demand

foldr (\x rest -> x == 3 || rest) False [1..] can return True: when it reaches 3, || needs no remainder. A right fold with (+) still needs every item to return a sum. Both foldl and its stricter relative foldl', available from Data.List, need the end of the list to return a final accumulator. For large finite numeric reductions, foldl' helps avoid deferred accumulator arithmetic; strictness does not make an infinite input finish.

A finite requested output is not a guarantee of termination either: searching [1..] for a negative number will never find its first match.

Starter files
Main.hs
module Main where

firstMatches :: Int -> (a -> Bool) -> [a] -> [a]
firstMatches n predicate items = take n items

main :: IO ()
main = do
  print (head (7 : error "tail demanded") :: Int)
  print (firstMatches 3 even [1..] :: [Integer])
  print (foldr (\x rest -> x == 3 || rest) False [1..] :: Bool)

Step 7 — Knowledge Check

Min. score: 80%

1. Which expression can produce a complete finite result?

  • take 3 (filter even [1..])
  • filter even (reverse [1..])

    Reverse needs the end of its input before it can produce its first output item. This input has no end.

  • take 3 (filter (< 0) [1..])

    Take limits how many matches are wanted, but the predicate never finds even one negative number in this input.

The even-number search reaches 2, 4, and 6 after finite work. Take then needs no further input.

2. What allows a right fold to finish on some infinite lists?

  • It first reverses the input list.

    Reversing an infinite list cannot produce a first item. Foldr expands from the front without reversing its input.

  • Its reducer can ignore the remainder.
  • It always evaluates its seed first.

    The seed may never be reached. A short-circuiting reducer can obtain its result before the base case.

A reducer such as a short-circuiting Boolean operation may return a result without demanding the folded remainder. A reducer that needs the entire remainder does not get this benefit.

8

The Playlist Report

Why this matters

A new problem rarely arrives labeled “use filter” or “use a fold.” The next step is to choose operations from the contract and explain how their parts fit together.

🎯 You will learn to

  • Create a pipeline that selects, transforms, and aggregates structured data.
  • Evaluate a solution using boundary examples and type relationships.

The Contract

playlistReport minimumScore bonus tracks receives a finite list of (title, score) pairs and returns (selectedTitles, totalPoints).

  • Select tracks whose original score is at least minimumScore.
  • Return selected titles in their input order. Repeated titles remain repeated.
  • Add bonus to each selected score and sum those adjusted scores.
  • With no selected tracks, return ([], 0). Scores, cutoffs, and bonuses can be negative.

Thinking Time!

For a cutoff of 10 and a bonus of 3, predict the report for [("Intro",8),("Loop",10),("Loop",12)]. Should the repeated title appear once or twice? Should the score 8 receive a bonus that makes it eligible?

Write the exact expected pair in a comment. The starter currently returns an empty report; run it to see the gap before implementing your design.

Your Turn

Implement playlistReport using the techniques you can now choose among. The signature and a sample input are provided; the decomposition is yours. A tuple pattern such as (title, score) lets a helper access both fields. Alternatively, fst and snd obtain the first and second components of a pair.

Before selecting Test My Work, add two examples to main: one that would expose a wrong cutoff boundary, and one that would expose counting each title only once. Add a short comment explaining the types between your chosen stages and why no input binding changes.

A Later Retrieval Check

Tomorrow, close these instructions and rebuild the report from its contract. Replace the domain with (snack, price) pairs and a maximum-price rule. Explain which parts change and which list-processing patterns stay the same.

For one final type connection, reason about twice f x = f (f x): the result of the inner f is an input to the outer f. That relationship forces f to consume and produce the same type. The last knowledge check asks you to use that connection.

Starter files
Main.hs
module Main where

playlistReport :: Int -> Int -> [(String, Int)] -> ([String], Int)
playlistReport minimumScore bonus tracks = ([], 0)

main :: IO ()
main = print (playlistReport 10 3 [("Intro",8),("Loop",10),("Loop",12)])

Step 8 — Knowledge Check

Min. score: 80%

1. Which test best distinguishes an inclusive cutoff from an accidentally strict cutoff?

  • A track exactly at the cutoff
  • A track far above the cutoff

    Both > and >= keep a score far above the cutoff, so that example cannot expose this particular error.

  • A track far below the cutoff

    Both > and >= reject a score far below the cutoff. They disagree at equality.

At the boundary, >= includes the track and > excludes it. A focused example separates the two candidate rules.

2. Which is the most general type of applyThen f g x = g (f (f x))?

  • (a -> b) -> (b -> c) -> a -> c

    The inner result is passed back into the same f. Its result type must therefore match its argument type, rather than being an unrelated b.

  • (a -> a) -> (a -> b) -> a -> b
  • (a -> a) -> (a -> a) -> a -> a

    G is applied only once, so it may change the type. Requiring its output to match its input would be unnecessarily restrictive.

The repeated f calls require f :: a -> a. G then receives an a and may return a different type b, giving the whole function its final result type.

3. To get the first two qualifying tracks from an infinite input, which design can finish when those tracks occur after a finite prefix?

  • Filter, then take two
  • Sort all tracks, then filter

    Sorting the entire unbounded input cannot finish before producing a globally ordered result. The contract only needs the first qualifying occurrences.

  • Count all tracks, then take two

    Counting every track requires reaching the end of the input. An unbounded list has no end to reach.

Filtering can produce matching items incrementally, and take can stop after consuming two. This extends the lazy selection pattern from the previous step.