# 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
• ADTs and type polymorphism

• Java developers prefer intention revealing names as opposed to mathematical single letter identifiers. So it might be better to use edge instead of e and so on.
• Most common type parameter name in Java is T as opposed to a, so maybe using at least 't' (if not a normal name like nodeType) to prevent confusion and better explain ADTs.
• loop might look like a syntax construct, especially because its definition follows afterwards.
• Just a detail, but initialSet instead of startSet would be clearer to me - same holds for startNode.
• I would replace where with let, because it would make one construct less (although idiomatic one) and it is a convention in mainstream languages to write declarations/definitions before use.
• I wouldn't use the apostrophe ('), although I understand it is common in math and theory of programming, but among backquoutes () for infix operators it might be confusing.
• I think it would help if the function composition operator (.) was surrounded with whitespace - it would better show that it is a different kind of '.' than the one in import Data.List(sort, deleteBy)`, which might be easier to understand for Java developers.