Fundamentals of Computer Science

Chapter 4 - Higher-Order Methods

27 min read

Higher-Order Methods

The LinkedList class from the previous section has methods for counting nodes, summing values, checking membership, and modifying the chain. Each one hard-codes a specific job: Count visits every node, Sum adds every value, and Contains checks whether a specific value exists.

Sometimes the job changes, but the traversal does not. You might want to count only values above 90, sum only the even values, or check whether any value satisfies some condition other than equality. You could write separate methods for each variation: CountAbove, CountEven, SumPositive, ContainsOdd. Every one of those methods would contain the same traversal loop with a different operation inside.

The array-based higher-order functions solved a similar problem by moving the changing part into a parameter. The traversal stayed the same, and the caller supplied the action, predicate, or combine function. The same idea transfers to LinkedList. ForEach, Filter, Map, and Fold become methods on the list, and once they are in place, variations like “count only values above 90” or “sum only the even values” become single calls instead of whole new methods.

Recursive List Processing

So far, we have processed linked lists by walking through them with a reference variable and a while loop. That is still a good way to think about many list methods. This section adds a second way to think about the same structure.

Start with Count from the previous section:

public int Count()
{
    int count = 0;
    LinkedListNode? current = this.head;
    while (current != null)
    {
        count++;
        current = current.Next;
    }
    return count;
}

Translation: “Bind 0 to count. Bind this.head to current. While current is not null, increment count by 1, then advance current to current.Next. After the loop, return count.”

The translation walks through a procedure. It describes what to start with, what condition to check, what to do at each step, and when to stop. To follow it, you have to mentally track count and current as the loop runs.

Now shift the focus from the loop to the structure of the list itself. A linked list node is either null (the empty list) or a value paired with a reference to another node. The structure refers to itself: a node’s Next field holds a reference to another node of the same type. Every non-empty list is a value followed by a smaller list, because node.Next is one step closer to null.

When data is defined this way, the function that processes it can be defined the same way. Instead of writing “start at the head and walk,” we can write “the answer for an empty list is one thing, and the answer for a non-empty list is built from the answer for the rest.” That second case uses the answer to the same problem applied to a smaller version of the data. This is the same recursive pattern that defined Factorial, SumTo, and CountDigits: state a base case, then define the general case in terms of the same function applied to a smaller input. What changes here is the shape of the smaller version. Instead of a smaller integer, the smaller input is a shorter list.

A recursive version of Count says something different. If the list is empty, the count is 0. If the list is not empty, the count is 1 plus the count of the rest of the list. That is a definition in two cases. It tells you what the count is in terms of itself on a smaller input.

To write this in C#, we need a function that takes a node and returns its count. The public Count method takes no node parameter because the list is self-contained. We could rewrite the public method to take a node, but callers would then have to reach into the list’s internal structure and pass the head themselves, which defeats the encapsulation the class was built to provide.

Use two methods named Count: a public one that takes no parameters and delegates to a private one that takes a node and does the recursion.

Method overloading is defining multiple methods with the same name in the same class, as long as their parameter lists differ.

The translations we have been writing already set this up. A method definition like public int Count() translates to “Define a method named Count that takes no inputs and returns an int.” A method definition like private int Count(LinkedListNode? node) translates to “Define a method named Count that takes a nullable LinkedListNode and returns an int.” Those are two different definitions with two different type signatures. They happen to share a name. C# allows this because the parameter lists distinguish them. When you call Count() with no arguments, C# picks the first one. When you call Count(someNode), C# picks the second.

Here is Count written recursively using method overloading:

public int Count() => Count(this.head);
 
private int Count(LinkedListNode? node)
{
    if (node == null) return 0;
    return 1 + Count(node.Next);
}

Translation of the public method: “Define a method named Count that takes no inputs and returns the result of calling Count with this.head.”

Translation of the private method: “Define a method named Count that takes a nullable LinkedListNode and returns an int. If node is null, return 0. Otherwise, return 1 plus the result of calling Count with node.Next.”

