Seq and complexity
Too long we’ve neglected
containers! We’re fixing that, starting with a page on
Seq.The paper that describes how
Seq works in detail, Finger Trees: A Simple General-purpose Data Structure, has been added to the timeline. The
containers library has been around since 2007 and is a central fixture in the Haskell ecosystem. It provides, notably,
Map, all different applications of
Ord-based tree data structures.
Additionally, we’ve added a page explaining the basics of time complexity. It goes over five big classes – constant, logarithmic, linear, polynomial, and exponential – with the goal of giving a broad overview of what asymptotic analysis is all about, helping you read the mathy bits of API documentation, and gaining an appreciation for why it matters that
Seq concatenation is logarithmic.