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, a sequence that respects precedence. We also implemented cycle detection and printing.
Hopefully, this gave you a taste of functional algorithms. In the next chapter, we will look at random access lists, yet another fascinating data structure-...