The public method is a one-line delegate. It passes this.head as the starting node, and the private method takes over from there. The recursive call inside the private method, Count(node.Next), resolves to the private overload because it matches the parameter list.

Switch expressions give us a shorter form. The two cases of the recursive definition become two arms in a switch:

public int Count() => Count(this.head);
 
private int Count(LinkedListNode? node) => node switch
{
    null => 0,
    _ => 1 + Count(node.Next)
};

Translation of the private method: “Define a method named Count that takes a nullable LinkedListNode and returns an int. If node is null, the result is 0. Otherwise, the result is 1 plus the result of calling Count with node.Next.”

The switch expression form matches the recursive definition closely. An empty list counts to 0. A non-empty list counts to 1 plus the count of the rest.

Look at the iterative and recursive translations side by side:

Iterative: Bind 0 to count. Bind this.head to current. While current is not null, increment count by 1, then advance current to current.Next. After the loop, return count.

Recursive: If node is null, the result is 0. Otherwise, the result is 1 plus the result of calling Count with node.Next.

The iterative version explains how to walk the list. The recursive version states what the answer is for an empty list and how to build it from the rest. They compute the same result, but they highlight different ways to think about the list.

Try it yourself.

Write a recursive version of Sum from the previous section. It should have a public method that takes no parameters and a private method that takes a nullable LinkedListNode and returns the sum of the values from that node onward. Use method overloading and a switch expression.

Reveal answer 
public int Sum() => Sum(this.head);
 
private int Sum(LinkedListNode? node) => node switch
{
    null => 0,
    _ => node.Value + Sum(node.Next)
};

Translation of the private method: “Define a method named Sum that takes a nullable LinkedListNode and returns an int. If node is null, the result is 0. Otherwise, the result is node.Value plus the result of calling Sum with node.Next.”

Self-correct against the model above.

Try it yourself.

Translate the following recursive method to English.

public bool Contains(int value) => Contains(this.head, value);
 
private bool Contains(LinkedListNode? node, int value) => node switch
{
    null => false,
    _ => node.Value == value || Contains(node.Next, value)
};
Reveal answer

Public method: “Define a method named Contains that takes an integer value and returns the result of calling Contains with this.head and value.”

Private method: “Define a method named Contains that takes a nullable LinkedListNode and an integer value and returns a bool. If node is null, the result is false. Otherwise, the result is whether node.Value equals value, or the result of calling Contains with node.Next and value.”

The recursive case uses short-circuit OR. If node.Value == value, the OR stops there and returns true without making the recursive call. If the values do not match, the OR evaluates the recursive call and returns its result. Three logical cases (empty, found, keep searching) fold into two arms in the switch.

If your answer differed, note what you missed before continuing.

From here on, this section uses whichever form matches the problem more directly. Methods that perform an action at each step or build a new list as they go are written iteratively. Methods that reduce a list to a single value in terms of its parts are written recursively. The exercises at the end ask you to rewrite several methods in the other form, so you practice both.

ForEach

In the previous section, Display traversed the list and printed each value. ForEach keeps that same traversal, but lets the caller choose the action performed at each node.

ForEach performs an action on each node and returns nothing. Since it walks through the list step by step, the iterative form fits naturally.

The array version of ForEach was a standalone function that took an array and an action:

Action<int[], Action<int>> ForEach = (arr, action) =>
{
    for (int i = 0; i < arr.Length; i++)
    {
        action(arr[i]);
    }
};
 
int[] scores = {85, 92, 78};
ForEach(scores, x => Console.WriteLine(x));

The function takes the array as its first parameter and the action as its second. At the call site, we pass both.

As a method on LinkedList, the array parameter disappears. The list is this. Only the action remains as a parameter:

public void ForEach(Action<int> action)
{
    LinkedListNode? current = this.head;
    while (current != null)
    {
        action(current.Value);
        current = current.Next;
    }
}

ForEach traverses the list from head to tail, calling the action on each node’s value.

