How can you represent weighted graphs in functional programming?

In functional programming, weighted graphs can be represented as a list of tuples or records, each containing two nodes and a weight.

In more detail, a graph is a set of vertices (or nodes) and edges that connect these vertices. A weighted graph is a graph where each edge has an associated numerical value, known as a weight. In functional programming, we can represent this structure using a list of tuples or records. Each tuple or record would contain two nodes, representing the start and end of an edge, and a weight, representing the weight of that edge.

For example, in Haskell, a functional programming language, a weighted graph could be represented as follows:

`type WeightedGraph a = [(a, a, Int)]`

This defines a type alias `WeightedGraph` for a list of tuples. Each tuple contains two nodes of type `a` and an integer weight. A specific graph could then be defined as follows:

`graph :: WeightedGraph Char
graph = [('A', 'B', 5), ('B', 'C', 3), ('C', 'A', 2)]`

This graph contains three edges: 'A' to 'B' with a weight of 5, 'B' to 'C' with a weight of 3, and 'C' to 'A' with a weight of 2.

In functional programming, we often use recursion to traverse such structures. For example, we could define a function to calculate the total weight of a graph as follows:

`totalWeight :: WeightedGraph a -> Int
totalWeight [] = 0
totalWeight ((_, _, w):ws) = w + totalWeight ws`

This function uses pattern matching to destructure the list of edges. It adds the weight of the first edge to the total weight of the rest of the graph, calculated recursively. The base case for the recursion is an empty graph, which has a total weight of 0.

In conclusion, functional programming provides a powerful and flexible way to represent and manipulate complex data structures such as weighted graphs.