Functional Graphs

A study of directed graphs through the lens of functional programming in Haskell, exploring the same problem from two entirely different angles: sets and edges on one hand, algebraic construction on the other, and then unifying them under a shared, typeclass-based interface.

The Story

A graph can be described in more than one way, and the way you choose to describe it shapes everything you can conveniently do with it. The obvious approach lists what a graph is made of: a set of nodes, a set of edges connecting them. It is direct, familiar, and mirrors the textbook definition almost exactly.

But there is another way to think about graphs, closer to how a functional programmer thinks about numbers: start from a few primitive building blocks and a couple of ways to combine them, and let every graph emerge as an expression built out of those pieces. An empty graph, a single node, the overlay of two graphs, the connection of two graphs: from just these four constructors, any directed graph without inconsistencies can be built, and dense graphs that would need quadratic space to enumerate their edges collapse into something closer to linear space. It even turns arithmetic into a language for graphs, where addition means overlay, multiplication means connection, and a single expression like ((1*2) * (3+4)) * 5 fully describes a nontrivial structure.

This project builds both representations from the ground up, implements the same vocabulary of operations on each, and then asks the natural next question: given that these two representations answer to the same interface, why not describe that interface once, abstractly, using Haskell's typeclasses, and let both structures, and anything built to the same shape in the future, share it. Along the way, the project also chases a smaller, more mathematical thread: modular decomposition, the search for the most compact algebraic description of a graph, based on identifying clusters of nodes that relate to the rest of the graph identically. Finally, it steps back and asks not "does this implementation work" but "why must it look this way", deriving certain functions not by guessing, but by a disciplined chain of equational reasoning starting from a known-correct definition.

The project unfolds across four stages, each one adding a language mechanism and a new way of looking at the same underlying problem: sets and comprehensions, algebraic data types, typeclass polymorphism, and finally equational reasoning as a design tool in its own right.

Features

Etapa 1: The Standard Representation

• Represents a directed graph as a pair of sets (nodes and edges) built on top of Data.Set for uniqueness and structural equality independent of ordering.
• fromComponents constructs a graph from a set of nodes and a set of edges; nodes and edges expose them back.
• outNeighbors and inNeighbors compute the sets of nodes reachable by outgoing and incoming edges from a given node.
• removeNode deletes a node and every edge touching it; splitNode expands a single node into several while preserving its edge structure; mergeNodes collapses several nodes into one, combining their edges.
• A companion Algorithms module implements breadth-first and depth-first search (bfs, dfs) along with countIntermediate, which checks reachability between two nodes and measures how many intermediate nodes each search strategy expands along the way.
• Every function in this stage is written without explicit recursion, operating directly on sets through their own combinators rather than converting to and from lists.

Etapa 2: The Algebraic Representation

• Introduces AlgebraicGraph a, a proper algebraic data type built from four constructors: Empty, Node, Overlay, and Connect, the empty graph, a single labeled node, the union of two graphs, and the union of two graphs fully cross-connected.
• Reimplements the Stage 1 interface (nodes, edges, outNeighbors, inNeighbors, removeNode, splitNode, mergeNodes) to operate natively on this new representation, using explicit structural recursion rather than any conversion back to the set-based form.
• Lays the groundwork for modular decomposition: identifying sets of nodes, modules, that share identical external in- and out-neighbor sets, which can then be factored out as a single Connect or Overlay subexpression, compacting the graph's description. Includes brute-force scaffolding for this: mapSingle for targeted single-element transformation, and partitions for enumerating every partition of a node set.

Etapa 3: Typeclasses and Structural Generalization

• Equips AlgebraicGraph with standard typeclass instances: Num, so that ordinary arithmetic expressions can be interpreted directly as graphs; Show, to render a graph through that same arithmetic lens; and Eq, to correctly compare two graphs that may have different symbolic descriptions but represent the same structure.
• Introduces extend, a general substitution mechanism that replaces every node in a graph with an arbitrary subgraph according to a mapping function: the foundation every higher-level operation in this stage is built on.
• Provides a Functor instance (fmap) generalizing map from lists to graphs, letting a function be applied uniformly across all node labels, and reimplements mergeNodes on top of it.
• Introduces filterGraph, generalizing filter from lists to graphs, and reimplements removeNode on top of it. Reimplements splitNode on top of extend as well.
• Continues the modular decomposition work with isModule, isModularPartition, and maximalModularPartition, culminating in modularlyDecompose, which assembles the full compaction pipeline.

