We wrote search code, sort code, and filter code in the previous sections. Each time, the logic sat directly in the main program. If we need to search a different array, we write the same loop again. If we need to sort in two places, we copy the sorting code into both. The program grows, and the same patterns appear over and over.
Functions solve this. We package an array operation into a named computation, and from that point forward, we call it by name. The loop body is written once. The function works on any array of the right type.
And once we have functions that operate on arrays, a new question appears: what if we could write a loop structure once and change what it does by passing in a different operation?
The for Loop
You have written this pattern many times:
int i = 0;
while (i < ar.Length)
{
// do something with ar[i]
i++;
}Three pieces make this loop work: initialize i to 0, check whether i is less than ar.Length, and increment i after each iteration. These three pieces are always present, but they are spread across three separate locations in the code. The initialization is above the loop. The condition is in the while header. The increment is at the bottom of the scope.
The for loop puts all three on one line:
for (int i = 0; i < ar.Length; i++)
{
// do something with ar[i]
}Here is a side-by-side comparison:
WHILE VERSION FOR VERSION
int i = 0; for (int i = 0; i < ar.Length; i++)
while (i < ar.Length) {
{ // do something with ar[i]
// do something with ar[i] }
i++;
}
The for loop does not introduce new behavior. It compresses the same three pieces into one line, separated by semicolons: initialization, then condition, then update.
Translation: “Begin with i bound to 0. While the result of evaluating i < ar.Length is true, execute the scope. After each time the scope runs, increment i by one.”
The behavior is identical to the while version.
From this point forward, we use for loops for array traversal. The while version still works, and you can always convert between the two, but for is the conventional choice when the loop variable follows the initialize-check-increment pattern.
Practice. Rewrite this while-based traversal as a for loop:
int[] scores = {85, 92, 78, 90, 88};
int total = 0;
int i = 0;
while (i < scores.Length)
{
total += scores[i];
i++;
}Write your answer before checking.
Reveal answer
int[] scores = {85, 92, 78, 90, 88};
int total = 0;
for (int i = 0; i < scores.Length; i++)
{
total += scores[i];
}Compare your answer to the model. Note any differences. Write the corrected version before continuing.
Practice. Predict the output of this program:
int[] vals = {10, 20, 30};
for (int i = vals.Length - 1; i >= 0; i--)
{
Console.WriteLine(vals[i]);
}Reveal answer
30
20
10
The loop starts at index 2 (the last valid index) and counts down to 0. Each iteration displays the element at that index.
Practice. Translate this for loop to English:
for (int i = 0; i < data.Length; i++)
{
data[i] = data[i] + 5;
}Reveal answer
“Begin with i bound to 0. While the result of evaluating i < data.Length is true, execute the scope. After each time the scope runs, increment i by one. The scope: go to the location of data, shift by i, read the value there. Add 5 to that value. Go to the location of data, shift by i, and store the result there.”
Self-correct against the models above.
Functions That Read Arrays
Here is a function that takes an integer array and returns the sum of its elements:
Func<int[], int> Sum = (arr) =>
{
int total = 0;
for (int i = 0; i < arr.Length; i++)
{
total += arr[i];
}
return total;
};The type is Func<int[], int>. Two types are listed. The rule from Chapter 1 applies: inputs come first, output comes last. The input is int[] (an integer array). The output is int (an integer). This function takes an integer array and returns an integer.
A full token-level translation of a multi-line function body would be long and repetitive. The loop inside Sum uses the same syntax we have already translated. From this point forward, we describe what a function does rather than translating every token. Descriptions are less precise than translations, but they are easier to read and write for functions whose bodies use familiar patterns.
Description: “Sum takes an integer array and returns the sum of its elements. It accumulates a running total starting at 0, adds each element, and returns the total.”
To call this function:
int[] scores = {85, 92, 78, 90, 88};
int result = Sum(scores);Translation: “Call Sum with the reference stored in scores, and bind the returned value to an integer variable named result.”
What happens at the call: the reference in scores is copied into the parameter arr. Both scores and arr now refer to the same array object. Sum reads each element through arr, accumulates the total, and returns it. Because Sum only reads elements, the original array is unchanged after the call.
| after line | scores[0] | scores[1] | scores[2] | scores[3] | scores[4] | result |
|---|---|---|---|---|---|---|
| 1 | 85 | 92 | 78 | 90 | 88 | — |
| 2 | 85 | 92 | 78 | 90 | 88 | 433 |
The array is the same before and after. Sum produced a value without altering the data.
Functions That Modify Arrays
Some array operations change the array itself. Here is a function that doubles every element in place:
Action<int[]> DoubleAll = (arr) =>
{
for (int i = 0; i < arr.Length; i++)
{
arr[i] = arr[i] * 2;
}
};The type is Action<int[]>. This function takes an integer array and returns nothing. It performs an action: modifying the elements of the array it receives.
Description: “DoubleAll takes an integer array and doubles each element in place.”
int[] data = {5, 10, 15};
DoubleAll(data);After the call, the contents of data have changed:
| after line | data[0] | data[1] | data[2] |
|---|---|---|---|
| 1 | 5 | 10 | 15 |
| 2 | 10 | 20 | 30 |
The reference in data was copied into arr. Both point to the same array object. When DoubleAll writes to arr[0], it modifies the same memory that data[0] reads from.
data ──────┐
▼
┌────┬────┬────┐
│ 10 │ 20 │ 30 │
└────┴────┴────┘
▲
arr ──────┘
(inside DoubleAll)
Two names, one object. Writing through either name changes what both names see.
Reference Semantics in Function Calls
Compare what happens with a value type parameter and a reference type parameter.
Value type (int):
Func<int, int> AddOne = (x) => x + 1;
int a = 5;
int b = AddOne(a);After the call, a is still 5. The function received a copy of the value. It computed 6 and returned it. The original variable a is unaffected.
Reference type (int[]):
Action<int[]> SetFirst = (arr) => { arr[0] = 99; };
int[] nums = {1, 2, 3};
SetFirst(nums);Predict: after the call, what is nums[0]? Write your answer before reading on.
Reveal answer
nums[0] is 99.
The function received a copy of the reference. The reference points to the same array object as nums. When the function writes to arr[0], it modifies the array that nums also refers to. This is the reference model from earlier in the chapter, now visible inside a function call.
The rule: for value types, the function gets its own copy of the data. For reference types, the function gets its own copy of the reference, which still points to the shared object. Reading is always safe. Writing through the reference affects the original.
Practice Round 1: Code to English
Describe each function and what happens to the original array when the function is called.
Problem 1.
Func<int[], int> Product = (arr) =>
{
int result = 1;
for (int i = 0; i < arr.Length; i++)
{
result *= arr[i];
}
return result;
};Reveal answer
“Product takes an integer array and returns the product of its elements. It starts with 1, multiplies by each element, and returns the result.”
The function only reads from the array. The original array is unchanged.
Problem 2.
Action<int[]> ZeroOut = (arr) =>
{
for (int i = 0; i < arr.Length; i++)
{
arr[i] = 0;
}
};Reveal answer
“ZeroOut takes an integer array and stores 0 at every index.”
The function writes to the array. Because the parameter is a reference to the same object, the original array is modified. Every element becomes 0 after the call.
Problem 3.
int[] values = {3, 7, 2};
int p = Product(values);
ZeroOut(values);After these three lines execute, what is the value of p? What are the contents of values?
Reveal answer
p is 42 (3 × 7 × 2). The contents of values are {0, 0, 0}. Product read from the array without changing it, so p captured the product of the original elements. Then ZeroOut modified every element to 0.
Compare your answers to the models. Note any differences. Write the corrected version before continuing.
Functions That Return New Arrays
Some operations need to produce a new array rather than modify the original. Here is a function that returns a new array where every element is the negation of the original:
Func<int[], int[]> Negated = (arr) =>
{
int[] result = new int[arr.Length];
for (int i = 0; i < arr.Length; i++)
{
result[i] = -arr[i];
}
return result;
};The type is Func<int[], int[]>. It takes an integer array and returns an integer array.
Description: “Negated takes an integer array and returns a new integer array containing the negation of each element. The original array is unchanged.”
int[] original = {3, -1, 4};
int[] flipped = Negated(original);| after line | original[0] | original[1] | original[2] | flipped[0] | flipped[1] | flipped[2] |
|---|---|---|---|---|---|---|
| 1 | 3 | -1 | 4 | — | — | — |
| 2 | 3 | -1 | 4 | -3 | 1 | -4 |
The original array is untouched. Negated created a separate array object and returned a reference to it.
When should a function modify an array in place, and when should it create a new one? For our purposes: modify in place when the original data is no longer needed and the array size stays the same. Create a new array when the original matters or when the result has a different size (as with filtering).
Packaging Familiar Patterns as Functions
Every pattern from the previous sections can be packaged as a function. The loop bodies are the same code you already wrote by hand. The new thing is the wrapping: a type signature, a name, and a parameter.
Two examples. The first returns a value. The second modifies the array in place.
Max
Func<int[], int> Max = (arr) =>
{
int max = arr[0];
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
return max;
};Type: Func<int[], int>. Takes an integer array, returns an integer.
Description: “Max takes an integer array and returns the largest element. It starts with the first element, compares each remaining element, and keeps the larger value.”
The loop body is the max-finding code from the previous sections. The wrapping gives it a name and a type signature. Now we can call Max(scores) anywhere instead of writing the loop again.
SelectionSort
Action<int[]> SelectionSort = (arr) =>
{
for (int i = 0; i < arr.Length - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
};Type: Action<int[]>. Takes an integer array, returns nothing.
Description: “SelectionSort takes an integer array and sorts it in ascending order. It repeatedly finds the minimum element in the unsorted portion and swaps it into the next sorted position.”
SelectionSort is Action, not Func, because it modifies the array in place rather than computing a return value. After calling SelectionSort(data), the elements of data are rearranged. The caller’s array is changed.
The same wrapping works for every pattern from the previous sections: min, index-of, contains, is-sorted, filtering, and so on. Each one becomes a function with a type signature that describes what goes in and what comes out.
Practice Round 2: English to Code
Write a function for each description. Use for loops. Pay attention to whether each function returns a value (Func) or modifies the array in place (Action).
Problem 1. A function named Min that takes an integer array and returns the smallest element.
Hint: the structure is almost identical to Max.
Reveal answer
Func<int[], int> Min = (arr) =>
{
int min = arr[0];
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
}
return min;
};Problem 2. A function named IndexOf that takes an integer array and an integer target, and returns the index of the first occurrence of target in the array. If target is not found, it returns -1.
Reveal answer
Func<int[], int, int> IndexOf = (arr, target) =>
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == target)
{
return i;
}
}
return -1;
};The sentinel value -1 signals “not found.” No valid index is -1.
Problem 3. A function named Contains that takes an integer array and an integer target, and returns true if target appears in the array, false otherwise.
Reveal answer
Func<int[], int, bool> Contains = (arr, target) =>
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == target)
{
return true;
}
}
return false;
};Problem 4. A function named IsSorted that takes an integer array and returns true if the elements are in ascending order, false otherwise.
Hint: compare each element to the one after it. Think carefully about the loop bound.
Reveal answer
Func<int[], bool> IsSorted = (arr) =>
{
for (int i = 0; i < arr.Length - 1; i++)
{
if (arr[i] > arr[i + 1])
{
return false;
}
}
return true;
};The loop bound is i < arr.Length - 1. The last comparison is between arr[arr.Length - 2] and arr[arr.Length - 1]. If the loop ran to i < arr.Length, the expression arr[i + 1] would shift past the end of the array on the final iteration.
Problem 5. A function named Average that takes an integer array and returns the average as a double.
Hint: the return type is double, not int. You will need a cast.
Reveal answer
Func<int[], double> Average = (arr) =>
{
int total = 0;
for (int i = 0; i < arr.Length; i++)
{
total += arr[i];
}
return (double)total / arr.Length;
};Problem 6. A function named AddToAll that takes an integer array and an integer, and adds that integer to every element in the array.
Reveal answer
Action<int[], int> AddToAll = (arr, value) =>
{
for (int i = 0; i < arr.Length; i++)
{
arr[i] = arr[i] + value;
}
};Self-correct against the models above.
Composing Functions
Functions can call other functions. Once operations have names, we can build new operations on top of them.
Suppose we have Max from above and Min from Practice Round 2:
Func<int[], int> Min = (arr) =>
{
int min = arr[0];
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
}
return min;
};
Func<int[], int> Range = (arr) => Max(arr) - Min(arr);Description: “Range takes an integer array and returns the difference between the largest and smallest elements. It calls Max and Min and subtracts the results.”
int[] temps = {72, 68, 85, 91, 77};
int spread = Range(temps); // spread is 91 - 68 = 23Once operations are packaged into functions, they become building blocks. Range did not need its own loop. It used two existing functions and combined their results.
Spotting the Repetition
Look at Sum, Product, and a function that counts positive elements, placed side by side:
Func<int[], int> Sum = (arr) =>
{
int acc = 0; // initial value
for (int i = 0; i < arr.Length; i++)
{
acc = acc + arr[i]; // update rule
}
return acc;
};
Func<int[], int> Product = (arr) =>
{
int acc = 1; // initial value
for (int i = 0; i < arr.Length; i++)
{
acc = acc * arr[i]; // update rule
}
return acc;
};
Func<int[], int> CountPositive = (arr) =>
{
int acc = 0; // initial value
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] > 0) // update rule
{
acc = acc + 1;
}
}
return acc;
};The structure of these three functions is identical. Each creates an accumulator, traverses the array, updates the accumulator on each iteration, and returns it. The only things that differ are the initial value and the update operation.
| Function | Initial Value | Update Operation |
|---|---|---|
| Sum | 0 | acc + element |
| Product | 1 | acc * element |
| CountPositive | 0 | acc + 1 if element > 0 |
The loop skeleton, the traversal, and the return are all shared. Writing a new accumulation function means copying this structure and changing two pieces.
What if we could write the loop skeleton once, and pass in the initial value and the update operation as arguments?
Functions are values. Since Chapter 1, we have written definitions like Func<int, int, int> Add = (a, b) => a + b;, bound them to variables, and called them by name. We have not yet passed a function as an argument to another function. That is the new step.
Here is what it looks like. Suppose we have a function called Fold that contains the accumulation loop skeleton. We pass in the array, the initial value, and a function that describes the update rule:
Func<int, int, int> Add = (a, b) => a + b;
Func<int, int, int> Multiply = (a, b) => a * b;
int[] scores = {10, 20, 30};
int[] values = {2, 3, 4};
int sum = Fold(scores, 0, Add); // sum is 60
int product = Fold(values, 1, Multiply); // product is 24In the call Fold(scores, 0, Add), the third argument is Add. We are not calling Add here. We are passing it as a value to Fold. Fold will call Add on each iteration, using it to combine the accumulator with the current element.
The initial values are the same ones we chose by hand in the previous sections. Sum starts at 0 because adding 0 changes nothing. Product starts at 1 because multiplying by 1 changes nothing. The identity element discussion from earlier applies directly. The difference is that now these values are arguments instead of hard-coded constants.
Same loop. Different update rule. Different result.
Definition. A higher-order function is a function that takes a function as an argument or returns a function as a result.
Fold is a higher-order function. It takes Add or Multiply as an argument and uses that function inside its loop.
Fold: The Definition
Here is the complete program. Fold contains the accumulation loop skeleton. Add and Multiply are the update rules we pass in:
Func<int, int, int> Add = (a, b) => a + b;
Func<int, int, int> Multiply = (a, b) => a * b;
Func<int[], int, Func<int, int, int>, int> Fold = (arr, initial, combine) =>
{
int acc = initial;
for (int i = 0; i < arr.Length; i++)
{
acc = combine(acc, arr[i]);
}
return acc;
};
int[] scores = {10, 20, 30};
int[] values = {2, 3, 4};
int sum = Fold(scores, 0, Add); // sum is 60
int product = Fold(values, 1, Multiply); // product is 24Fold’s body should look familiar. It creates an accumulator, traverses the array, updates the accumulator on each iteration, and returns it. The only difference from Sum or Product is that initial and combine are parameters instead of fixed values.
The combine function takes the current accumulator and the current element, and produces the new accumulator. On each iteration, the line acc = combine(acc, arr[i]); calls whatever function was passed as combine. In the call Fold(scores, 0, Add), the parameter combine is bound to Add, so this line executes Add(acc, arr[i]) on each iteration. In the call Fold(values, 1, Multiply), the same line executes Multiply(acc, arr[i]) instead.
The pattern is general. Any operation that takes an accumulator and an element and produces a new accumulator fits. Addition and multiplication happen to be arithmetic, but the shape of the pattern, start with an initial value, combine with each element, return the result, does not depend on arithmetic.
Tracing Fold
Trace Fold(scores, 0, Add) where scores is {10, 20, 30}:
| Iteration | i | arr[i] | acc (before) | combine(acc, arr[i]) | acc (after) |
|---|---|---|---|---|---|
| — | — | — | — | — | 0 (initial) |
| 1 | 0 | 10 | 0 | Add(0, 10) = 10 | 10 |
| 2 | 1 | 20 | 10 | Add(10, 20) = 30 | 30 |
| 3 | 2 | 30 | 30 | Add(30, 30) = 60 | 60 |
Return value: 60.
This trace is identical to the hand-written sum loop from the previous sections. The combine function is doing what acc += arr[i] did before. The update rule is now a parameter instead of hard-coded syntax.
Trace Fold(values, 1, Multiply) where values is {2, 3, 4}:
| Iteration | i | arr[i] | acc (before) | combine(acc, arr[i]) | acc (after) |
|---|---|---|---|---|---|
| — | — | — | — | — | 1 (initial) |
| 1 | 0 | 2 | 1 | Multiply(1, 2) = 2 | 2 |
| 2 | 1 | 3 | 2 | Multiply(2, 3) = 6 | 6 |
| 3 | 2 | 4 | 6 | Multiply(6, 4) = 24 | 24 |
Return value: 24.
Same loop structure. Different combine function. Different result.
Reading Nested Type Signatures
Fold’s type is longer than any type signature we have seen so far:
Func<int[], int, Func<int, int, int>, int>
One of the inputs is itself a Func<>. We need a systematic way to read types like this.
Start with what you know:
Func<int, int> means a function that takes one integer and returns one integer.
Func<int, int, int> means a function that takes two integers and returns one integer.
The rule is the same as always: inputs come first, output comes last. When one of the inputs happens to be a Func<>, treat that entire Func<> as a single input.
For Fold’s type, Func<int[], int, Func<int, int, int>, int>, there are four types listed. The last is the output. The first three are inputs. Reading left to right:
The first input is int[], an integer array.
The second input is int, an integer.
The third input is Func<int, int, int>, a function that takes two integers and returns an integer.
The output is int.
We can write this as a list:
“A function that takes:
- an integer array,
- an integer (the initial value),
- a function that takes two integers and returns an integer (the combine operation),
and returns an integer.”
Each input has a role. The array is the data to traverse. The integer is the starting value for the accumulator. The function is the rule for combining the accumulator with each element. The return type is the final accumulated value.
This list-style translation is how we will read every nested type signature. Read the types left to right, treat each one as a parameter, and describe what it is. For Func<>, the last type is always the return. For Action<>, there is no return type, so every type listed is an input.
The type translation using the list-style form:
“A function that takes:
- an integer array,
- an integer (the initial value),
- a function that takes two integers and returns an integer (the combine operation),
and returns an integer.”
Description: “Fold traverses an array, maintaining an accumulator that starts at the initial value. For each element, it calls combine with the current accumulator and the current element, and rebinds the accumulator to the result. After the loop, it returns the accumulator.”
Practice. Translate this type to the list-style form:
Func<int[], Func<int, int>, int[]>
Reveal answer
“A function that takes:
- an integer array,
- a function that takes an integer and returns an integer (the transformation),
and returns an integer array.”
Practice. Translate this type to the list-style form:
Func<int[], Func<int, bool>, int[]>
Reveal answer
“A function that takes:
- an integer array,
- a function that takes an integer and returns a boolean (the condition),
and returns an integer array.”
Practice. Translate this type to the list-style form. This one uses Action instead of Func, so there is no return type.
Action<int[], Action<int>>
Reveal answer
“A function that takes:
- an integer array,
- a function that takes an integer and returns nothing (the action to perform on each element),
and returns nothing.”
Compare your answers to the models. Note any differences before continuing.
Map: Abstracting Element Transformation
You wrote functions like Negated that create a new array by transforming each element. The pattern looks like this: create a result array of the same length, traverse the original, apply some transformation to each element, and store the result in the corresponding position of the new array.
Map captures this pattern. The transformation is a parameter:
Func<int, int> Negate = x => -x;
Func<int, int> AddTen = x => x + 10;
Func<int[], Func<int, int>, int[]> Map = (arr, transform) =>
{
int[] result = new int[arr.Length];
for (int i = 0; i < arr.Length; i++)
{
result[i] = transform(arr[i]);
}
return result;
};
int[] original = {3, -1, 4};
int[] flipped = Map(original, Negate); // {-3, 1, -4}
int[] curved = Map(original, AddTen); // {13, 9, 14}Type translation:
“A function that takes:
- an integer array,
- a function that takes an integer and returns an integer (the transformation),
and returns an integer array.”
Description: “Map creates a new array of the same length. For each element, it calls transform on that element and stores the result at the corresponding index in the new array. The original is untouched.”
In the call Map(original, Negate), the parameter transform is bound to Negate. On each iteration, transform(arr[i]) executes Negate(arr[i]), which returns the negation of that element. In the call Map(original, AddTen), the same loop executes AddTen(arr[i]) instead, adding 10 to each element.
After both calls, original is still {3, -1, 4}. Map created two new arrays without touching the original.
Tracing Map
Trace Map(original, Negate) where original is {3, -1, 4}:
| Iteration | i | arr[i] | transform(arr[i]) | result[i] |
|---|---|---|---|---|
| 1 | 0 | 3 | Negate(3) = -3 | -3 |
| 2 | 1 | -1 | Negate(-1) = 1 | 1 |
| 3 | 2 | 4 | Negate(4) = -4 | -4 |
Return value: a new array {-3, 1, -4}.
Filter: Abstracting Selection
The two-pass filtering pattern from the previous sections counted matching elements in one pass, created a new array of that size, then filled it in a second pass. The condition that decided which elements to keep was written directly into the code.
Filter takes the condition as a parameter:
Func<int, bool> IsPositive = x => x > 0;
Func<int, bool> IsEven = x => x % 2 == 0;
Func<int[], Func<int, bool>, int[]> Filter = (arr, predicate) =>
{
int count = 0;
for (int i = 0; i < arr.Length; i++)
{
if (predicate(arr[i]))
{
count++;
}
}
int[] result = new int[count];
int fillIndex = 0;
for (int i = 0; i < arr.Length; i++)
{
if (predicate(arr[i]))
{
result[fillIndex] = arr[i];
fillIndex++;
}
}
return result;
};
int[] values = {-3, 5, 0, -8, 12, -7, 9};
int[] positives = Filter(values, IsPositive); // {5, 12, 9}
int[] evens = Filter(values, IsEven); // {0, -8, 12}Type translation:
“A function that takes:
- an integer array,
- a function that takes an integer and returns a boolean (the predicate),
and returns an integer array.”
Description: “Filter counts how many elements satisfy the predicate, creates a new array of that size, then traverses the original again and copies each matching element into the new array.”
The predicate is the condition. A predicate is a function that takes a value and returns true or false. The if conditions inside filtering loops from the previous sections were predicates, just written inline rather than named. The name is new. The concept is familiar.
In the call Filter(values, IsPositive), the parameter predicate is bound to IsPositive. Each time the loop evaluates predicate(arr[i]), it executes IsPositive(arr[i]), which returns true when the element is greater than 0. The structure of Filter is the same two-pass pattern from before. The condition predicate(arr[i]) replaces the hard-coded comparison. Different predicates select different elements from the same array.
Tracing Filter
Trace Filter(values, IsPositive) where values is {-3, 5, 0, -8, 12}:
Pass 1 (counting):
| i | arr[i] | predicate(arr[i]) | count |
|---|---|---|---|
| 0 | -3 | IsPositive(-3) = false | 0 |
| 1 | 5 | IsPositive(5) = true | 1 |
| 2 | 0 | IsPositive(0) = false | 1 |
| 3 | -8 | IsPositive(-8) = false | 1 |
| 4 | 12 | IsPositive(12) = true | 2 |
Create result with size 2.
Pass 2 (filling):
| i | arr[i] | predicate(arr[i]) | fillIndex | result |
|---|---|---|---|---|
| 0 | -3 | false | 0 | {0, 0} |
| 1 | 5 | true | 0 → 1 | {5, 0} |
| 2 | 0 | false | 1 | {5, 0} |
| 3 | -8 | false | 1 | {5, 0} |
| 4 | 12 | true | 1 → 2 | {5, 12} |
Return value: {5, 12}.
Composing Higher-Order Functions
Filter, Map, and Fold can be chained. The output of one becomes the input of the next.
Suppose we want to keep only positive values from an array and then double each one:
Func<int, bool> IsPositive = x => x > 0;
Func<int, int> Double = x => x * 2;
int[] values = {-3, 5, 0, -8, 12};
int[] doubledPositives = Map(Filter(values, IsPositive), Double);Read from the inside out. Filter(values, IsPositive) produces a new array containing {5, 12}. That array becomes the input to Map(..., Double), which produces {10, 24}.
Two operations, no hand-written loops. The same work done by hand would require a counting pass, a filling pass with a condition, then a traversal that doubles each element. The composed version is one line.
Practice Round 3: Higher-Order Functions
Trace and Predict
Problem 1. Trace Fold(arr, 0, Add) where arr is {4, 1, 3, 2} and Add = (a, b) => a + b. Fill in the state table and give the return value.
Reveal answer
| Iteration | i | arr[i] | acc (before) | combine(acc, arr[i]) | acc (after) |
|---|---|---|---|---|---|
| — | — | — | — | — | 0 |
| 1 | 0 | 4 | 0 | Add(0, 4) = 4 | 4 |
| 2 | 1 | 1 | 4 | Add(4, 1) = 5 | 5 |
| 3 | 2 | 3 | 5 | Add(5, 3) = 8 | 8 |
| 4 | 3 | 2 | 8 | Add(8, 2) = 10 | 10 |
Return value: 10.
Problem 2. Trace Map(arr, x => x + 1) where arr is {5, 0, -2}. Give the returned array.
Reveal answer
| Iteration | i | arr[i] | transform(arr[i]) | result[i] |
|---|---|---|---|---|
| 1 | 0 | 5 | 6 | 6 |
| 2 | 1 | 0 | 1 | 1 |
| 3 | 2 | -2 | -1 | -1 |
Return value: {6, 1, -1}.
Problem 3. Predict the result of Filter(arr, x => x % 2 == 0) where arr is {7, 4, 11, 8, 3, 6}.
Reveal answer
The predicate keeps elements that are even (divisible by 2). From the array {7, 4, 11, 8, 3, 6}, the even values are 4, 8, and 6.
Return value: {4, 8, 6}.
Problem 4. Translate this type to the list-style form:
Func<int[], int, Func<int, int, int>, int>
Reveal answer
“A function that takes:
- an integer array,
- an integer (the initial value),
- a function that takes two integers and returns an integer (the combine operation),
and returns an integer.”
This is the type of Fold.
Write Code
In these problems, you can define the function separately and pass it by name, or you can write the function expression directly in the argument position. For example, these two calls to Map do the same thing:
Func<int, int> AddTen = x => x + 10;
int[] a = Map(arr, AddTen);
int[] b = Map(arr, x => x + 10);The second version writes the function inline. It has no name. It exists only as the argument to Map. Both versions produce the same result.
Problem 5. Use Fold to compute the sum of squares of all elements in an array. The sum of squares of {2, 3, 4} is 4 + 9 + 16 = 29.
Reveal answer
int sumOfSquares = Fold(arr, 0, (acc, x) => acc + x * x);The initial value is 0. The combine function takes the current accumulator and the current element, squares the element, and adds it to the accumulator.
Problem 6. Use Map to add 10 to every element of an array named scores.
Reveal answer
int[] curved = Map(scores, x => x + 10);Problem 7. Use Filter to keep only values above a threshold. Assume the threshold is stored in a variable named cutoff.
Reveal answer
int[] above = Filter(values, x => x > cutoff);Problem 8. Compose Filter and Fold: filter an array to keep only passing scores (70 or above), then fold to compute their sum.
Reveal answer
Func<int, bool> IsPassing = x => x >= 70;
Func<int, int, int> Add = (a, b) => a + b;
int passingTotal = Fold(Filter(scores, IsPassing), 0, Add);Filter produces the array of passing scores. Fold sums them.
Self-correct against the models. For each problem, compare both your approach and your answer.
Common Bugs
Wrong Initial Value in Fold
Passing 0 as the initial value when computing a product:
int result = Fold(arr, 0, Multiply); // BUG: always returns 0On the first iteration, Multiply(0, arr[0]) produces 0. Every subsequent multiplication keeps the accumulator at 0. The initial value for multiplication is 1, not 0. This is the same issue from the previous sections, now visible as a function argument.
Confusing Parameter Order in the Combine Function
In Fold, the combine function receives the accumulator as its first argument and the current element as its second:
acc = combine(acc, arr[i]);If you write a combine function that assumes the element comes first, the result will be wrong for non-commutative operations. For addition and multiplication, the order does not matter because these operations are commutative. For subtraction or other operations where order matters, the distinction is important.
Forgetting That Map Returns a New Array
Map(scores, x => x + 10); // BUG: result is discardedMap does not modify the original array. It creates and returns a new one. If you call Map without binding the result to a variable, the new array is created and immediately lost. The original array is unchanged.
The fix:
int[] curved = Map(scores, x => x + 10);Passing a Function with the Wrong Type
Fold expects a combine function of type Func<int, int, int> (two integers in, one integer out). Passing a function of type Func<int, bool> (one integer in, one boolean out) is a type mismatch. The compiler will report an error.
The list-style translation helps catch these bugs before writing code. If Fold expects “a function that takes two integers and returns an integer,” and the function you are passing takes one integer and returns a boolean, the shapes do not match.
Review
Before continuing, test yourself on what you have learned. Attempt each exercise from memory, then search this section to check your answers. Note what you missed.
Part 1: Definitions
Write the definition from memory, then find it in this section to check.
- What is a higher-order function?
If your answer differs from the definition in this section, note what you missed and write the corrected version.
Review from Chapter 1:
- What is a function?
- What is a parameter?
- What is an argument?
Part 2: Reading Type Signatures
Translate each type to the list-style form.
Func<int[], int>Func<int[], int, int>Func<int[], Func<int, int>, int[]>Func<int[], int, Func<int, int, int>, int>Func<int[], Func<int, bool>, int[]>Action<int[], Action<int>>
Check your answers against the translations in this section.
Part 3: Descriptions and Translations
Describe the function definition. Translate the function calls.
- Describe what this function does:
Func<int[], int> Sum = (arr) => { int t = 0; for (int i = 0; i < arr.Length; i++) { t += arr[i]; } return t; }; - Translate:
int result = Fold(data, 0, Add); - Translate:
int[] doubled = Map(values, x => x * 2); - Translate:
int[] big = Filter(scores, x => x > 90);
Check your answers against the patterns shown in this section.
Part 4: Write Code
- Package a function named Min that takes an integer array and returns the smallest element.
- Use Fold to compute the product of all elements in an array.
- Use Map to negate every element of an array.
- Use Filter to keep only negative values from an array.
- Compose Filter and Fold: keep only even numbers, then compute their product.
Check your code against the examples in this section.
Part 5: Trace
Complete the state table for Fold(arr, 1, Multiply) where arr is {5, 2, 3} and Multiply = (a, b) => a * b.
| Iteration | i | arr[i] | acc (before) | combine(acc, arr[i]) | acc (after) |
|---|---|---|---|---|---|
| — | — | — | — | — | ? |
| 1 | ? | ? | ? | ? | ? |
| 2 | ? | ? | ? | ? | ? |
| 3 | ? | ? | ? | ? | ? |
What is the return value?
Check your table against a careful trace.
Part 6: Bug Identification
Find and fix the bug in each piece of code.
Bug 1.
int total = Fold(prices, 1, Add);Bug 2.
Map(temps, x => x + 5);
Console.WriteLine(temps[0]); // expects the +5 versionBug 3.
Func<int[], int> Smallest = (arr) =>
{
int min = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
}
return min;
};Search this section for the relevant discussions to verify your fixes.