2026-10-28
Relax.hs
data Dist = Infinity | Finite Int
deriving (Eq, Ord, Show)
extend :: Dist -> Int -> Dist
extend (Finite d) w = Finite (d + w)
extend Infinity _ = Infinity
relax :: [Dist] -> (Int, Int, Int) -> [Dist]
relax ds (u, v, w) =
[if i == v then min d (extend (ds !! u) w) else d | (i, d) <- zip [0 ..] ds]
main :: IO ()
main = print (foldl relax [Finite 0, Infinity, Infinity] [(0, 1, 4), (1, 2, -1), (0, 2, 5)])
頂点0からの最短距離を、まだ辿り着けない頂点を Infinity として持ち、辺 (u, v, w)(u から v へ重み w)を1本ずつ見て v の距離を縮めていくつもりのコードです。main は3つの頂点と3本の辺を渡します。本来は [Finite 0,Finite 4,Finite 3] と出力されるはずが、いまは [Finite 0,Infinity,Infinity] と出力され、頂点1と2に辿り着けないことになります。
Answer
Wrong
data Dist = Infinity | Finite Int
deriving (Eq, Ord, Show)
deriving で作った Ord は、構成子を宣言した順に小さいものとして比べます。Infinity を先に宣言しているので、Infinity はどの Finite よりも小さくなります。
最初の辺 (0, 1, 4) で、relax は頂点1のいまの距離 Infinity と、頂点0を通る候補 Finite 4 の min を取ります。小さいのは Infinity なので、頂点1は Infinity のまま残ります。続く辺でも同じことが起き、どの頂点も Infinity から変わりません。
Right
data Dist = Finite Int | Infinity
deriving (Eq, Ord, Show)
Finite を先に宣言すると、どの Finite も Infinity より小さくなります。Finite どうしは中の Int で比べられるので、min が最短距離の更新として働きます。頂点1は Finite 4 に、頂点2は辺 (1, 2, -1) で Finite 3 になり、辺 (0, 2, 5) の Finite 5 には負けません1。
- Haskell 2010 Language Report の derived instance の章が、
Ordの比較では構成子の宣言順で先のものが小さく、同じ構成子どうしはフィールドを左から順に比べると定めています。MaybeでNothingがJustより小さいのも同じ理由です。