Etapa 4: Equational Reasoning

• Adds a Foldable instance for AlgebraicGraph, and derives nodesWithFoldr, an alternative formulation of nodes expressed through foldr.
• Derives nodesEdges, a single compositional traversal that computes nodes and edges together via tupling: more efficient than computing edges independently, obtained by following a chain of equational reasoning rather than being written from scratch.
• Introduces AlgebraicGraphFolder and foldAlgebraicGraph, a dedicated reduction mechanism tailored to the shape of AlgebraicGraph, more expressive than the generic Foldable instance, together with combinators (<+>) and (>.>) for composing independent and semi-dependent folders.
• Reimplements nodes and introduces isNode on top of this new folding mechanism, and reassembles edges by combining the nodes folder with a second, semi-dependent one, gaining efficiency, modularity, and reuse simultaneously.
• Derives dfsStack, a stack-based depth-first search that visits each node at most once, starting from the Stage 1 definition of dfs and reasoning through to the more efficient form.
• Every derivation obtained this way is documented step by step in a DERIVARE: comment block alongside the code, recording the equational reasoning rather than just its result.

Design Notes

• Two representations, one vocabulary. Stages 1 and 2 implement the same conceptual operations, node removal, splitting, merging, neighbor queries, on fundamentally different underlying structures, making it possible to compare their trade-offs directly: explicit edge sets are simple and general but can be quadratic in space; the algebraic form is often linear but requires structural recursion to query.
• Correctness by construction. The algebraic representation makes it structurally impossible to build an inconsistent graph. There is no way to reference an edge to a node that doesn't exist, a guarantee the set-based representation cannot offer without extra validation.
• Typeclasses as the seam between representations. Stage 3's Num, Show, Eq, and Functor instances are not decoration; they are what allows the algebraic graph to be built, printed, compared, and mapped over using Haskell's ordinary vocabulary rather than a bespoke one.
• Derivation over invention. Stage 4 deliberately avoids writing optimized implementations from intuition. Each one is calculated from a known-correct starting point through equational reasoning, with the reasoning preserved as part of the deliverable.
• Modular decomposition as a running thread. Rather than being confined to a single stage, the compaction problem is introduced conceptually in Stage 2, built out mechanically in Stage 3, and left as a coherent, self-contained pipeline by the time modularlyDecompose is complete.

Repository Structure

.
├── etapa1/
│   ├── StandardGraph.hs   Set-based graph representation and operations
│   └── Algorithms.hs      BFS, DFS, and reachability analysis
├── etapa2/
│   ├── AlgebraicGraph.hs  Algebraic graph representation and operations
│   └── Modular.hs         Partition generation and module-checking scaffolding
├── etapa3/
│   ├── AlgebraicGraph.hs  Typeclass instances, extend, fmap, filterGraph
│   └── Modular.hs         Full modular decomposition pipeline
├── etapa4/
│   ├── AlgebraicGraph.hs  Foldable instance, folder combinators, derivations
│   ├── StandardGraph.hs   Carried over from Stage 1
│   └── Algorithms.hs      Stack-based DFS, derived by equational reasoning
└── README.md

Running the Project

Each stage includes a TestGraph module used to validate the implementation. Load it into GHCi and run the full test suite:

ghci TestGraph.hs
ghci> checkAll

The project depends on containers (for Data.Set) at version 0.6.7.

Background

This project was built as coursework for a functional programming course, following an assignment titled Functional Graphs, structured around Haskell. Each stage was built to line up with the corresponding week's lecture and lab material: sets, functionals, and list comprehensions; algebraic data types; ad-hoc polymorphism and typeclasses; and finally equational reasoning as a technique for deriving efficient code from a specification rather than guessing at it: so the two graph representations and the reasoning connecting them serve as a working record of those ideas.