For Loops and Folds: How we Iterate in Functional and Non-functional Languages

Sep 13, 2025

Let's look at a few use-cases which highlight the big three higher order functions for handling lists:

  1. Given a list of numbers, increase all of the numbers by one
  2. Given a list of numbers, return all the even numbered elements
  3. Given a list of numbers, return the sum of all the elements in the list

Loops

In a procedural context, these can all be solved with for loops. Let's implement in Java.

Add one to elements 

public static List<Integer> addOne(List<Integer> givenValues) {
    var returnValues = new ArrayList<Integer>();
    for (var currentValue : givenValues) {
        returnValues.add(currentValue + 1);
    }
    return returnValues;
}

Return all the even numbered elements 

public static List<Integer> evenNumbers(List<Integer> givenValues) {
    var returnValues = new ArrayList<Integer>();
    for (var currentValue : givenValues) {
        if (currentValue % 2 == 0) {
            returnValues.add(currentValue);
        }
    }
    return returnValues;
}

Return the sum of the values in the list 

public static Integer sumNumbers(List<Integer> givenValues) {
    var returnValue = 0;
    for (var currentValue : givenValues) {
        returnValue += currentValue;
    }
    return returnValue;
}

The functional approach - recursion

In pure functional languages, these problems are generally solved with a recursive approach, since this maps more to a declarative, function-oriented syntax. Let's demonstrate in Erlang.

Add one to elements 

add_one([]) -> [];
add_one([Head|Tail]) -> [Head+1|add_one(Tail)].

Return all the even numbered elements 

get_evens([]) -> [];
get_evens([Head|Tail]) ->
    case Head rem 2 of
        0 -> [Head|get_evens(Tail)];
        _ -> get_evens(Tail)
    end.

Return the sum of the values in the list 

sum_values([]) -> 0;
sum_values([Head|Tail]) -> Head + sum_values(Tail).

Generalizing to map, filter, fold

These three examples are concrete use-cases for the "Big Three" higher order functions: map, filter, and fold. So, let's abstract out to these functions. Note that Erlang provides these functions out of the box, but for illustrative purposes, let's implement them anyway.

Add one to elements 

% abstract out to map
add_one(List) -> map(fun(X) -> X + 1 end, List).

map(_, []) -> [];
map(Fun, [Head|Tail]) -> [Fun(Head)|map(Fun, Tail)].

Return all the even numbered elements 

% abstract out to filter
get_evens(List) -> filter(fun(X) -> X rem 2 =:= 0 end, List).

filter(_, []) -> [];
filter(Pred, [Head|Tail]) ->
    case Pred(Head) of
        true -> [Head|filter(Pred, Tail)];
        false -> filter(Pred, Tail)
    end.

Return the sum of the values in the list

Note that in this case, we have to provide a "starting" value upon which to fold for this to work.

sum_values(List) -> fold(fun(X, SumSoFar) -> X + SumSoFar end, List, 0).

fold([], _, Accumulated) -> Accumulated;
fold([Head|Tail], Fun, Accumulated) -> fold(Tail, Fun, Fun(Head, Accumulated)).

Making them tail recursive

For most of these implementations, we run into the scaling problem of recursive approaches: since the frames of the previous recursive calls have to be preserved, memory usage scales linearly with the size of the given list. Languages like Erlang solve for this with Tail Call Optimization. As such, we can avoid the inefficiency as long as we make these implementations tail recursive:

Map 

% Start with a 2-arity function which performs the list reverse, and provides a default starting value for the accumulator
map_tco(List, Fun ) ->
    map_tco(lists:reverse(List), Fun, []).

% Use the 3-arity function with the accumulator for TCO
map_tco([], _, Acc) -> Acc;
map_tco([Head|Tail], Fun, Acc) -> map_tco(Tail, Fun, [Fun(Head)|Acc]).

Filter 

% Again, a 2-arity proxy for convenience
filter_tco(List, Pred) ->
    filter_tco(lists:reverse(List), Pred, []).

filter_tco([], _, Acc) -> Acc;
filter_tco([Head|Tail], Pred, Acc) ->
    case Pred(Head) of
        true -> filter_tco(Tail, Pred, [Head|Acc]);
        false -> filter_tco(Tail, Pred, Acc)
    end.

Fold

Notice that fold is already tail recursive! The last call in fold is of a call to fold, so it already enjoys tail call optimization. We can rename it to fold_tco, to match our other functions, but the syntax doesn't change at all.

fold_tco([], _, Accumulated) -> Accumulated;
fold_tco([Head|Tail], Fun, Accumulated) -> fold_tco(Tail, Fun, Fun(Head, Accumulated)).

