Understanding Nested Iteration: a Key to Success in RB101
In my judgment being able understand nested iteration on a conceptual and practical level is a key to success in RB101. This is not a surprise since this complex topic presents itself in both curriculum content and practice problems. This article is written for the student who is new to programming and is overwhelmed by the palindrome_substrings problem that features nested iteration in the “Introduction to PEDAC process” Assignment from Lesson 4.
Nested iteration stretches a beginning programmer’s ability to its maximum boundaries because of the complexity needed to perform such a task. There are many things that can go wrong. Even a small error in syntax or implementation is exacerbated by the multiple moving parts and actions taking place. When an unexpected value is returned it can be very difficult to pinpoint where exactly the error has occurred. In other words, it’s easy to get lost in the code.
Understanding With an Example
Understanding a difficult topic can be made easier through a comparison to a simple to understand real life example. This can help to solidify a mental model that can then be applied with more confidence to novel examples of the topic. Thus, when a mental model is firmly established the abstract becomes more comprehensible.
A simple example that I drafted to understand nested iteration better is the task of collecting coins from parking meters (imagine that parking meters still accept coins). Let’s examine the tasks to see how this can be applied to nested iteration.
This is a relatively simple and easy to understand process. For this example there will be an outer iteration and an inner, nested, iteration. Within the inner iteration an action will take place.
This is a helpful example because it represents each iteration as movement. The outer iteration is walking. The inner iteration is going over the coins. Mentally, this can be a useful approximation of what happens during iteration over data structures since they can be thought of as being traversed.
Modeling the example in code
Given the following array where each subarray represents a parking meter and each element in the array represents a coin type.
The task is to calculate the total quarters, dimes and nickels by returning a hash. The hash will have the coin type as a key and an integer count as a value. The expected output will be this:
Given the data structure that will be traversed as well as the expected output a higher level algorithm can be composed within the context of this example.
Coding Strategy: Outsource to helper methods
For problems of nested iteration like this there seem to be two main coding strategies:
1) To code it all in one place within a single method
Although there is a certain sense of security that comes from solving a problem within a single method this approach can be problematic with nested iteration since it is difficult to test the different parts of the method as it is being built. Additionally, if an error occurs it is difficult to pinpoint where the error occurred to troubleshoot and remedy it.
2) To outsource functionality to helper methods
Using multiple methods increases the conceptual burden to a certain extent since helper methods must be constructed independently and plugged in. However, for difficult problems with nested iteration the trade off is worth it since it allows for testing on the go as well as simpler troubleshooting. This is the strategy I have elected to demonstrate with this example. This strategy will break down a complex problem into smaller, simpler problems.
Building the main method
A framework for the main method is illustrated in the code snippet below. Within the context of this problem initializing the hash to track the coins and returning it is straightforward (lines 2 and 11 ). Likewise, the outer iteration on line 4 is fairly simple to implement. It’s the nested iteration and subsequent actions within this that are difficult to represent in code. The commented out notes will help bridge the gap between concept and code. It’s apparent that we need a method to tally the coins and that this helper method will interact with both the block parameter parking_meter and the meter_count hash. Simply put those will be the arguments supplied to the helper method.
Building the helper method
This is the substantial part of the problem. It’s a good idea to revisit the algorithm and add additional details:
Using the details from the algorithm the helper method can be drafted. In the code snippet below the parameters are parking_meter and meter_count which we’ve already determined. It’s been named tally_coins! as a descriptive name appended with ! since the meter_count hash will be mutated (the counts will be incremented). Lastly, the iteration on line 2 will consider the index of each element of the array, this is an important detail.
Referring to the code snippet below, the next step is adding functionality to determine the type of coin and increment the corresponding hash key/value pair appropriately. Conditional logic is used with an if expression to identify the index of the current iteration. Depending on the index the appropriate value of meter_count is accessed via bracket notation and incremented.
Testing the Helper Method
A benefit of using a helper method is that this key detail in the solution can be tested independently. This is important since after a successful test one can conclude that the helper method will work as anticipated. This will give a higher level of confidence when working through a complex problem as well as eliminate an option to troubleshoot if things are to go wrong. If something has been verified to work at an acceptable level it cannot be the source of an error. The helper method in this example can be tested independently and apart from any other code. In the code snippet below an empty meter_count is successfully incremented by tally_coins! .
Plugging the Helper Method Into the Main Method
It’s as simple as line 5. There is a functional and tested tally_coins! helper method. This helper method performs the nested iteration and operations needed. The method is called for each outer iteration. The code snippet below shows another benefit of using helper methods: simplicity. The code below is much simpler to read and understand than a solution that doesn’t rely on helper methods.
Running the Code
At this point one can anticipate the code will produce the correct output because of the benefits of independently testing the helper method. That is the point of being in control of the code: solutions are tested along the way and problems are identified and corrected.
Putting It All Together
With nested iteration the difficulty isn’t really with the individual steps in isolation. It’s the interaction of these steps within a nested context that adds a substantial burden of difficulty. Having both a conceptual understanding and functional ability with nested iteration is a key to success in RB101 and beyond. This means having a familiar mental model as well as the capability to apply that model to solve problems in code. I encourage new programmers to experiment with their own mental models and example problems to increase their ability and confidence.
