Reducing Lists with Fold | CodeSignal Learn

Reducing Lists with Fold | CodeSignal Learn

Introduction: Crushing a List into One Value

Welcome to the fifth unit of our course! In the previous lessons, you learned how to treat functions as values and apply them using tools like map to transform lists and filter to select specific items. However, another common task in programming is taking a list of many items and collapsing it into a single value. Whether you need to find the sum of a list of numbers, identify the largest number, or simply count how many items it contains, you are performing a reduction . In this lesson, we will explore folds, which are Haskell's elegant, built-in tools for reducing lists automatically.

Recall: The Accumulator Pattern

Before we introduce our new tools, let us take a moment to recall a concept from Course 2 . You might remember writing manual recursion to process a list using an accumulator pattern . An accumulator pattern involves a starting value (often called a seed, like 0) that is updated step-by-step as you traverse a list. For example, to sum a list, you started with 0, added the first number to it, then added the second number to that new total, and so on until the list was empty. A fold is simply this exact seed-and-update pattern wrapped in a convenient higher-order function . Instead of writing out manual recursion every time, you can let Haskell handle the repetition for you.

Summing Lists with foldl

Let us learn how to use our first folding function: foldl (which stands for "fold left"). Here is its type signature: Haskell foldl :: (acc -> item -> acc) -> acc -> [item] -> acc This tells us that foldl takes a combining function, a starting accumulator value, and a list. The combining function receives the current accumulator first and the current list item second, then returns the next accumulator. Let us start by defining a value called total and providing foldl with its combining function and starting value. Haskell total :: Int total = foldl (+) 0 Here, (+) is our combining function. We place it in parentheses to pass the addition operator as a function. The 0 is our starting accumulator value. Next, we provide the list of numbers we want to reduce. Haskell total :: Int total = foldl (+) 0 [1, 2, 3, 4, 5] main :: IO () main = do print total When you run this code, the output will be: 15 Behind the scenes, foldl takes the starting 0 and adds the first element 1 to get 1 . It then takes that 1 and adds the next element 2 to get 3, continuing this process from left to right until the entire list is consumed and reduced to 15 . For small examples, foldl is fine for learning. In real programs with very large lists and strict numeric accumulators, foldl' from Data.List is often preferred because it avoids building up too much lazy accumulator work.

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Changing the Combiner with foldr

One of the best things about folds is how versatile they are. By simply swapping out the combining function, the same pattern can perform a completely different task. Let us demonstrate this by finding the maximum number in a list. This time, we will use foldr (fold right). It works similarly to foldl, but its combining function receives arguments in a different order: Haskell foldr :: (item -> acc -> acc) -> acc -> [item] -> acc For foldr, the combining function receives the current item first and the folded result of the rest of the list second. This order matters when you write your own lambdas. We will start by defining largest and giving it the built-in max function along with a starting value of 0 . Haskell largest :: Int largest = foldr max 0 The max function takes two numbers and returns the larger of the two. Now, let us add a list of positive numbers to complete the reduction. Haskell largest :: Int largest = foldr max 0 [3, 9, 2, 7] main :: IO () main = do print largest When you run this code, the output will be: 9 Instead of adding numbers together, foldr now compares each item with the folded result of the rest of the list, eventually reducing the entire list to the largest element, which is 9 . This example works because the list contains positive numbers and the seed 0 is below all expected values. If you used foldr max 0 on a list like [-5, -2, -9], the result would incorrectly be 0, even though 0 is not in the list. Always choose a starting value that makes sense for the data you expect.

Custom Combiners using Lambdas

Sometimes, a built-in function like (+) or max is not exactly what we need. As you learned in the previous lesson, we can create our own inline, anonymous functions called lambdas. We can use a lambda as our combining function inside a fold. Let us say we want to count how many elements are in a list. We can start by writing foldl with a custom lambda and our starting value of 0. Haskellcount :: Int count = foldl (\acc _ -> acc + 1) 0 Let us break down this lambda: (\acc _ -> acc + 1). In foldl, the combining function receives the current accumulator first and the current list element second. acc represents our running total. _ (an underscore) is standard Haskell syntax for a value we want to ignore. Since we just want to count the items, the specific values in the list do not matter. acc + 1 simply adds one to our running total for every item it sees. If you were writing a custom lambda for foldr, remember that the order would be different: the current item would come first, and the accumulator would come second. Now, let us provide the list. Haskellcount :: Int count = foldl (\acc _ -> acc + 1) 0 [10, 20, 30, 40] main :: IO () main = do print count When you run this code, the output will be: 4 Even though the list contains large numbers like 10 and 40, our lambda ignores them and simply adds 1 to the accumulator four times, correctly telling us there are 4 elements in the list.

Summary and Practice Prep

Whether you are summing values, finding a maximum, or counting items, list reductions all boil down to the same general shape: a folding function (foldl or foldr), a combining function, a starting value, and a list. The key detail is that foldl and foldr pass arguments to custom combining functions in different orders. Here is the complete picture of what we built step-by-step in this lesson: Haskelltotal :: Int total = foldl (+) 0 [1, 2, 3, 4, 5] largest :: Int largest = foldr max 0 [3, 9, 2, 7] count :: Int count = foldl (\acc _ -> acc + 1) 0 [10, 20, 30, 40] main :: IO () main = do print total print largest print count Running this complete program yields: text15 9 4 You have now learned how to replace manual accumulator recursion with clean, declarative folds. Next up, you will move into the interactive environment to practice writing these list reductions yourself. Take your time, experiment with the functions, and get comfortable with how the accumulator updates step-by-step!