Learning Functional Data Structures and Algorithms

Chapter 5.  More List Algorithms

In this chapter, we will look at some more list algorithms to see how lists permeate functional programming. For example, binary numbers could be represented as a list of 0 and 1.

We will apply all that we have learned so far to implement algorithms in order to perform binary arithmetic. Binary arithmetic works from right to left. The least significant bit (LSB) is the rightmost bit, where we will start working. However, we typically process lists from left to right. Getting a list head and prepending to a list are O(1) operations. We will see how a change in representation allows us to design algorithms in terms of list head and list prepend.

While doing binary arithmetic, we need to deal with a carry. The carry ...