When diving into the world of Haskell, understanding its data structures is paramount. Among the most fundamental are Haskell Lists, Arrays, Vectors, and Sequences. These structures provide different ways to organize and manipulate data, each with its own strengths and weaknesses. Choosing the right data structure can significantly impact the performance and efficiency of your Haskell programs. This article will explore these core data structures in Haskell, highlighting their characteristics, use cases, and how to leverage them effectively for various programming tasks. By the end, you’ll have a solid foundation for selecting the appropriate data structure for your specific needs, improving your Haskell code’s clarity and performance. We’ll cover everything from the lazy evaluation of lists to the efficient indexing of arrays and vectors, and the versatile nature of sequences.

Understanding Haskell Lists

Haskell Lists are the most basic and commonly used data structure in Haskell. They are singly linked lists, meaning each element points to the next. Lists in Haskell are homogeneous, meaning they can only contain elements of the same type. They’re also immutable; you can’t change a list in place, but you can create new lists based on existing ones. This immutability contributes to the purity and referential transparency that Haskell is known for.

A key feature of Haskell Lists is their lazy evaluation. Elements of a list are only computed when they are actually needed. This allows for the creation of infinite lists, which can be incredibly powerful for representing streams of data or generating values on demand. For example, you can define an infinite list of natural numbers using list comprehension: [1..]. Only the numbers that are actually accessed will be computed, making this a very efficient way to represent a potentially unbounded sequence.

Lists are incredibly versatile and are used extensively in Haskell programming. They are easy to create, manipulate, and process using various built-in functions like map, filter, and fold. However, due to their linked-list nature, accessing elements by index can be inefficient, requiring traversal from the head of the list. For performance-critical applications where random access is frequent, other data structures like arrays or vectors are more suitable. According to “Real World Haskell” [Real World Haskell Book], lists are ideal for situations where the sequence length is unknown or when lazy evaluation is desired.

Exploring Haskell Arrays

Haskell Arrays offer a more efficient alternative to lists when random access is required. Unlike lists, arrays provide constant-time access to elements by index. This makes them suitable for applications where you need to frequently retrieve or modify elements at specific positions. Haskell provides several types of arrays, including immutable arrays (Array), mutable arrays (IOUArray and STUArray), and unboxed arrays (UArray).

Immutable arrays (Array) are similar to lists in that they cannot be modified after creation. However, they offer much faster random access. Mutable arrays, on the other hand, allow you to change the values of elements after the array has been created. These are typically used within monadic contexts like IO or ST to maintain purity. Unboxed arrays (UArray) are even more efficient, as they store the values directly in the array without boxing, reducing memory overhead and improving performance, especially for primitive types like integers and floats. As stated by Simon Peyton Jones in “The Implementation of Functional Programming Languages” [Functional Programming Languages Implementation], the choice of array type depends heavily on the specific application requirements and the trade-offs between immutability and performance.

Arrays are particularly useful in numerical computations, simulations, and other applications where fast random access is crucial. For example, if you’re implementing a matrix operation, using arrays to store the matrix elements can significantly improve performance compared to using lists. However, arrays have a fixed size, which needs to be known at creation time. This can be a limitation in situations where the size of the data is not known in advance. “Haskell Data Structures and Algorithms” [Haskell DSA] recommends using arrays when data size is known and random access is the priority.

Delving into Haskell Vectors

Haskell Vectors provide a high-performance alternative to lists and arrays, offering a balance between flexibility and efficiency. Vectors are similar to arrays in that they provide fast random access, but they also offer more advanced features like efficient slicing and concatenation. The vector package in Haskell provides several types of vectors, including boxed vectors (containing pointers to values), unboxed vectors (containing primitive values directly), and immutable and mutable variants. Vectors are often preferred over lists and arrays when performance is critical, and the data is relatively small and fits in memory.

One of the key advantages of vectors is their efficient implementation of common operations like slicing and concatenation. Slicing allows you to create a new vector that contains a subset of the original vector’s elements, without copying the underlying data. Concatenation allows you to combine two vectors into a single vector efficiently. These operations are implemented using techniques like pointer manipulation and memory sharing, which minimize memory allocation and copying.

