Implementing Prim's algorithm in Haskell

I facing difficulties implementing prim's algorithm, my logic is quite wrong, this is what I got so far:

import Data.Array
import Data.Function (on)
import Data.List (sortBy, delete)

type Vertex = Int
type Weight = Int
type Graph  = Array Vertex [(Vertex, Weight)]
type Bounds = (Vertex, Vertex)
type Edge   = (Vertex, Vertex, Weight)

g1 = mkGraph (1, 4) [(1, 2, 1), (1, 3, 10), (1, 4, 3), (2, 3, 4), (2, 4, 10), (3, 4, 1)] -- 5
g2 = mkGraph (1, 5) [(1, 2, 15), (1, 3, 10), (2, 3, 1), (3, 4, 3), (2, 4, 5), (4, 5, 20)] -- 34

mkGraph :: Bounds -> [Edge] -> Graph
mkGraph bounds edges = accumArray (\xs x -> x:xs) [] bounds [ (x, (y, w)) | (x, y, w) <- edges]

--[(1,[(4,3),(3,10),(2,1)]),(2,[(4,10),(3,4)]),(3,[(4,1)]),(4,[])]
prim :: Graph -> Vertex -> [(Vertex, Weight)]
prim graph start = prim' (sortBy (compare `on` snd) (graph ! start)) [start] []
    where
        prim' [] _ mst = mst
        prim' (x:xs) visited mst
            | elem (fst x) visited = prim' xs visited mst
            | otherwise            = prim' (delete x $ sortBy (compare `on` snd) ((graph ! (fst x)) ++ xs)) ((fst x):visited) (x:mst)

My idea was, if I put every edge that is possible to reach from the vertice start (let's say that is 1) pick the minimum (in this case is the first element from that list, because it's sorted), pick it's first element from the tuple and use that as an index and also make all edges reachable from that vertice while adding the vertices reachable from the previous vertice too.

While doing this keeping track of the vertices visited, the problem is that if it reach the final vertice (it will be empty) then it will stop adding the edges and will use just the edges that was added already.

But this will not work either, because the way that I'm keeping tracking the visited vertices will skip something like [(1, 3, 10) (2, 3, 1)], because it will mark the vertice 3 as visited.

I think the issue is that your Graph representation as an array is implicitly "directed", so you need to take your input undirected graph and tabulate edges in both directions:

mkGraph :: Bounds -> [Edge] -> Graph
mkGraph bounds edges = accumArray (\xs x -> x:xs) [] bounds 
    [(x, (y, w)) | (x', y', w) <- edges, (x, y) <- [(x', y'), (y', x')]]

Now, the invariant for the recursion is that in:

prim' outgoing visited mst

the argument outgoing is the list of (vertex, weight) pairs of all directed, outgoing arrows from anywhere in the visited set to some other vertex (possibly including some arrows pointing to vertexes already in the visited set).

At each recursive step, you skip any such outgoing arrows to vertexes you've already visited, and when you find an unvisited vertex with minimum weight, you add that edge to your mst, add the unvisited vertex to those visited, and augment the set of outgoing arrows with any arrows outgoing from the newly visited vertex.

(In your code, you delete x, though there's no technical need to do this, as it'll be filtered out as part of the "already visited" check.)

With the above change to mkGraph, your prim seems to work correctly on g1, g2, and the graph:

g3 = mkGraph (1,3) [(1,3,10), (2,3,1)]