Haskellで蟻本やるぜ

前回の続き。
しかし、一旦2-5のグラフの最小全域木問題（プリム法）まで飛ぶ。
冷静に考えると早いプログラムを作るには、配列は必須！
前回、「HaskellでArrayとかLoopとか使いだすと負けな気がする」と書いた矢先に前言撤回！
だって、プリム法ArrayもLoopも使うんだもん。
Haskellで蟻本（初級編） - グラフをパクる。

-- プリム法
prim :: Int -> Int -> Int -> [(Int, Int, Int)] -> Int
prim n m start es = runST $ do
    used <- newArray (0, n - 1) False :: ST s (STArray s Int Bool)
    writeArray used start True
    let ss = fmap (\(t, c) -> (c, t)) (g ! start)
    go 0 used (foldr push Empty ss)
  where
    g = buildGList (0, n - 1) [(a, (b, c)) | (a, b, c) <- es]
    go !k used que
        | Just ((c, t), q) <- pop que = do
            usedt <- readArray used t
            if usedt
                then go k used q
                else do
                    let ss = fmap (\(t, c) -> (c, t)) (g ! t)
                    let q' = foldr push q ss
                    writeArray used t True
                    go (k + c) used q'
        | otherwise = return k

方向性としては、以下の３つがあるがどうしよう。

• 速度を犠牲にするが、ArrayもLoopも使わないアルゴリズムを考える。
  （それはそれで、修行になり良い気がする。）
• HaskellのArrayもLoopの修行をする。
  （Haskellerになるためには正しい道な気がする。）
• Haskellやめる。
  （いつもこれ。現実解。妥協の産物。人生は短い。お前はHaskellがやりたいのか？競プロがやりたいのか？）

やはりちゃんとHaskellやるか。。
手続き脳によるHaskell -- クイックソート(quick sort)
Darkside of the Haskell -- 副作用版 クイックソート

ちなみに、プリム法は、以下の動画がわかりやすい。

そして、ダイクストラのアルゴリズムは、以下の動画がわかりやすい。