So I set about doing it, and at first I figured there should be a way to do it all with a single elegant list comprehension...but I couldn't quite make that work, so I just went for a straight-forward recursive definition that I think should work, except that it's dependent on a function that determines whether or not adding an edge to the MST will form a circuit, which is in turn dependent on a function that determines the parent of a node in a tree graph, that I can't quite seem to make work right. In class we were told to use disjoint sets to keep track of the parents of all the nodes as we went along, which works great, but I can't seem to reconcile it with the functional paradigm, since it's a strictly imperative technique that uses arrays.

Rambling aside, I was wondering if anyone has any suggestion as to how I could most efficiently implement the parent and loop functions, or just replace them altogether with some more clever technique. Do I just need to break down and make the whole thing iterative? Do most algorithms just not adapt well? Here's the mess of code I've thrown together so far, if anyone feels like figuring out how I could fix it (I realize at the moment that my parent implementation isn't working because the graph is undirected, but I haven't quite figured out how to make it work)

Code: Select all

`--A QuickSort implementation to sort the edges used initially`

qs :: Ord b => (a -> b) -> [a] -> [a]

qs _ [] = []

qs eval (pivot: rest) = qs eval left ++ (pivot : qs eval right)

where

left = [x | x <- rest, (eval x) < (eval pivot)]

right = [x | x <- rest, (eval x) >= (eval pivot)]

--A graph is a list of three-tuples, formatted as:

--(begin, end, weight) :: (Char, Char, Int)

--Here's a simple graph to test the algorithm with

testGraph :: [(Char, Char, Int)]

testGraph = [('a', 'b', 8), ('a', 'c', 1), ('a', 'd', 6),

('b', 'c', 4), ('b', 'd', 2),

('c', 'd', 3), ('c', 'e', 1),

('d', 'e', 9)]

--Kruskal's MST algorithm

--The base function calls the recursive function with the graph's edges sorted

--in descending order by edge weight, so the first recursive calls that actually

--get considered are those with the lowest edge weights

mst :: [(Char, Char, Int)] -> [(Char, Char, Int)]

mst x = mstRec (qs (\(x, y, z) -> -z) x)

mstRec :: [(Char, Char, Int)] -> [(Char, Char, Int)]

--MST for an empty graph is an empty graph

mstRec [] = []

--The head of the list will always be the worst-case weighted edge. If adding

--the worst possible edge wouldn't produce a loop in the graph when added to the

--MST one iteration before, then we add it to the end of the MST one iteration

--before this one

mstRec (worst: rest)

| not(loops worst (mstRec rest)) = mstRec rest ++ [worst]

| otherwise = mstRec rest

--Determines whether adding an edge to a graph will produce a loop

loops :: (Char, Char, Int) -> [(Char, Char, Int)] -> Bool

loops _ [] = False

--Determines the ultimate parent of a graph node on an MST

parent :: Char -> [(Char, Char, Int)] -> Char

parent node graph

| length findParent == 0 = node

| otherwise = parent (findParent !! 0) graph

where

bySource=[y | (x, y, z) <- graph, x==node]

byDest=[x | (x, y, z) <- graph, y==node]

findParent

| not(length bySource == 0) = bySource

| not(length byDest == 0) = byDest

| otherwise = []