Summary
We looked at some more list algorithms in this chapter and how lists permeate functional programming.
Modeling binary numbers as an integer list of just 0 or 1 is very easy. List operations perform best when they work at the head, allowing you to have maximum sharing and least copying. So we reversed the number's list to express our algorithms.
We looked at addition and multiplication algorithms. Next, we covered the concept of greediness and backtracking. We saw how these concepts drive regular expression matching.
We then looked at a fun problem: how to satisfy an amount, given a set of coin denominations. We looked at the greedy version, which proved to be too greedy at times. This was fixed with a backtracking solution.
Hopefully, this ...
Get Learning Functional Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
