Как я могу написать алгоритм MST (Prim или Kruskal) на Haskell?

Как предлагает Свеннингссон, очередь поиска с приоритетом хорошо подходит как для Крускала, так и для Прима (по крайней мере, автор заявляет об этом в своем paper.) Проблема с Kruskal заключается в том, что он требует наличия O (log n) алгоритм поиска объединения. Структура данных union-find с чисто функциональным интерфейсом описана здесь, но это использует изменяемое состояние внутри, и чисто функциональная реализация может быть невозможна, и на самом деле существует несколько проблем, для которых эффективное чисто функциональное решение не известно, как обсуждается в этот вопрос SO.

Альтернативой, не являющейся чистой, является реализация алгоритма поиска объединения в монаде ST. Поиск на Hackage обнаружил, что пакет эквивалентность соответствует нашим потребностям. Ниже представлена ​​реализация Kruskal с использованием Data.Equivalence.Monad из пакета Equivalence:

import Data.Equivalence.Monad
import Data.Graph as G
import Data.List(sortBy)
import Data.Map as M
import Control.Monad(filterM)
import Data.Ord(comparing)

run = runEquivM (const ()) (const $ const ())

kruskal weight graph = run $
 filterM go (sortBy (comparing weight) theEdges)
     where
      theEdges = G.edges graph
      go (u,v) = do 
        eq <- equivalent u v
        if eq then return False else
         equate u v >> return True

Его можно использовать так:

fromL xs = fromJust . flip M.lookup (M.fromList xs)

testWeights = fromL [((1,2),1),((2,3),4),((3,4),5),((1,4),30),((1,3),4)]
testGraph = G.buildG  (1,4) [(1,2),(2,3),(3,4),(1,4),(1,3)]
test = kruskal testWeights testGraph

и текущий тест дает:

[(1,2),(1,3),(3,4)]

Следует отметить, что время работы зависит от весов, работающих за время O (1), однако fromL создает весовую функцию, работающую за время O (log (n)), это можно улучшить до времени O (1) с помощью массивов или просто отслеживание веса во входном списке, но на самом деле это не часть алгоритма.

Вот грубая реализация Крускала.

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') 

Первым шагом является сортировка ребер, что составляет O (n log n). Проблема состоит в том, чтобы быстрее найти наборы вершин в функции извлечения. Я не смог найти более быстрого решения для этого, может у кого-то есть идея ...

[Обновлять]

Для реализации Scala я использовал структуру данных, подобную карте, для (надеюсь) лучшей производительности, но, к сожалению, она использует изменяемые наборы, и я понятия не имею, как перевести это в Haskell. Код есть в моем блоге (извините, описание на немецком языке): http://dgronau.wordpress.com/2010/11/28/nochmal-kruskal/

Я думаю, что очередь поиска с приоритетом - это то, что вы ищете. Его можно оптимально реализовать на функциональном языке, как продемонстрировал Ральф Хинце в статье. Похоже, что эту бумагу можно получить только в библиотеке acm за определенную плату.