Haskellで蟻本やるぜ

1 min read読了の目安(約1600字

前回の続き。
しかし、一旦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

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

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

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

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

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