Return to Question

Here is my implementation:

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                                                    

[Update]

In patticular I'm interested to show these concepts:

• Type Inference
• Lazyness, Immutability
• Currying
• Pattern matching, Guards
• ADTs and Type Polymorphism

[Update 2]

The improved code:

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

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

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

instance Ord t => Ord (Edge t) where
   compare (Edge v1 v2 len1) (Edge v3 v4 len2) =
      compare (len1, min v1 v2, max v1 v2) (len2, min v3 v4, max v3 v4)

prim [] = []
prim edges = 
   let initialVertex ((Edge vertex _ _) : _) = vertex
       initialSet = singleton (initialVertex edges)
   in step (sort edges) initialSet []  

step [] _ solution  = solution
step edges vertices solution  =
   let (edge, newVertex) = findNextEdge edges vertices
       newVertices = insert newVertex vertices
       validEdge (Edge v1 v2 _) = notMember v1 newVertices || notMember v2 newVertices
       newEdges = filter validEdge edges
   in step newEdges newVertices (edge : solution)

findNextEdge [] vertices = error ("Disjunct graph with island " ++ show vertices)
findNextEdge (edge @ (Edge vertex1 vertex2 _) : edges) vertices
    | member vertex1 vertices = (edge, vertex2)
    | member vertex2 vertices = (edge, vertex1)
    | otherwise = findNextEdge edges vertices

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

[Update 2]

The improved code:

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

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

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

instance Ord t => Ord (Edge t) where
   compare (Edge v1 v2 len1) (Edge v3 v4 len2) =
      compare (len1, min v1 v2, max v1 v2) (len2, min v3 v4, max v3 v4)

prim [] = []
prim edges = 
   let initialVertex ((Edge vertex _ _) : _) = vertex
       initialSet = singleton (initialVertex edges)
   in step (sort edges) initialSet []  

step [] _ solution  = solution
step edges vertices solution  =
   let (edge, newVertex) = findNextEdge edges vertices
       newVertices = insert newVertex vertices
       validEdge (Edge v1 v2 _) = notMember v1 newVertices || notMember v2 newVertices
       newEdges = filter validEdge edges
   in step newEdges newVertices (edge : solution)

findNextEdge [] vertices = error ("Disjunct graph with island " ++ show vertices)
findNextEdge (edge @ (Edge vertex1 vertex2 _) : edges) vertices
    | member vertex1 vertices = (edge, vertex2)
    | member vertex2 vertices = (edge, vertex1)
    | otherwise = findNextEdge edges vertices

[Update]

In patticular I'm interested to show these concepts:

• Type Inference
• Lazyness, Immutability
• Currying
• Pattern matching, Guards
• ADTs and Type Polymorphism