dijkstra.hs

import Data.List
import Control.Monad.State

type Weight = Int
type Vertex = Char

newtype WEdge = WEdge (Vertex, Vertex, Weight)

head' :: WEdge -> Vertex
head' (WEdge (x, _, _)) = x

tail' :: WEdge -> Vertex
tail' (WEdge (_, y, _)) = y

newtype WPath = WPath ([Vertex], Vertex, Weight)

path :: WPath -> [Vertex]
path (WPath (vs, _, _)) = vs

target :: WPath -> Vertex
target (WPath (_, t, _)) = t

class HasWeight a where
  weight :: a -> Weight

instance HasWeight WEdge where
  weight (WEdge (_, _, w)) = w

instance HasWeight WPath where
  weight (WPath (_, _, w)) = w

type Graph = ([Vertex], [WEdge])

-- | Find shortest path using dijkstra's method.
-- | Result is shortest path including start and terminal.
dijkstra :: Vertex -> Vertex -> Graph -> [Vertex]
dijkstra s t graph = reverse $ evalState go (fst graph, [WPath ([], s, 0)])
  where
    go :: State ([Vertex], [WPath]) [Vertex]
    go = do
      vs <- gets fst
      (wp : rest) <- gets (sortOn weight . snd)
      if target wp == t
         then pure (target wp : path wp)
         else do
           let wes = filter (\we -> head' we == target wp) (snd graph)
               nextWPath we = WPath (head' we : path wp, tail' we, weight wp + weight we)
           put (vs \\ [target wp], map nextWPath wes ++ rest)
           go

main :: IO ()
main = do
  let vertices = ['a', 'b', 'c']
      wedges = [WEdge ('a', 'b', 1), WEdge ('a', 'c', 1), WEdge ('b', 'c', 1)]
      graph = (vertices, wedges)
  print $ dijkstra 'a' 'c' graph