Elixir Data Structures: Building Blocks of Functional Programming
In Elixir, data structures are fundamental to writing efficient and expressive code, especially within its functional programming paradigm. Unlike imperative languages where data structures are often mutable and modified in place, Elixir's data structures are immutable. This means that when you 'change' a data structure, you're actually creating a new one with the modifications. This immutability is a cornerstone of functional programming, enabling easier reasoning about code, concurrency, and fault tolerance.
Lists: Ordered Sequences
Elixir lists are linked lists, meaning they are composed of a head (the first element) and a tail (the rest of the list). They are represented using square brackets
[]
Lists are linked lists, efficient for prepending elements.
Lists in Elixir are built using a head and a tail. The | operator (the cons operator) is used to prepend an element to a list. For example, 1 | [2, 3] results in [1, 2, 3]. Accessing elements by index can be less efficient than in array-like structures.
Elixir lists are implemented as singly linked lists. Each element in a list is a node containing the element's value and a pointer to the next node. The list itself is a pointer to the first node (the head). The end of the list is marked by a special atom, :nil. The cons operator | is used to construct lists by prepending an element to an existing list. For instance, 1 | [2, 3] creates a new list [1, 2, 3]. While prepending is an O(1) operation, accessing elements by index (e.g., list !! index) is an O(n) operation because it requires traversing the list from the beginning.
Prepending elements using the cons operator |. This is efficient because lists are linked lists, and adding to the head is a constant time operation (O(1)).
Tuples: Fixed-Size Collections
Tuples are fixed-size collections of elements, where each element can be of a different type. They are represented using curly braces
{}
Tuples are fixed-size and allow O(1) access to any element.
Tuples are defined with curly braces, like {1, :atom, "string"}. You can access any element in a tuple by its index using the elem/2 function (e.g., elem({1, :atom}, 0) returns 1). Tuples are efficient for random access.
Tuples in Elixir are implemented as contiguous blocks of memory, allowing for constant-time access to any element by its index. This makes them ideal for scenarios where you need to retrieve specific pieces of data quickly. The size of a tuple is fixed at creation. When you need to 'modify' a tuple, you actually create a new one. The elem/2 function is used to retrieve an element at a specific index (0-based). For example, elem({:ok, 10}, 1) returns 10. Tuples are commonly used to return multiple values from a function, often in a pattern like {:ok, value} or {:error, reason}.
Tuples offer constant-time (O(1)) access to any element by its index, whereas lists require linear time (O(n)) for indexed access.
Maps: Key-Value Stores
Maps are Elixir's primary key-value data structure. They are highly flexible and efficient for looking up values based on their keys. Keys can be of any type, but atoms are commonly used.
Maps in Elixir are implemented using hash tables. They store key-value pairs. You can create a map using %{key1: value1, key2: value2} or %{key1 => value1, key2 => value2}. Accessing a value is done using map[key]. Maps are immutable, so operations like adding or updating a key-value pair return a new map. They are optimized for fast lookups, insertions, and deletions, typically with an average time complexity of O(1). The visual below illustrates the concept of a hash table, where keys are mapped to values through a hashing function, allowing for efficient retrieval.
Text-based content
Library pages focus on text content
Maps are created using the
%{}
%{name: "Alice", age: 30}
=>
%{1 => "one", "two" => 2}
map[key]
nil
You access a value using square brackets, e.g., my_map[key]. If the key is not found, nil is returned.
Structs: Structured Maps with Default Values
Structs are a special type of map that provide a way to define a fixed structure with default values. They are defined using the
@derive
Structs are maps with a defined schema and default values.
Structs are defined using defstruct [:field1, :field2] within a module. They behave like maps but enforce a structure. When you create a struct, you can provide values for its fields, and any fields not provided will take their default values (often nil if not specified). For example, %{__struct__: MyStruct, field1: "value"}.
Structs in Elixir are built on top of maps, providing a way to create data structures with a defined schema and default values. They are declared within a module using defstruct. A struct is essentially a map with a special __struct__ key that identifies its type. When creating a struct, you can initialize its fields. Any fields not explicitly provided will be set to their default value, which is nil if not otherwise specified in the defstruct definition. This makes structs excellent for representing domain-specific data, like user profiles or configuration settings, ensuring consistency and providing a clear contract for data shape.
__struct__ key in an Elixir struct?The __struct__ key identifies the type of the struct, allowing Elixir to treat it as a specific data structure rather than just a generic map.
Choosing the Right Data Structure
The choice of data structure depends on the specific use case. Lists are great for sequential processing and when prepending is common. Tuples are ideal for returning multiple fixed values or when fast indexed access is needed. Maps are perfect for key-value lookups, and structs provide a structured way to organize data with default values.
| Data Structure | Mutability | Access Efficiency | Common Use Cases |
|---|---|---|---|
| List | Immutable | Prepending: O(1), Indexed Access: O(n) | Sequential processing, building sequences |
| Tuple | Immutable | Any Element Access: O(1) | Returning multiple fixed values, fixed data records |
| Map | Immutable | Key Lookup: Average O(1) | Key-value storage, configuration, dynamic data |
| Struct | Immutable | Key Lookup: Average O(1) | Structured data, domain modeling, default values |
Learning Resources
The official Elixir documentation provides a clear overview of lists, their properties, and common operations.
Learn about Elixir tuples, their fixed-size nature, and how to access elements efficiently from the official guide.
Explore Elixir maps, their key-value structure, and their immutability from the official Elixir documentation.
Understand Elixir structs, how they define structured data with default values, and their relationship to maps.
A beginner-friendly tutorial covering Elixir lists, including creation, manipulation, and common functions.
This tutorial explains Elixir maps and structs, highlighting their differences and use cases.
A video tutorial that visually explains Elixir's fundamental data structures like lists, tuples, and maps.
A blog post that delves into the internal workings and practical implications of Elixir's core data structures.
An excerpt from the 'Elixir in Action' book, detailing Elixir's data structures and their functional programming context.
A concise video explaining the core concepts of Elixir lists, tuples, maps, and structs with practical examples.