TheAlgorithms
Implemented Disjoint Set, Stack and Queue Data Structures
This PR to introduces:
- Disjoint Set (Union-Find) data structure using mutable arrays within the Haskell the ST monad:
It includes support for both union by rank and path compression optimisations.
Implementation Details:
makeSet :: Int -> ST s (DisjointSet s): Initializes a new disjoint set with each node as its own parent and rank zero.findSet :: DisjointSet s -> Node -> ST s Node: Finds the root of the set containing the given node with path compression.unionSet :: DisjointSet s -> Node -> Node -> ST s (): Unites the sets containing the two nodes using union by rank.example :: Int -> [(Node, Node)] -> [Node] -> [Node]: Example function demonstrating how to use the disjoint set.test :: IO (): Basic test function to validate the implementation with sample data.
Testing:
The implementation has been tested with the following unions and find operations:
- Unions:
[(0, 1), (1, 2), (3, 4), (4, 5), (6, 7), (8, 9), (0, 5), (6, 9)] - Finds:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] - Expected Output:
[0, 0, 0, 6, 6, 6, 6, 6, 6, 6]
- Stack Data Structure using mutable arrays within the Haskell ST monad:
The stack supports standard stack operations such as push, pop, and checking for emptiness.
Implementation Details:
newStack :: Int -> ST s (Stack s a): Initializes a new stack with a given capacity.push :: Stack s a -> a -> ST s (): Pushes an element onto the stack.pop :: Stack s a -> ST s (Maybe a): Pops an element from the stack. Returns Nothing if the stack is empty.isEmpty :: Stack s a -> ST s Bool: Checks if the stack is empty.
Testing:
A testing function that pushes a list of elements onto the stack, then pops them off, and checks if the stack was empty before and after operations.
-
testStack :: [a] -> ([Maybe a], Bool, Bool) -
main :: IO () -
Input:
let input = [1, 2, 3, 4, 5] -
Expected Output
[Just 5, Just 4, Just 3, Just 2, Just 1]FalseTrue
- Queue Data Structure using mutable arrays within the Haskell ST monad:
The queue supports typical queue operations such as enqueue, dequeue, and checking for emptiness.
Implementation Details:
newQueue :: Int -> ST s (Queue s a): Initializes a new queue with a given capacity.enqueue :: Queue s a -> a -> ST s (): Adds an element to the end of the queue.dequeue :: Queue s a -> ST s (Maybe a): Removes an element from the front of the queue. Returns Nothing if the queue is empty.isEmptyQueue :: Queue s a -> ST s Bool: Checks if the queue is empty.
Testing:
A testing function that enqueues a list of elements, then dequeues them, and checks if the queue was empty before and after operations.
testQueue :: [a] -> ([Maybe a], Bool, Bool)main :: IO (): tests the queue implementation- Input:
let input = [1, 2, 3, 4, 5] - Expected Output
[Just 1, Just 2, Just 3, Just 4, Just 5]FalseTrue
Reference
Data Structures and Algorithms in C++, 2nd Edition
