What’s the difference between a set, a map and a list in Haskell?

In Haskell, sets, maps, and lists are three different types of data structures, each with its own characteristics and use cases. Here’s a breakdown of their differences and when to use each:

1. List (Data.List)

You’re dealing with potentially infinite data streams or recursive structures.

Definition: A list is a linear sequence of elements in Haskell, represented with square brackets (e.g., [1, 2, 3]).

Properties

• Ordered: Lists preserve the order of elements.
• Allow Duplicates: Lists can contain duplicate elements.
• Homogeneous: All elements in a list must be of the same type.
• Lazy Evaluation: Lists are lazily evaluated, so they’re suitable for infinite sequences.

Performance

• Access by Index: O(n) for accessing elements by index, as lists are not optimized for random access.
• Appending/Prepending: O(1) for prepending to the beginning, but O(n) for appending at the end.
• Searching: O(n) for checking membership or finding an element.

Use Case

Use lists when:

• You need to maintain order.
• You don’t mind duplicates.

myList = [1, 2, 3, 4, 4, 5]

2. Set (Data.Set)

Definition: A set is a collection of unique elements in Haskell, provided by the Data.Set module.

Properties

• Unordered: Sets do not maintain any specific order of elements.
• No Duplicates: Sets automatically remove duplicates, so each element is unique.
• Homogeneous: All elements in a set must be of the same type.

Performance

• Membership Testing: O(log n) due to the internal balanced tree structure.
• Insert/Delete: O(log n), as sets are optimized for efficient insertion and deletion.
• Union/Intersection/Difference: O(n log n), making sets efficient for set operations.

Use Case

• You need unique elements only.
• Order is not a concern.
• You frequently need to check for membership or perform set operations like union and intersection.

import qualified Data.Set as Set

mySet = Set.fromList [1, 2, 3, 4, 4, 5]  -- Results in Set.fromList [1, 2, 3, 4, 5]

3. Map (Data.Map)

Definition: A map is a collection of key-value pairs in Haskell, provided by the Data.Map module.

Properties

• Key-Value Pairs: Each entry in a map has a unique key associated with a value.
• Unique Keys: Keys must be unique, and duplicate keys are not allowed.
• Homogeneous Values: While keys and values can be different types, all keys must be of the same type, and all values must be of the same type.
• Ordered by Keys: The map maintains order based on the keys’ ordering.

Performance

• Lookup: O(log n) for looking up values by key.
• Insert/Delete: O(log n) for inserting or deleting a key-value pair.
• Union/Intersection: Efficient, similar to sets, with complexity generally around O(n log n).

Use Case

Use maps when:

• You need to associate each key with a value.
• You want efficient lookups by key.
• Keys need to be unique and values do not.

import qualified Data.Map as Map

myMap = Map.fromList [("apple", 1), ("banana", 2), ("cherry", 3)]

Summary Table

Feature	List	Set	Map
Structure	Sequence	Unique elements	Key-value pairs
Duplicates Allowed	Yes	No	No for keys
Ordered	Yes	No	Ordered by keys
Access Time	O(n)	O(log n)	O(log n)
Membership Testing	O(n)	O(log n)	O(log n) for keys
Common Use Case	Ordered data, infinite sequences	Unique elements, set operations	Key-value associations

Choosing Between Them

• Use lists for simple, ordered sequences where duplicates are fine, or when working with infinite data.
• Use sets when you need uniqueness, and order isn’t a priority.
• Use maps for efficient lookups of values based on unique keys.

💡 Helpful References

Haskell.org - Data.List
https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-List.html

Haskell.org - Data.Set
https://hackage.haskell.org/package/containers-0.7/docs/Data-Set.html

Haskell.org - Data.Map
https://hackage.haskell.org/package/containers-0.4.0.0/docs/Data-Map.html