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.

Subscribe to our blog via email

Email subscriptions come from our Atom feed and are handled by Blogtrottr. You will only receive notifications of blog posts, and can unsubscribe any time.