Chapter 8. Advanced list handling

 

This chapter covers

  • Speeding list processing with memoization
  • Composing List and Result
  • Implementing indexed access on lists
  • Unfolding lists
  • Automatic parallel list processing

In chapter 5, you created your first data structure, the singly linked list. At that point, you didn’t have at your disposal all the techniques needed to make it a complete tool for data handling. One particularly useful tool you were missing was some way to represent operations producing optional data, or operations that can produce an error. In chapters 6 and 7, you learned how to represent optional data and errors. In this chapter, you’ll learn how to compose operations that produce optional data or errors with lists.

You also developed some functions that were far from optimal, such as length, and I said that you’d eventually learn more-efficient techniques for these operations. In this chapter, you’ll learn how to implement these techniques. You’ll also learn how to automatically parallelize some list operations in order to benefit from the multicore architecture of today’s computers.

8.1. The problem with length

Folding a list involves starting with a value and composing it successively with each element of the list. This obviously takes an amount of time proportional to the length of the list. Is there any way to make this operation faster? Or, at least, is there a way to make it appear faster?

8.2. Composing List and Result

8.3. Abstracting common List use cases

8.4. Automatic parallel processing of lists

8.5. Summary