LinkedList scores = new LinkedList();
scores.Prepend(78);
scores.Prepend(92);
scores.Prepend(85);
 
scores.ForEach(x => Console.WriteLine(x));

Output:

85
92
78

Translation for scores.ForEach(x => Console.WriteLine(x));: “Call the ForEach method on the object referred to by scores, passing a function that takes an integer x and displays it.”

The shift from standalone function to method is the same shift that turned earlier free-standing list functions into methods on LinkedList. The collection moves from inside the parentheses to the left of the dot, the parameter that held the collection becomes this, and the traversal changes from an index-based for loop to a reference-based while loop that follows node references. The higher-order idea stays the same: accept an action and apply it to each element.

The earlier Display method printed every value separated by spaces. ForEach generalizes that idea: Display is one particular action, while ForEach lets the caller choose the action.

Try it yourself.

What does this code display?

LinkedList data = new LinkedList();
data.Prepend(3);
data.Prepend(7);
data.Prepend(2);
data.Prepend(9);
 
data.ForEach(x => Console.WriteLine(x * 10));
Reveal answer

Output:

90
20
70
30

Prepend adds at the front, so the chain order is 9, 2, 7, 3. ForEach visits each node from head to tail and applies the action x => Console.WriteLine(x * 10), displaying each value multiplied by 10.

If your answer differed, trace through each Prepend to determine the chain order, then trace the ForEach call.

Try it yourself.

Write a ForEach call that displays only the values greater than 5. Use an if-statement inside the action.

Reveal answer 
data.ForEach(x =>
{
    if (x > 5)
    {
        Console.WriteLine(x);
    }
});

The action is a multi-statement lambda with curly braces and an if-statement inside. ForEach calls this action on every node. Only values greater than 5 produce output.

Self-correct against the model above.

Filter

ForEach applies an action to every element. Filter changes the job: it keeps some elements and discards others.

Filter selects the elements that satisfy a condition and collects them into a new list. Contains checked for one specific value. Filter generalizes that idea: instead of looking for one exact match, it keeps every value that passes a test.

The array version of Filter needed two passes through its input: one to count how many elements matched (because arrays have fixed size), and one to fill the result array. The linked list version needs only one pass, because Append grows the list without knowing the final size in advance:

public LinkedList Filter(Func<int, bool> predicate)
{
    LinkedList result = new LinkedList();
    LinkedListNode? current = this.head;
    while (current != null)
    {
        if (predicate(current.Value))
        {
            result.Append(current.Value);
        }
        current = current.Next;
    }
    return result;
}

Filter creates a new LinkedList containing only the values for which the predicate returns true, in their original order.

LinkedList scores = new LinkedList();
scores.Prepend(78);
scores.Prepend(92);
scores.Prepend(85);
scores.Prepend(60);
 
LinkedList passing = scores.Filter(x => x >= 80);
passing.Display();

Output:

85 92

Translation for scores.Filter(x => x >= 80): “Call the Filter method on the object referred to by scores, passing a predicate that takes an integer x and returns the result of evaluating x >= 80. Bind the returned LinkedList to passing.”

Filter uses Append rather than Prepend so the result stays in the same order as the original chain. If it used Prepend, the matching values would come out reversed.

The result is a separate LinkedList with its own nodes. Changing the original list after filtering does not affect the filtered list, and vice versa.

Try it yourself.

A LinkedList contains the values 15, 8, 22, 3, 17 (in chain order from head to tail). What values does data.Filter(x => x > 10) produce, and in what order?

Reveal answer

The predicate x > 10 is true for 15, 22, and 17. The result list contains those three values in their original order: 15, 22, 17.

8 and 3 do not satisfy the predicate and are excluded.

If your answer differed, trace through each node and check the predicate.

Try it yourself.

Write a Filter call that keeps only negative values from a LinkedList named temps.

Reveal answer 
LinkedList negatives = temps.Filter(x => x < 0);

Self-correct against the model above.

Map

