8 Advanced list handling

 

In this chapter

    • 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 all the techniques needed to make this structure a complete tool for data handling. One particularly useful tool you were missing was some way to represent operations producing optional data or operations producing 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’re going to learn how to implement these more efficient 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

    8.2 The performance problem

    8.3 The benefits of memoization

    8.3.1 Handling memoization drawbacks

    8.3.2 Evaluating performance improvements

    8.4 List and Result composition

    8.4.1 Handling lists returning Result

    8.4.2 Converting from List<Result> to Result<List>

    8.5 Common List abstractions

    8.5.1 Zipping and unzipping lists

    8.5.2 Accessing elements by their index

    The zero element

    8.5.3 Splitting lists

    When not to use folds

    8.5.4 Searching for sublists

    8.5.5 Miscellaneous functions for working with lists

    8.6 Automatic parallel processing of lists

    8.6.1 Not all computations can be parallelized

    8.6.2 Breaking the list into sublists

    8.6.3 Processing sublists in parallel

    Summary