jonnifyfsharp

Module C2.05

From loops to recursion, map & fold

Stop writing the loop. Name the result instead.

A C# developer steps through a collection with for, foreach, or while, and accumulates into a mutable variable: var sum = 0; foreach (var x in xs) sum += x;. The loop spells out how to walk the data and where to put the running total. F# does the same work with recursion and three list functions — map, filter, and fold. A recursive function replaces the counter; fold replaces the accumulator loop; map and filter replace the loops that build a new list. Each one names what the answer is, not the steps to reach it — no index, no off-by-one, no mutable target. This is the single biggest day-one habit to swap, and the module takes it in three dives.

The three dives Back to C2 · F# for C# developers

How becomes what

The C# loop is a recipe for the machine: set a counter, read each element, update a variable, stop at the end. The bug surface is the mechanics — the index that starts at one instead of zero, the accumulator reset in the wrong place, the early break that skips the last item. F# moves the mechanics into library functions that are already correct, and asks only for the part that differs between problems: the function applied at each element, and the starting value.

The first dive trades the counting loop for a recursive function — and names the rule a C# developer needs to know it is safe: a recursive call in tail position compiles to a loop, so it runs in constant stack space and does not overflow. The second dive shows the for-plus-mutable-accumulator is fold, the one function that sums, finds a maximum, counts, or even rebuilds a list, depending only on the folder you hand it. The third dive takes the loops that build a new collection — transform every element, keep some — and replaces them with map, filter, and the both-at-once choose, read top to bottom through the pipe |>.

The three dives · select one

C2.05.1 loops → recursion C2.05.2 accumulator → fold C2.05.3 transform → map & filter the counter the accumulator the new list
C2.05.1 · From loops to recursion

A for loop with a counter becomes a recursive function that calls itself on a smaller input. The nuance a C# dev needs: a recursive call in tail position compiles to a loop, so an accumulator-passing helper runs in constant stack space.

You learn how recursion replaces the counting loop, and why tail recursion does not overflow

Open this dive · or pick another above

The loop describes how to step; the combinator describes what the result is. The machinery that caused the bugs moves into a function that was written correctly once.

The habit, in one example

Sum the numbers one to five. In C# the answer is a loop and a variable that the body mutates. In F# the answer is the name of the aggregation — List.fold (+) 0, or for this common case the even shorter List.sum. The same list, the same result, but the F# line states the operation and the seed, and nothing in it can be reset in the wrong place.

C# — a loop and a mutable accumulator

int Sum(int[] xs) {
    int t = 0;                       // the accumulator
    for (int i = 0; i < xs.Length; i++)
        t += xs[i];                  // the body mutates it each step
    return t;
}
// Sum(new[]{1,2,3,4,5}) == 15

F# — name the aggregation

let sum xs = List.fold (+) 0 xs    // val sum : int list -> int

List.fold (+) 0 [1..5]              // val it : int = 15
[1..5] |> List.sum                   // val it : int = 15

C# habit

A for/foreach/while loop with a mutable accumulator — the body spells out every step and where the running total lives.

F# form

A recursive function or one of map · filter · fold — the operation and the seed, with the stepping already written and correct.

The three dives

Read them in order. Each stands on valid F# beside the idiomatic C# it replaces: every // val it : echo below was produced by dotnet fsi, and every C# line compiles. Together they take a C# developer from the counting loop, the accumulator loop, and the transform loop to recursion, fold, and map / filter.

live module hub built dive ready soon specified
C2.05.1built

From loops to recursion

A counting loop becomes a recursive function; an accumulator-passing helper in tail position is a constant-stack loop.

  • the counterfactorial, sumTail, and the tail-call rule
C2.05.2built

From the accumulator loop to fold

The for-plus-mutable-accumulator is List.fold — one function, any aggregation, depending on the folder.

  • the accumulatorfold, foldBack, reduce, and C#'s Aggregate
C2.05.3built

From the transform loop to map & filter

Loops that build a new list become map (transform), filter (keep some), and choose (both at once).

  • the new listmap, filter, choose, and the pipe

References

Sources

Related in this course