# Prim's algorithm for minimal spanning trees

I want to write an article giving a Haskell introduction specifically to Java developers, and would like to get feedback on my implementation. Please keep in mind that I don't want to be "too clever", as too advanced Haskell concepts would only confuse the readers. On the other hand I need to show some really interesting features (e.g. that's why I decided to use Edge a a Double and a type class instance instead of a simple (String, String, Double)), else the readers would ask "And where is the advantage over Java?". So I need a good balance between clarity and "interesting stuff", showing a nice example of Haskell's expressiveness.

module Prim (
prim,
Edge(..)
) where

import Data.List(sort, deleteBy)
import Data.Set(member, empty, insert, singleton, Set)

data Edge a = Edge a a Double deriving (Eq, Show)

instance Ord a => Ord (Edge a) where
compare (Edge a b c) (Edge d e f) =
(c, min a b, max a b) compare (f, min d e, max d e)

prim [] = []
prim edges = loop (sort edges) [] startSet where
startSet = singleton (startNode edges)
startNode ((Edge node _ _):_) = node

loop [] solution _ = solution
loop edges solution vertices =
let (e,x) = findNextEdge edges vertices
vertices' = x insert vertices
cyclicEdge (Edge a b _) = a member vertices' &&
b member vertices'
edges' = filter (not.cyclicEdge) edges
in loop edges' (e:solution) vertices'

findNextEdge [] vs = error ("Disjunct graph with island " ++ show vs)
findNextEdge (e@(Edge a b _):edges) vertices
| a member vertices = (e,b)
| b member vertices = (e,a)
| otherwise = findNextEdge edges vertices

In particular, I'm interested in these concepts:

• Type inference
• Laziness, immutability
• Currying
• Pattern matching, guards