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.
Methods 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 method works on any array of the right type.
Once we have methods 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.
Methods That Read Arrays
Here is a method that takes an integer array and returns the sum of its elements:
int Sum(int[] arr)
{
int total = 0;
for (int i = 0; i < arr.Length; i++)
{
total += arr[i];
}
return total;
}The return type is int. The parameter is int[] arr, so the method receives an integer array. This method takes an integer array and returns an integer.
A full token-level translation of a multi-line method 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 method does rather than translating every token. Descriptions are less precise than translations, but they are easier to read and write for methods 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 method:
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.
Methods That Modify Arrays
Some array operations change the array itself. Here is a method that doubles every element in place:
void DoubleAll(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
arr[i] = arr[i] * 2;
}
}The return type is void. This method takes an integer array and returns nothing. It modifies 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 Method Calls
Compare what happens with a value type parameter and a reference type parameter.
Value type (int):
int AddOne(int x)
{
return x + 1;
}
int a = 5;
int b = AddOne(a);After the call, a is still 5. The method received a copy of the value. It computed 6 and returned it. The original variable a is unaffected.
Reference type (int[]):
void SetFirst(int[] 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 method received a copy of the reference. The reference points to the same array object as nums. When the method 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 method call.
The rule: for value types, the method gets its own copy of the data. For reference types, the method 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 method and what happens to the original array when the method is called.
Problem 1.
int Product(int[] 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 method only reads from the array. The original array is unchanged.
Problem 2.
void ZeroOut(int[] 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 method 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.
Methods That Return New Arrays
Some operations need to produce a new array rather than modify the original. Here is a method that returns a new array where every element is the negation of the original:
int[] Negated(int[] arr)
{
int[] result = new int[arr.Length];
for (int i = 0; i < arr.Length; i++)
{
result[i] = -arr[i];
}
return result;
}The return type is 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 method 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 Methods
Every pattern from the previous sections can be packaged as a method. The loop bodies are the same code you already wrote by hand. The new thing is the wrapping: a return type, a name, and parameters.
Two examples. The first returns a value. The second modifies the array in place.
Max
int Max(int[] arr)
{
int max = arr[0];
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
return max;
}Signature: int Max(int[] arr). 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
void SelectionSort(int[] 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;
}
}Signature: void SelectionSort(int[] arr). 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 returns void 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 method with a signature that describes what goes in and what comes out.
Practice Round 2: English to Code
Write a method for each description. Use for loops. Pay attention to whether each method returns a value or modifies the array in place and returns void.
Problem 1. A method named Min that takes an integer array and returns the smallest element.
Hint: the structure is almost identical to Max.
Reveal answer
int Min(int[] 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 method 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
int IndexOf(int[] arr, int 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 method named Contains that takes an integer array and an integer target, and returns true if target appears in the array, false otherwise.
Reveal answer
bool Contains(int[] arr, int target)
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == target)
{
return true;
}
}
return false;
}Problem 4. A method 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
bool IsSorted(int[] 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 method 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
double Average(int[] arr)
{
int total = 0;
for (int i = 0; i < arr.Length; i++)
{
total += arr[i];
}
return (double)total / arr.Length;
}Problem 6. A method named AddToAll that takes an integer array and an integer, and adds that integer to every element in the array.
Reveal answer
void AddToAll(int[] arr, int value)
{
for (int i = 0; i < arr.Length; i++)
{
arr[i] = arr[i] + value;
}
}Self-correct against the models above.
Composing Methods
Methods can call other methods. 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:
int Min(int[] arr)
{
int min = arr[0];
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
}
return min;
}
int Range(int[] arr)
{
return 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 methods, they become building blocks. Range did not need its own loop. It used two existing methods and combined their results.
Spotting the Repetition
Look at Sum, Product, and a method that counts positive elements, placed side by side:
int Sum(int[] arr)
{
int acc = 0; // initial value
for (int i = 0; i < arr.Length; i++)
{
acc = acc + arr[i]; // update rule
}
return acc;
}
int Product(int[] arr)
{
int acc = 1; // initial value
for (int i = 0; i < arr.Length; i++)
{
acc = acc * arr[i]; // update rule
}
return acc;
}
int CountPositive(int[] 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 methods 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.
| Method | 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 method 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?
That question starts the higher-order part of the chapter. Until now, parameters have held ordinary data such as integers, booleans, and array references. A higher-order method has a parameter that holds behavior.
In C#, behavior-parameter types use Func and Action.
Func<...>describes behavior that returns a value.Action<...>describes behavior that returns nothing.- A lambda expression, written with
=>, is a compact way to write short behavior at the call site.
The four array patterns in the rest of this section use these roles:
| Role | Type notation | Pattern | Job |
|---|---|---|---|
| Effect | Action<T> | ForEach | perform an action for each element |
| Predicate | Func<T, bool> | Filter | decide whether to keep an element |
| Transform | Func<T, U> | Map | produce a new value from each element |
| Combiner | Func<U, T, U> | Fold | update an accumulator with one element |
This chapter uses integer arrays, so the concrete types will usually be int, int[], and bool. Chapter 4 reuses the same role names when the collection is a linked list.
ForEach: Abstracting Effects
Sometimes the loop performs an effect rather than computing a return value. Displaying each element is the simplest example:
for (int i = 0; i < scores.Length; i++)
{
Console.WriteLine(scores[i]);
}ForEach keeps the traversal and takes the effect as a parameter:
void ForEach(int[] arr, Action<int> action)
{
for (int i = 0; i < arr.Length; i++)
{
action(arr[i]);
}
}
int[] scores = {10, 20, 30};
ForEach(scores, x => Console.WriteLine(x));Action<int> means behavior that takes one integer and returns nothing. The lambda x => Console.WriteLine(x) says: given an integer x, display it.
In the call ForEach(scores, x => Console.WriteLine(x)), the method traverses scores. On each iteration, it calls the action with the current element.
ForEach names the effect pattern: keep the traversal fixed, and let the caller choose what effect happens for each element.
Fold: The Definition
Fold names the reduction pattern. It traverses a collection and reduces many values to one value.
Fold contains the accumulation loop skeleton. We pass in the array, the initial value, and behavior that describes the update rule:
Func<int, int, int> Add = (a, b) => a + b;
Func<int, int, int> Multiply = (a, b) => a * b;
int Fold(int[] arr, int initial, Func<int, int, int> 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 24Func<int, int, int> means behavior that takes two integers and returns an integer. The first two int entries are inputs. The last int is the return type.
The lambda (a, b) => a + b has two parameters, a and b, and returns their sum. The lambda (a, b) => a * b has the same type, but returns their product.
Fold’s body should look familiar. It creates an accumulator, traverses the array, updates the accumulator on each iteration, and returns it. The difference from Sum or Product is that initial and combine are parameters instead of fixed values.
The combine behavior 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 behavior 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 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.
The loop structure is unchanged; the update rule comes from the behavior passed to Fold, so changing the argument changes the result.
Definition. A higher-order function is a function that takes a function as an argument or returns a function as a result. In C# code, these often appear as methods with Func or Action parameters.
Fold is higher-order because it takes Add or Multiply as an argument and uses that behavior inside its loop.
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 behavior 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 behavior. Different result.
Reading Behavior Parameter Types
The important type in Fold’s signature is the behavior parameter:
int Fold(int[] arr, int initial, Func<int, int, int> combine)Read Func<int, int, int> combine as one parameter:
- the parameter name is
combine, - its type is
Func<int, int, int>, - it takes two integers,
- it returns an integer.
Func<int, int> means behavior that takes one integer and returns one integer.
Func<int, int, int> means behavior that takes two integers and returns one integer.
The rule for Func is: inputs come first, output comes last. Treat the whole Func<...> as the type of one parameter.
For Fold’s method signature, read left to right:
intbefore the name says Fold returns an integer.int[] arris the array to traverse.int initialis the starting value for the accumulator.Func<int, int, int> combineis the rule for combining the accumulator with each element.
For Action<>, there is no return type. Every type listed is an input. Action<int> means behavior that takes one integer and returns nothing.
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 method signature:
int[] Map(int[] arr, Func<int, int> transform)Reveal answer
“Map takes an integer array and a transformation. The transformation takes an integer and returns an integer. Map returns an integer array.”
Practice. Translate this method signature:
int[] Filter(int[] arr, Func<int, bool> predicate)Reveal answer
“Filter takes an integer array and a predicate. The predicate takes an integer and returns a boolean. Filter returns an integer array.”
Practice. Translate this method signature. This one uses Action, so the behavior parameter returns nothing.
void ForEach(int[] arr, Action<int> action)Reveal answer
“ForEach takes an integer array and an action. The action takes an integer and returns nothing. ForEach returns nothing.”
Compare your answers to the models. Note any differences before continuing.
Map: Abstracting Element Transformation
You wrote methods 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;
int[] Map(int[] arr, Func<int, int> 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}Signature translation: “Map takes an integer array and a transformation. The transformation takes an integer and returns an integer. Map 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;
int[] Filter(int[] arr, Func<int, bool> 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}Signature translation: “Filter takes an integer array and a predicate. The predicate takes an integer and returns a boolean. Filter 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 behavior 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 Methods
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 Methods
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 method signature:
int Fold(int[] arr, int initial, Func<int, int, int> combine)Reveal answer
“Fold takes an integer array, an initial integer, and a combine function. The combine function takes two integers and returns an integer. Fold returns an integer.”
Write Code
In these problems, you can name the behavior separately and pass it by name, or you can write the lambda 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 behavior 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 an argument to Fold.
Confusing Parameter Order in the Combine Function
In Fold, the combine behavior receives the accumulator as its first argument and the current element as its second:
acc = combine(acc, arr[i]);If you write combine behavior 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 Behavior with the Wrong Type
Fold expects combine behavior of type Func<int, int, int> (two integers in, one integer out). Passing behavior of type Func<int, bool> (one integer in, one boolean out) is a type mismatch. The compiler will report an error.
The signature translation helps catch these bugs before writing code. If Fold expects “behavior that takes two integers and returns an integer,” and the behavior 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.
- What is a method parameter?
- What is an argument?
- What does
returndo in a value-returning method?
Part 2: Reading Method Signatures
Translate each signature.
int Sum(int[] arr)void ForEach(int[] arr, Action<int> action)int[] Map(int[] arr, Func<int, int> transform)int[] Filter(int[] arr, Func<int, bool> predicate)int Fold(int[] arr, int initial, Func<int, int, int> combine)
Check your answers against the translations in this section.
Part 3: Descriptions and Translations
Describe the method definition. Translate the method calls.
- Describe what this method does:
int Sum(int[] 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 method 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.
int Smallest(int[] 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.