Lists

We start our data structures series by looking at lists, which are the most fundamental container we have in Haskell for multiple objects of the same type. If you're already familiar with lists you can browse the series page to learn more about other types!

You can also get a deeper look into Haskell's data structures by taking a look at our Data Structures eBooks!

What are lists good for?

Lists are the simplest structure for storing many items of the same type while maintaining an order. They provide fast access to the first element in the list, and can quickly remove this element or add a new element as the "head" of the list.

With all these features, lists work well as a "Stack" data structure - a Last-In-First-Out queue (LIFO). Depth-First-Search is an example of an algorithm where a basic list can get you started.

Lists have minimal overhead compared to other structures, so if you're doing some algorithm that requires accessing all your items, they're often a good choice.

What are lists not as good for?

Lists have no special way to access elements with particular properties. So if you want to know if your list contains a particular item, or if you want to find the minimum, these are O(n) operations on a list. Accessing any elements in the latter part of the list, even if you know their numeric index i, will also take O(i) time. The only "efficient" access is the first element.

List Parameters and Constraints

Lists have a single type parameter for the contained type. There are no constraints on this type; anything can go in a list.

How do I create a list?

Lists are a fundamental syntactic construct in Haskell. To construct a list, you simply place all the elements within "brackets" separated by commas. An empty set of brackets indicates an empty list.

>> let emptyList = []
>> let a = [1, 2]
>> let b = ["Hello", "World"] :: [String]

How do I get the size of a list?

Use the length function from Prelude or Data.List. This works for any Foldable type, but it takes O(n) time.

length :: (Foldable f) => f a -> Int

How do I add elements to a list?

Use (:) to add a value to the front to the front of the list. This is very efficient - O(1).

>> let a = [1, 2, 3]
>> let b = 0 : a
>> b
[0, 1, 2, 3]

You cannot add values directly to the end of a list. You need to wrap them inside another list and use the append operator in the "Combination" section.

How do I access list elements?

You can access the first element of a list by using the head function. This is very efficient, but it will throw an error if the list is empty.

head :: [a] -> a

Similarly, you can access the final element with last, but this is an inefficient, O(n) operation. It will also throw an error on an empty list.

last :: [a] -> a

You can use the double-bang operator (!!) to access the element at a numeric index i, but it is also inefficient (O(i)), and will throw an error if your index is out of bounds.

(!!) :: [a] -> Int -> a

The last function we'll look at for accessing lists is take. This allows you to grab the first few elements of a list. This function is safe. If the number of elements is too great, you'll just get the full list.

take :: Int -> [a] -> [a]

How do I delete elements from a list?

You can use the tail function to "remove" the first element of a list, returning a list of all the remaining elements. This is efficient, but also throws an error with empty lists.

tail :: [a] -> [a]

Similarly, init will "remove" the last element, but this is inefficient (O(n)).

init :: [a] -> [a]

Finally, there is a drop function similar to take. It just removes the first few elements from the list. It is also a safe function, returning an empty list if you drop more elements than exist in the list.

drop :: Int -> [a] -> [a]

How do I combine lists?

Lists can be appended using the (++) operator. Lists also implement the Semigroup typeclass, so you can use the Semigroup/Monoid append operator (<>).

(++) :: [a] -> [a] -> [a]
(<>) :: (Semigroup c) => c -> c -> c

To append a list of length n to a list of length k is an O(n) operation.

Import Notes

While most of the basic functions for list manipulation live in the Prelude module, there are a multitude of helpful functions for operating on lists in the Data.List module.

Lists also implement the Foldable class, which opens the door for a number of other helpful functions in Data.Foldable.

There is less name overlap with these functions, so it is usually fine to import them unqualified:

import Data.List
import Data.Foldable

Other Notes

Using folds (foldr, foldl, foldl') is one of the most important skills you can learn to replicate basic "for loop" patterns in Haskell.

The basic String type is simply a list of characters:

type String = [Char]

This allows you to use many of those list functions in String contexts.

Conclusion

If you want to learn about more data structures in Haskell, make sure to head back to the series page! The next structure in the series is the Ordered Set.