Vectors are widely used in areas such as scientific computing, data analysis, and game development, where performance is paramount. For example, in a physics simulation, vectors can be used to represent the positions and velocities of objects, allowing for efficient updates and calculations. Similarly, in a data analysis pipeline, vectors can be used to store numerical data, enabling fast computations and transformations. Vectors also integrate well with other Haskell libraries and frameworks, making them a versatile choice for a wide range of applications. Here’s what makes Vectors a good choice:

• Efficient random access.
• Optimized for numerical computations.
• Support for slicing and concatenation.

Understanding Haskell Sequences

Haskell Sequences are a powerful and flexible data structure that provides a general interface for working with ordered collections of data. Unlike lists, arrays, and vectors, sequences are not a specific data type but rather an abstraction that can be implemented using various underlying data structures. This allows you to write code that is agnostic to the specific representation of the data, making it more reusable and adaptable. The Data.Sequence module in Haskell provides an efficient implementation of sequences based on finger trees, which offer logarithmic time complexity for many common operations like indexing, splitting, and concatenation. This is the featured snippet paragraph.

Sequences are particularly well-suited for situations where you need to perform a variety of operations on a collection of data, and the specific performance characteristics of each operation are not critical. For example, you might use a sequence to represent a queue of tasks, where you need to add tasks to the end, remove tasks from the front, and occasionally access tasks in the middle. The logarithmic time complexity of sequences ensures that these operations remain reasonably efficient even for large collections of data.

Sequences also support a rich set of operations, including insertion, deletion, splitting, concatenation, and reversal. These operations can be combined to implement complex algorithms and data transformations in a concise and elegant way. The Data.Sequence module also provides functions for converting between sequences and other data structures like lists and vectors, making it easy to integrate sequences into existing Haskell code. Here’s how to create and use sequences:

1. Import the Data.Sequence module.
2. Create a sequence using functions like empty, fromList, or fromVector.
3. Perform operations on the sequence using functions like (<|) (prepend), (|>) (append), index, splitAt, and append.
4. Convert the sequence back to other data structures if needed.

When should I use a list instead of an array or vector?

Use lists when you need lazy evaluation, the size of the data is unknown, or you primarily perform operations at the beginning of the list. Lists are generally not suitable for random access due to their linear access time.

What are unboxed arrays and vectors, and when should I use them?

Unboxed arrays and vectors store primitive values directly in memory, without boxing, which reduces memory overhead and improves performance. Use them when working with primitive types like integers or floats and when performance is critical.

How do I choose between mutable and immutable arrays or vectors?

Choose immutable arrays or vectors when you want to ensure data integrity and avoid side effects. Choose mutable arrays or vectors when you need to modify the data in place, typically within monadic contexts like IO or ST to maintain purity.

What are the performance characteristics of sequences?

Sequences, implemented using finger trees, offer logarithmic time complexity for many common operations like indexing, splitting, and concatenation. They are a good choice when you need a balance between flexibility and efficiency.

Question & Answer :
I’m learning Haskell and read a couple of articles regarding performance differences of Haskell lists and (insert your language)’s arrays.

Being a learner I obviously just use lists without even thinking about performance difference. I recently started investigating and found numerous data structure libraries available in Haskell.

Can someone please explain the difference between Lists, Arrays, Vectors, Sequences without going very deep in computer science theory of data structures?

Also, are there some common patterns where you would use one data structure instead of another?

Are there any other forms of data structures that I am missing and might be useful?

Lists Rock

By far the most friendly data structure for sequential data in Haskell is the List

data [a] = a:[a] | [] 

Lists give you ϴ (1) cons and pattern matching. The standard library, and for that matter the prelude, is full of useful list functions that should litter your code (foldr, map, filter). Lists are persistent, aka purely functional, which is very nice. Haskell lists aren’t really “lists” because they are coinductive (other languages call these streams) so things like

ones :: [Integer] ones = 1:ones twos = map (+1) ones tenTwos = take 10 twos 

Work wonderfully. Infinite data structures rock.

Lists in Haskell provide an interface much like iterators in imperative languages (because of laziness). So, it makes sense that they are widely used.

On the other hand

The first problem with lists is that to index into them (!!) takes ϴ (k) time, which is annoying. Also, appends can be slow ++, but Haskell’s lazy evaluation model means that these can be treated as fully amortized if they happen at all.

The second problem with lists is that they have poor data locality. Real processors incur high constants when objects in memory are not laid out next to each other. So, in C++ std::vector has faster “snoc” (putting objects at the end) than any pure linked list data structure I know of, although this is not a persistent data structure so less friendly than Haskell’s lists.