Filter keeps or discards elements. ForEach performs an action and returns nothing. Map does something else: it builds a new list by replacing each element with a transformed version of itself.

Map transforms each element of a list and collects the results into a new list. Where Filter decides which elements to keep, Map decides how to change them.

The array version of Map took an array and a transform function and returned a new array where every element had been transformed. The method version works the same way, with the list as this instead of a parameter:

public LinkedList Map(Func<int, int> transform)
{
    LinkedList result = new LinkedList();
    LinkedListNode? current = this.head;
    while (current != null)
    {
        result.Append(transform(current.Value));
        current = current.Next;
    }
    return result;
}

Map creates a new LinkedList where each value is the result of applying the transform function to the corresponding value in the original list.

LinkedList scores = new LinkedList();
scores.Prepend(78);
scores.Prepend(92);
scores.Prepend(85);
 
LinkedList curved = scores.Map(x => x + 10);
curved.Display();

Output:

95 102 88

Translation for scores.Map(x => x + 10): “Call the Map method on the object referred to by scores, passing a function that takes an integer x and returns x + 10. Bind the returned LinkedList to curved.”

Map does not modify the list it is called on. It creates and returns a new list with the transformed values. The two lists are independent: each has its own nodes, and modifying one does not affect the other.

Like Filter, Map uses Append to preserve order. The first value in the original list maps to the first value in the result.

Try it yourself.

A LinkedList contains the values 4, 9, 16. What does data.Map(x => x * x) produce?

Reveal answer

The result list contains 16, 81, 256. Each value is squared: 4×4 = 16, 9×9 = 81, 16×16 = 256.

Try it yourself.

What goes wrong if Map uses Prepend instead of Append? Predict the output of this modified version on a list containing 1, 2, 3:

public LinkedList MapBroken(Func<int, int> transform)
{
    LinkedList result = new LinkedList();
    LinkedListNode? current = this.head;
    while (current != null)
    {
        result.Prepend(transform(current.Value));
        current = current.Next;
    }
    return result;
}
LinkedList broken = data.MapBroken(x => x * 10);
broken.Display();
Reveal answer

Output:

30 20 10

The traversal visits 1, 2, 3 in order. Prepend adds each transformed value at the front: first 10, then 20 ahead of 10, then 30 ahead of 20. The result is reversed: 30, 20, 10 instead of 10, 20, 30.

Compare your answer and note what you missed.

Fold

Sum and Count both reduce an entire list to one value. Fold makes that shared pattern explicit.

Fold reduces a list down to a single value. It takes an initial value and a combine function, then builds one result from every element. Sum, Count, and finding the maximum all follow that same pattern: start with something, then combine it with each element in turn.

The definition of Fold on a linked list is itself recursive. The fold of an empty list is the initial value, because there is nothing to combine. The fold of a non-empty list is the fold of the rest of the list, with the combine function applied to the initial value and the current element producing the new initial value. Each step absorbs one element into the accumulator and passes it forward to the next call.

public int Fold(int initial, Func<int, int, int> combine) =>
    Fold(this.head, initial, combine);
 
private int Fold(LinkedListNode? node, int acc, Func<int, int, int> combine) =>
    node switch
    {
        null => acc,
        _ => Fold(node.Next, combine(acc, node.Value), combine)
    };

Translation of the private method: “Define a method named Fold that takes a nullable LinkedListNode, an integer accumulator, and a combine function, and returns an int. If node is null, the result is acc. Otherwise, the result is the fold of node.Next, using combine(acc, node.Value) as the new accumulator.”

The two arms of the switch expression match the two cases of the definition. An empty list folds to whatever the accumulator currently holds. A non-empty list folds the rest of the list with an updated accumulator that already includes the current element.

Here is a call on a simple list:

LinkedList scores = new LinkedList();
scores.Prepend(78);
scores.Prepend(92);
scores.Prepend(85);
 
int total = scores.Fold(0, (a, b) => a + b);
Console.WriteLine(total);

Output:

255

