Try Fold First!

Last time we talked about map and filter, which allow us to do the work of certain, very simple for-loops in other languages. However, they have a major limitation in that they don't let us carry any kind of state from element to element. In order to get this, we'll need the idea of a Fold.

Folds are the most important idea I will talk about this month. When it pops into your head to use a for-loop, the first one you should try to use to represent that idea in Haskell is a fold. I used them constantly in my Advent of Code run last year. Let's start with a simple example of a for-loop in C++.

struct Point {
  int x;
  int y;
};

int myFunc(const std::vector<Point>& myPoints) {
  int result = 0;
  for (const auto& point : myPoints) {
    if (result % 2 == 0) {
      result += point.x;
    } else {
      result += point.y
    }
  }
  return result;
}

Map and filter are not sufficient to replicate this in Haskell. We cannot filter myPoints for those points where we add x or y because we need the accumulated results to determine which way each of them goes. We cannot merely map a function over our list because, again, we lack the stateful information to figure out what information we need from each point.

But we can see the pattern developing.

We have our result variable, set to an initial value. Each element in our list affects the result in some way (based on the previous result). At the end we get our final result.

These element are all present if we look at the type signature for foldl, the most basic folding function in Haskell.

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

Notice that a is our "result" type, whereas b is the type of the items in our list. Things become more clear if we do this renaming:

foldl ::
  (result -> item -> result) -> -- Folding Function
  result -> -- Initial Result
  [item] -> -- List of inputs
  result -- Final Result

The most important part of this is the "folding" function. This function takes the previous result and the next item in the list, and incorporates that item into the result. The best analogy I can think of is like a stew. It starts out as water/stock (the initial value). And then you incorporate each item into the stew (but it's still a stew after each thing you add). And at the end your have your "final stew".

In our example above, the folding function considers whether the previous result is even or odd, and uses that to determine which part of the point to add to make the new result.

myFuncFold :: Int -> Point -> Int
myFuncFold prev (Point x y) = if prev `mod` 2 == 0
  then prev + x
  else prev + y

Once we have the folding function, it is usually very simple to write the final expression!

myFunc :: [Point] -> Int
myFunc points = foldl myFuncFold 0 points

With the list as the last argument, you can often eta reduce:

myFunc :: [Point] -> Int
myFunc = foldl myFuncFold 0

As a note, there are three different folding functions. We'll seen foldl, but there's also foldr and foldl':

foldr :: (item -> result -> result) -> result -> [item] -> result

foldl' :: (result -> item -> result) -> result -> [item] -> result

Notice that the arguments of the folding function are flipped for foldr! This is a "right" fold, so it will actually start from the right of your list instead of the left. For associative operations, order does not matter, but often it does!

>> foldl (+) 0 [1, 2, 3, 4]
10
>> foldr (+) 0 [1, 2, 3, 4]
10 -- Addition is associative, same result
>> foldl (-) 0 [1, 2, 3, 4]
-10
>> foldr (-) 0 [1, 2, 3, 4]
-2 -- Subtraction is not, different result!

More commonly foldl will capture how you see the operation in your head. However, foldl is more prone to stack overflows with large input lists due to laziness in Haskell. Using foldr gets around these problems, but might force you to reverse your list. You can use foldl' to solve both problems. It processes the list in the same order as foldl, while introducing strictness that prevents memory accumulation. Note that foldl' must be imported from Data.List while the other two functions are included in Prelude.

Finally, another great use for folds is manipulating data structures like sets and sequences. Suppose you're just trying to add a list of elements to an existing set. You could create a second set with fromList and append.

addListToSet :: Set a -> [a] -> Set [a]
addListToSet prevSet items = prevSet <> (Set.fromList items)

However, this is inefficient. You can avoid making an intermediate set like so:

addListToSet :: Set a -> [a] -> Set a
addListToSet prevSet items = foldr Set.insert prevSet items

-- Alternative with foldl
addListToSet prevSet items = foldl (flip Set.insert) prevSet items

Set insertion is associative so the difference in the two above approaches doesn't matter. But with a Map, the values for keys can be overwritten, so the order is important. Remember that!

If you master folds, you'll be well on your way to being more comfortable with Haskell. But stay tuned for more ways that Haskell will save you from for-loops! If you're interested in more beginner level tips, you should download our Beginners Checklist! It'll help you get set up with Haskell so you can be more effective!