Summary
We looked at lists again, but in a different light. We revisited the list prepending and appending techniques and saw that prepending a node to a list has O(1) complexity. It is a very fast operation, sharing most of the existing list.
Appending to a list is very costly though, as we end up copying the entire existing list. We looked at list reversal and saw how we could express the list reversal algorithm in terms of list prepending.
Next, we saw how extensively list prepending is used. We looked at directed graphs, modeling them as a list of pairs.
We also implemented common graph algorithms, such as getting successors of a node and a depth-first traversal.
Incrementally tweaking the depth-first traversal, we came up with topological sorting, ...
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.
