Edit this page

Data Structures

You mean Haskell has things besides lists???

It’s important to focus on data structures, since getting your data right is step 1 to great Haskell code.

Generic data structures

There are three basic flavors to the data structures

  • Sequences: list, vector, ByteString, Text, and Seq (not covered)
    • Order of values matters
    • Can have multiple copies of the same value
  • Maps: Map, HashMap, IntMap
    • Map a key to a value
    • Aka, dictionary
    • Each key only appears once
  • Sets: Set, HashSet, IntSet
    • Map without values
    • Like a sequence, but (1) order undefined and (2) no duplicates

API design

  • Each of these families has very similar APIs (though not quite identical).
  • Learning one will help you master the others.
    • Yes, this means you already know most of the vector, ByteString, and Text APIs.
  • The Map and Set APIs are also very similar.
  • APIs are designed to be imported qualified (lots of conflicting names)
  • Later: we’ll look at mono-traversable for typeclasses to unify these APIs.

Laziness

  • Lists are fully lazy
  • Lazy ByteString and Text still have strict chunks
  • Boxed vectors are spine strict
  • Map has strict and lazy modules, different impacts on values
  • Unboxed and storable vectors are fullhy strict.

Impacts: undefined, infinite structures, performance, memory usage.

Some caveats

  • Unlike the other sequences, ByteString and Text are monomorphic
  • There are three common flavors of Vector, we’ll cover the differences later
  • IntMap and IntSet requires Int keys
  • Some of the structures have constraints on keys or values

There are also ByteString and Text builders for efficient construction.

Quiz: Pick the data structure

  • Names of all students in a class
  • Names and grades of all students in a class
  • All the prime numbers
  • The first 1000 prime numbers
  • Whitelist of allowed email addresses to access a resource

We’ll come back to this quiz after we explore the data types in more detail.