The third problem with lists is that they have poor space efficiency. Bunches of extra pointers push up your storage (by a constant factor).

Sequences Are Functional

Data.Sequence is internally based on finger trees (I know, you don’t want to know this) which means that they have some nice properties

1. Purely functional. Data.Sequence is a fully persistent data structure.
2. Darn fast access to the beginning and end of the tree. ϴ (1) (amortized) to get the first or last element, or to append trees. At the thing lists are fastest at, Data.Sequence is at most a constant slower.
3. ϴ (log n) access to the middle of the sequence. This includes inserting values to make new sequences
4. High-quality API

On the other hand, Data.Sequence doesn’t do much for the data locality problem, and only works for finite collections (it is less lazy than lists)

Arrays are not for the faint of heart

Arrays are one of the most important data structures in CS, but they don’t fit very well with the lazy pure functional world. Arrays provide ϴ (1) access to the middle of the collection and exceptionally good data locality/constant factors. But, since they don’t fit very well into Haskell, they are a pain to use. There are actually a multitude of different array types in the current standard library. These include fully persistent arrays, mutable arrays for the IO monad, mutable arrays for the ST monad, and un-boxed versions of the above. For more check out the Haskell wiki

Vector is a “better” Array

The Data.Vector package provides all of the array goodness, in a higher level and cleaner API. Unless you really know what you are doing, you should use these if you need array-like performance. Of course, some caveats still apply – mutable array-like data structures just don’t play nice in pure lazy languages. Still, sometimes you want that O (1) performance, and Data.Vector gives it to you in a usable package.

You have other options

If you just want lists with the ability to efficiently insert at the end, you can use a difference list. The best example of lists screwing up performance tends to come from [Char] which the prelude has aliased as String. Char lists are convient, but tend to run on the order of 20 times slower than C strings, so feel free to use Data.Text or the very fast Data.ByteString. I’m sure there are other sequence oriented libraries I’m not thinking of right now.

Conclusion

90+% of the time I need a sequential collection in Haskell lists are the right data structure. Lists are like iterators, functions that consume lists can easily be used with any of these other data structures using the toList functions they come with. In a better world the prelude would be fully parametric as to what container type it uses, but currently [] litters the standard library. So, using lists (almost) everywhere is definitely okay.
You can get fully parametric versions of most of the list functions (and are noble to use them)

Prelude.map ---> Prelude.fmap (works for every Functor) Prelude.foldr/foldl/etc ---> Data.Foldable.foldr/foldl/etc Prelude.sequence ---> Data.Traversable.sequence etc 

In fact, Data.Traversable defines an API that is more or less universal across anything “list like”.

Still, although you can be good and write only fully parametric code, most of us are not and use lists all over the place. If you are learning, I strongly suggest you do too.

Based on comments I realize I never explained when to use Data.Vector vs Data.Sequence. Arrays and Vectors provide extremely fast indexing and slicing operations but are fundamentally transient (imperative) data structures. Pure functional data structures like Data.Sequence and [] let efficiently produce new values from old values as if you had modified the old values.

newList oldList = 7 : drop 5 oldList 

Doesn’t modify the old list, and it doesn’t have to copy it. So even if oldList is incredibly long, this “modification” will be very fast. Similarly

newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

Will produce a new sequence with a newValue for in the place of its 3000 elements. Again, it doesn’t destroy the old sequence, it just creates a new one. But, it does this very efficiently, taking O (log (min (k, k-n) where n is the length of the sequence, and k is the index you modify.

You can’t easily do this with Vectors and Arrays. They can be modified but that is a real imperative modification, and so can’t be done in regular Haskell code. That means operations in the Vector package that make modifications like snoc and cons have to copy the entire vector so takes O(n) time. The only exception to this is that you can use the mutable version (Vector.Mutable) inside the ST monad (or IO) and do all your modifications just like you would in an imperative language. When you are done, you “freeze” your vector to turn it into the immutable structure you want to use with pure code.

My feeling is that you should default to using Data.Sequence if a list is not appropriate. Use Data.Vector only if your usage pattern doesn’t involve making many modifications, or if you need extremely high performance within the ST/IO monads.

If all this talk of the ST monad is leaving you confused: all the more reason to stick to pure fast and beautiful Data.Sequence.