O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required