| title |
|---|
24 Days of Hackage: containers |
The basic linked list is a data structure that every aspiring computer programmer comes to know and love at some point early in their career. Haskell is no different here - the linked list is baked right into the language, including its own special syntax for construction and pattern matching. In fact, Haskell's linked list could be seen as even more powerful than those in other languages as lazy evaluation allows us to construct lists of infinite length.
With all that said, lists are not the end all of data structures - often we have
specific needs, such as O(1) retrieval, specific data access patterns to
optimize for, or perhaps just more speed. The containers library is one of the
answers to this problem.
Containers is a library in
the Haskell platform which provides implementations of maps, sets, sequences,
graphs and trees. The current maintainer is
Johan Tibbel - so you know its going to be fast!
(Johan has
blogged
about performance a few times, and regularly talks on the topic)
So, how does the API look? After all - we spent all this time learning how to
fold and map in our Haskell infancy, it would be a pain if this knowledge
doesn't carry forward. Luckily, it does. All the structures provided by
containers feature instances of various Haskell type classes, such as
Functor, Traversable and Foldable. Of course, each structure offers
something new to the table, so while there are a few more functions to be aware
of the documentation is fantastic and easy to navigate.
As a quick example, lets assume we have a function that does some IO to give us
a mapping from a Person to a Set of their favourite Colours.
peopleFavColours :: IO (Map Person (Set Colour))
peopleFavColours = ...Now, what if we want to find a Set of all favourite colours? Presumably, we
just take all the Sets of Colours for all people and "smash" them together
into a new set. Hmm, this "smashing" together sounds exactly like something a
fold, perhaps with a Monoid instance...
allFavColours :: IO (Set Colour)
allFavColours = fold <$> peopleFavColoursBecause Map k is an instance of Foldable, and Set is an instance of
Monoid, we can simply fold our Map Person (Set Colour) down into a single
Set Colour; the Monoid Set instance for combining multiple Sets together
is simply the union of them.
Finally, what if we wanted to print out each of these colours, one per line?
Iteration with side effects sounds like something we could do with a function
like mapM_. Again, the trusty Foldable type class can help us out, with
mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ():
showColours :: IO ()
showColours = allFavColours >>= mapM_ printSet is Foldable - so this code is identical to the code to do this for a
list! Talk about reusable knowledge.
As mentioned before, containers is part of the Haskell platform and you most
likely already have it installed. It takes very little effort to get started,
and almost every application will find a need for these data structures at some
point.
Go on, have a play!