# Problem 84 Solution

``````prim : comparable -> Graph comparable -> Graph comparable
prim start ( nodes, edges ) =
snd <| findMst ( ( nodes, edges ), ( [ start ], [] ) )

{-| given a SpanningTree, add the lowest weight edge from the left graph
to the right graph until it includes all nodes
-}
findMst : SpanningTree comparable -> SpanningTree comparable
findMst ( ( lNodes, lEdges ), ( rNodes, rEdges ) ) =
let
edges =
List.filter (hasOneNodeIn rNodes) lEdges

edge =
minimumBy (\( a, b, w ) -> w) edges
in
case edge of
Nothing ->
( ( lNodes, lEdges ), ( rNodes, rEdges ) )

Just e ->
let
rEdges' =
rEdges ++ [ e ]

rNodes' =
nodesOfEdges rEdges'

lEdges' =
Set.toList <| Set.remove e <| Set.fromList lEdges
in
if List.length lNodes <= List.length rNodes then
( ( lNodes, lEdges ), ( rNodes', rEdges' ) )
else
findMst ( ( lNodes, lEdges' ), ( rNodes', rEdges' ) )

hasOneNodeIn : List comparable -> Edge comparable -> Bool
hasOneNodeIn nodes ( a, b, w ) =
(List.member a nodes && (not (List.member b nodes)))
|| ((not (List.member a nodes)) && List.member b nodes)

nodesOfEdges : List (Edge comparable) -> List comparable
nodesOfEdges edges =
List.sort
<| Set.toList
<| Set.fromList
<| List.concatMap (\( a, b, w ) -> [ a, b ]) edges

{-| Find the first minimum element in a list using a comparable transformation
(borrowed from List.Extra)
-}
minimumBy : (a -> comparable) -> List a -> Maybe a
minimumBy f ls =
let
minBy x ( y, fy ) =
let
fx =
f x
in
if fx < fy then
( x, fx )
else
( y, fy )
in
case ls of
[ l' ] ->
Just l'

l' :: ls' ->
Just <| fst <| List.foldl minBy ( l', f l' ) ls'

_ ->
Nothing

last : List a -> Maybe a
last list =