Translation for scores.Fold(0, (a, b) => a + b): “Call the Fold method on the object referred to by scores, with initial value 0 and combine function (a, b) ⇒ a + b. Bind the returned value to total.”

Trace through the call the same way we traced recursive functions like Factorial and SumTo. The chain holds 85, 92, 78 (head to tail). The public Fold calls the private Fold with the head, 0, and the combine function:

Fold(node(85), 0, combine)
    = Fold(node(92), combine(0, 85), combine)
    = Fold(node(92), 85, combine)
    = Fold(node(78), combine(85, 92), combine)
    = Fold(node(78), 177, combine)
    = Fold(null, combine(177, 78), combine)
    = Fold(null, 255, combine)
    = 255

Each call advances to node.Next and updates the accumulator. When node reaches null, the switch expression returns the accumulator unchanged.

Notice the shape of each line. Once Fold hands off to the next recursive call, nothing is left for the caller to do: it will simply return whatever comes back. There is no “plus one” waiting outside the call, no multiplication pending, no list being built up after the call returns. That shape has a name.

Tail recursion is recursion where the recursive call is the last operation in the method.

Fold is tail-recursive. Each step updates the node and the accumulator, then hands off. Because nothing accumulates on the call stack across calls, a tail-recursive method can be rewritten as a loop in a mechanical way: the parameters of the recursive call become the updated values of the loop variables, and the recursive call itself becomes “go back to the top of the loop.” The iterative Fold in the exercises below is exactly that conversion.

The recursive Sum from the earlier exercise is different. Its recursive case is node.Value + Sum(node.Next), which has work waiting after the call returns: the addition cannot happen until the recursive call finishes. That is not tail recursion, and the conversion to a loop is less direct.

The earlier Sum method computed the same total as this Fold call, but with a hand-written loop. Fold can express that method in a single call:

// The earlier Sum method:
public int Sum()
{
    int sum = 0;
    LinkedListNode? current = this.head;
    while (current != null)
    {
        sum += current.Value;
        current = current.Next;
    }
    return sum;
}
 
// The same computation as a Fold call:
int total = scores.Fold(0, (a, b) => a + b);

The initial value 0 matches the initialization of sum. The combine function (a, b) => a + b matches the sum += current.Value inside the loop. Fold packages that accumulation pattern into a method that accepts the combining operation as a parameter.

Count works the same way. The combine function ignores the element value and adds 1 to the accumulator:

int count = scores.Fold(0, (acc, x) => acc + 1);

Sum and Count are specific instances of the general pattern that Fold captures.

Try it yourself.

Write a Fold call that computes the product of all values in a list named factors. Use 1 as the initial value.

Reveal answer 
int product = factors.Fold(1, (acc, x) => acc * x);

The initial value is 1 (the multiplicative identity). The combine function multiplies the accumulator by each element.

Self-correct against the model above.

Try it yourself.

Trace data.Fold(0, (acc, x) => acc + 1) on a list containing 10, 20, 30, 40. Show the recursive unwinding the way we traced the call above.

Reveal answer 
Fold(node(10), 0, combine)
    = Fold(node(20), combine(0, 10), combine)
    = Fold(node(20), 1, combine)
    = Fold(node(30), combine(1, 20), combine)
    = Fold(node(30), 2, combine)
    = Fold(node(40), combine(2, 30), combine)
    = Fold(node(40), 3, combine)
    = Fold(null, combine(3, 40), combine)
    = Fold(null, 4, combine)
    = 4

Return value: 4. This Fold call counts the number of elements in the list. The combine function ignores the element value and adds 1 to the accumulator on each call.

Compare your answer and note what you missed.

Try it yourself.

Trace data.Fold(100, (acc, x) => acc - x) on a list containing 10, 25, 30. What is the return value?

Reveal answer 
Fold(node(10), 100, combine)
    = Fold(node(25), combine(100, 10), combine)
    = Fold(node(25), 90, combine)
    = Fold(node(30), combine(90, 25), combine)
    = Fold(node(30), 65, combine)
    = Fold(null, combine(65, 30), combine)
    = Fold(null, 35, combine)
    = 35