Wait - don't these all look similar?

Notice that all of these tail-recursive functions follow the same form:

  1. They are a function of the form function_name(List, Function, Accumulator)
  2. In the recursive calls they make to themselves, they set the accumulator by composing the function, the head of the list, and the accumulator.

The last bit is important to see how we can refactor further.

  • In tail-recursive map: map_tco(Tail, Fun, [Fun(Head)|Acc]) uses the expression [Fun(Head)|Acc]
  • In tail-recursive filter: filter_tco(Tail ,Pred, [Head|Acc]) uses the expression [Head|Acc] (and just Acc in the other tree case)
  • In fold: fold_tco(Fun, Tail, Fun(Head, Accumulated)) uses the expression Fun(Head, Accumulated)

Recall that fold as we originally wrote it was already tail-recursive. And in fact, if we look at the pattern we've identified, we can see that fold is in fact more abstract than map and filter. In other words, map and filter can be written to use fold! Let's try:

First map. Notice that we must reverse the list up front so that elements get ordered correctly after the fold. This can be done as a post-processing operation as well.

map(List, Fun) ->
    fold(lists:reverse(List), fun(Head, Acc) -> [Fun(Head) | Acc] end, []).

filter can be written this way too:

filter(List, Fun) ->
    fold(lists:reverse(List),
         fun(Head, Acc) ->
            case Fun(Head) of
                true -> [Head | Acc];
                _ -> Acc
            end
         end,
         []).

Folds and for loops

map and filter can be written in terms of fold because, conceptually, fold is doing the same work as a for loop: we start with a list, we have a "current" element in the list (we refer to it as Head since we are pattern matching against the front of the list), and we operate on we've collected so far from our previous steps through the loop, in composition with the current element. We can write a sort of fold as a for loop using the same variable names in java to demonstrate:

public interface Accumulator<T, E> {
    E accumulate(T first, E second);
}

public static <T,E> E fold(List<T> list, E initialAccumulated, Accumulator<T, E> accumulator) {
    var accumulated = initialAccumulated;

    for (T head : list) {
        accumulated = accumulator.accumulate(head, accumulated);
    }

    return accumulated;
}

By that same token, we can use the language of fold to define a for loop, but in Erlang!

for([], _, ReturnValue) -> ReturnValue;
for([Head|Tail], Fun, AccumulatedValue) -> for(Tail, Fun, Fun(Head, AccumulatedValue)).

Because all of our use-cases are variants on a for loop in a procedural context, they can all be similarly solved with fold.

Add One 

add_one(List) -> fold(lists:reverse(List), fun(X, Ls) -> [X + 1|Ls] end, []).

% Or, if you'd rather append the value (less efficient in erlang, but readable), you can avoid the list reverse:
add_one(List) -> fold(List, fun(X, Ls) -> Ls ++ [X + 1] end, []).

Get Evens 

% again, swap append for reverse if you'd prefer here
get_evens(List) ->
    fold(
        lists:reverse(List),
        fun(X, Ls) -> if X rem 2 =:= 0 -> [X|Ls]; true -> Ls end end,
        []).

With this longer syntax, it even starts to look a little bit like a for loop - just replace the word fold with for.

Sum

Since we're returning a single value in this case, we can avoid calling lists:reverse.

sum_values(List) -> fold(List, fun(X, SumSoFar) -> X + SumSoFar end,0).

Some other use-cases

  1. Find element in a list

    find_value(List, Value) -> fold(
    List,
    fun(X, Else) ->
        if X == Value -> Value;
        true -> Else
        end
    end,
    notfound
).

  2. Index of an element in a list

    In cases like this, the accumulator doesn't really need to contain much information about the list at all. In this case, it's just a) the index to check next, and b) whether the element has been found.

    index_of(List, Value) ->
    case fold(
        List,
        fun(CurrentValue, {FoundIndex, IsFound}) ->
            if  IsFound == found -> {FoundIndex, found};
                CurrentValue == Value -> {FoundIndex+1, found};
                true -> {FoundIndex+1, notfound}
            end
        end,
        {-1, notfound}
    ) of
        {Index, found} -> Index;
        _ -> notfound
    end.

Wrapping up

Whether in a functional or a procedural paradigm, programmers frequently need to operate on lists of objects. It turns out, whether you're using an iterative loop (procedural paradigm) or a tail-recursive function (functional paradigm), you conceptually have to do the same work: "seek" through the list, and operate on the current element in composition with however you've accumlated values in the previous iterations (starting, of course, with a seed element). Whether you call it a for loop or a fold, it's a remarkably similar operation.

https://blog.kyleandzoebarton.com/posts/atom.xml