Question: I can write both Prim's and Kruskal's algorithms to find a minimum spanning tree in C++ or Java, but I want to know how to implement them in Haskell with O(mlogm) or O(mlogn) (pure functional programs is better). Thanks a lot.

Answer: 
Here is a crude Kruskal implementation. 

```
import Data.List(sort)
import Data.Set (Set, member, fromList, insert, union)

data Edge a = Edge a a Double deriving Show

instance (Eq a) => Eq (Edge a) where
  Edge x1 y1 z1 == Edge x2 y2 z2 = x1 == x2 && y1 == y2 && z1 == z2

instance Eq a => Ord (Edge a) where
  (Edge _ _ x) `compare` (Edge _ _ y) = x `compare` y

kruskal :: Ord a => [Edge a] -> [Edge a]
kruskal = fst . foldl mst ([],[]) . sort

mst :: Ord a => ([Edge a],[Set a]) -> Edge a -> ([Edge a],[Set a])
mst (es, sets) e@(Edge p q _) = step $ extract sets where
   step (rest, Nothing, Nothing) = (e : es, fromList [p,q] : rest)
   step (rest, Just ps, Nothing) = (e : es, q `insert` ps : rest)
   step (rest, Nothing, Just qs) = (e : es, p `insert` qs : rest)
   step (rest, Just ps, Just qs) | ps == qs = (es, sets) --circle
                                 | otherwise = (e : es, ps `union` qs : rest)
   extract = foldr f ([], Nothing, Nothing) where
       f s (list, setp, setq) =
            let list' = if member p s || member q s then list else s:list
                setp' = if member p s then Just s else setp
                setq' = if member q s then Just s else setq
            in (list', setp', setq') 

```

The first step is sorting the edges, which is O(n log n). The problem is to find a faster lookup for the vertex sets in the extract function. I couldn't find a faster solution for this, maybe someone has an idea...

[Update]

For a Scala implementation I used a map-like data-structure for (hopefully) better performance, but unfortunately it uses mutable sets, and I have no clue how to translate this into Haskell. The code is in my blog (sorry, description is in German): <http://dgronau.wordpress.com/2010/11/28/nochmal-kruskal/>
I think a priority search queue is what you're looking for. It can be implemented optimally in a functional language as demonstrated by Ralf Hinze in [a paper](http://www.comlab.ox.ac.uk/publications/publication1150-abstract.html). It seems like the paper is only available via acm's library at a cost.