Return value: 35.

If your answer differed, check whether you used the correct initial value and applied the combine function in the right order (accumulator first, element second).

Try it yourself.

Write Fold iteratively. Your version should be a single method that takes an initial value and a combine function, starts an accumulator at the initial value, traverses the list with a while loop, and updates the accumulator at each node.

Reveal answer 
public int Fold(int initial, Func<int, int, int> combine)
{
    int acc = initial;
    LinkedListNode? current = this.head;
    while (current != null)
    {
        acc = combine(acc, current.Value);
        current = current.Next;
    }
    return acc;
}

Translation: “Bind initial to acc. Bind this.head to current. While current is not null, replace acc with the result of calling combine with acc and current.Value, then advance current to current.Next. After the loop, return acc.”

The iterative version uses a single method with no overloading. The loop mirrors the recursive call because Fold is tail-recursive: the recursive version’s only remaining step after each call is to return whatever comes back, so a loop that updates acc and current in place covers the same ground. Both versions produce the same result on every input.

Self-correct against the model above.

Composing Higher-Order Methods

Once these methods return either a new list or a final value, we can chain them together.

Each method returns a LinkedList (or a value in Fold’s case), so one call can feed directly into the next. Filter produces a list, and that returned list has Map, Filter, and Fold methods of its own. Chain them together with the dot operator:

LinkedList scores = new LinkedList();
scores.Prepend(78);
scores.Prepend(92);
scores.Prepend(85);
scores.Prepend(60);
scores.Prepend(45);
 
int passingTotal = scores.Filter(x => x >= 70).Fold(0, (a, b) => a + b);
Console.WriteLine(passingTotal);

Output:

255

Translation: “Call Filter on the object referred to by scores with the predicate x >= 70. On the returned list, call Fold with initial value 0 and combine function (a, b) ⇒ a + b. Bind the returned value to passingTotal.”

Filter produces a new list containing 85, 92, 78, and Fold sums that list to produce 255.

Composing the standalone array versions required nesting the calls:

int result = Fold(Filter(scores, x => x >= 70), 0, (a, b) => a + b);

That reads inside out: identify the Filter call, wrap it in Fold, and sort out which arguments belong to which function. The method version reads left to right: start with scores, filter it, then fold the result.

Chain Map the same way:

LinkedList doubled = scores.Filter(x => x >= 70).Map(x => x * 2);
doubled.Display();

Output:

170 184 156

Filter keeps 85, 92, 78, and Map doubles each one. The operations apply in order from left to right.

Try it yourself.

Write a single chained expression that takes a LinkedList named grades, keeps only values below 60, and counts how many there are.

Reveal answer 
int failCount = grades.Filter(x => x < 60).Fold(0, (acc, x) => acc + 1);

Filter produces a list of failing grades. Fold counts them by adding 1 for each element, ignoring the element’s value.

Self-correct against the model above.

Try it yourself.

What does this expression produce on a list containing 3, 7, 2, 8, 1?

int result = data.Filter(x => x > 4).Map(x => x * 10).Fold(0, (a, b) => a + b);
Reveal answer

Filter keeps values greater than 4: 7, 8. Map multiplies each by 10: 70, 80. Fold sums them: 0 + 70 + 80 = 150.

The result is 150.

If your answer differed, trace each step separately: first determine which values Filter keeps, then apply Map to that list, then trace the Fold.

Review

Attempt each exercise from memory, then search this section to check your answers, then note what you missed.

Part 1: Definitions

Write the definitions from memory, then find them in this section to check.

  1. What is method overloading?
  2. What is tail recursion?

Review from earlier:

  1. What is a higher-order function?
  2. What is a method?
  3. What is recursion?
  4. What is a base case?
  5. What is a recursive case?

If any of your answers differed from the definitions, note what you missed and write the corrected version.

Part 2: Translations

Translate each piece of code to English.

  1. scores.ForEach(x => Console.WriteLine(x));

  2. LinkedList big = values.Filter(x => x > 100);

  3. LinkedList negated = data.Map(x => -x);

  4. int total = prices.Fold(0, (acc, p) => acc + p);

  5. int count = items.Filter(x => x > 0).Fold(0, (acc, x) => acc + 1);

  6. Translate the following recursive method:

public int Max() => Max(this.head);
 
private int Max(LinkedListNode? node) => node switch
{
    null => int.MinValue,
    _ => Math.Max(node.Value, Max(node.Next))
};

Check your translations against the patterns shown earlier in this section.

Part 3: Writing Code

Write the code for each description. Do not look at the examples in this section.

  1. Write a ForEach call that displays the square of every value in a LinkedList named nums.

  2. Write a Filter call that keeps only the even values from a LinkedList named data. (An integer x is even when x % 2 == 0.)

  3. Write a Map call that subtracts 5 from every value in a LinkedList named temps.

  4. Write a Fold call that finds the largest value in a LinkedList named heights. Use int.MinValue as the initial value (the smallest possible integer, so any element will be larger).

  5. Write a chained expression that takes a LinkedList named scores, keeps only values of 90 or above, and computes their sum.

  6. Write a recursive version of ForEach using method overloading. The public method takes an Action<int> and delegates to a private method that takes a nullable LinkedListNode and the action.

  7. Write a recursive version of Contains using method overloading and a switch expression.

  8. Write a recursive method named Max that returns the largest value in a LinkedList. Use method overloading. For the base case where node is null, return int.MinValue. For the recursive case, compare node.Value to the result of calling Max on node.Next and return whichever is larger. You can use Math.Max(a, b) to get the larger of two integers.

Part 4: Tracing

Trace data.Fold(1, (acc, x) => acc * x) where data contains values 5, 3, 4 (head to tail). Show the recursive unwinding, as in the Fold section.

What is the return value? What does this Fold call compute?

Part 5: Bug Identification

Find and fix the bug in each piece of code.

Bug 1. This Map method produces reversed output.

public LinkedList Map(Func<int, int> transform)
{
    LinkedList result = new LinkedList();
    LinkedListNode? current = this.head;
    while (current != null)
    {
        result.Prepend(transform(current.Value));
        current = current.Next;
    }
    return result;
}

Bug 2. This Fold call is supposed to compute the sum, but it returns a value that is too large.

int total = scores.Fold(100, (a, b) => a + b);

Bug 3. This code is supposed to display only the values above 50 from a list, but it displays all the values instead.

LinkedList result = scores.Filter(x => x > 50);
scores.Display();

Search this section for the correct patterns to verify your fixes.

Part 6: Concept Connections

  1. Express the earlier Sum method as a Fold call. What initial value and combine function would produce the same result?

  2. Express Count as a Fold call. What does the combine function do with the element value?

  3. Can Contains be expressed as a Fold call? If so, what types are involved? If not, what makes it different from Sum and Count?

  4. The standalone ForEach that took an array and the method ForEach defined here compute the same thing. Describe the differences in terms of where the collection comes from, how the loop works, and what the call site looks like.

  5. ForEach, Filter, and Map are written iteratively here, while Fold is written recursively. Explain why each choice fits the problem. Your answer should address what each method produces and how that shapes which form reads more clearly.

  6. Filter and Map both build new lists as they traverse. A recursive version of Filter that tried to construct the result list by returning node chains directly would run into a specific structural problem with the LinkedList wrapper class. Describe what the problem is. (This question is open-ended. There is no single right answer.)

ForEach, Filter, Map, and Fold now work on linked lists. The traversal changed from indices to references, but the main idea stayed the same: keep the traversal structure and let the caller supply the behavior.

Every method here still operates on int values. The node stores an int, Filter’s predicate takes an int, and Map’s transform takes an int and returns an int. The element type is the next thing to generalize: instead of hard-coding int, the list itself can be parameterized by type, so the same methods work for rectangles, strings, and anything else.

Backlinks