はじめに Haskellでは、ListやTreeがよく取り上げられる一方で、グラフの話題はあまり出てこないことがあります。これは、ListやTreeには適切な始代数があり、それに応じたコンストラクタ(パターンマッチング)がうまく機能するためです。しかし、グラフ構造でも実はmatch関数を使ったパターンマッチングで、驚くほど簡潔に各種のアルゴリズムを実装できます。 グラフの基本構造 まず、グラフの基本構造を以下に示します。 import Data.List import Data.IntMap.Strict (IntMap) import qualified Data.IntMap.Strict as IM type Gr a b = IntMap (a, IntMap b) type Node = Int type LNode a = (Node, a) type Edge = (Node
![Haskellでグラフアルゴリズムを攻略する(WIP)](https://cdn-ak-scissors.b.st-hatena.com/image/square/987815db7addee7bc0d973b7509a37bb1a518324/height=288;version=1;width=512/https%3A%2F%2Fres.cloudinary.com%2Fzenn%2Fimage%2Fupload%2Fs--V3V6tNDw--%2Fc_fit%252Cg_north_west%252Cl_text%3Anotosansjp-medium.otf_55%3AHaskell%2525E3%252581%2525A7%2525E3%252582%2525B0%2525E3%252583%2525A9%2525E3%252583%252595%2525E3%252582%2525A2%2525E3%252583%2525AB%2525E3%252582%2525B4%2525E3%252583%2525AA%2525E3%252582%2525BA%2525E3%252583%2525A0%2525E3%252582%252592%2525E6%252594%2525BB%2525E7%252595%2525A5%2525E3%252581%252599%2525E3%252582%25258B%252528WIP%252529%252Cw_1010%252Cx_90%252Cy_100%2Fg_south_west%252Cl_text%3Anotosansjp-medium.otf_37%3A0xYusuke%252Cx_203%252Cy_98%2Fg_south_west%252Ch_90%252Cl_fetch%3AaHR0cHM6Ly9zdG9yYWdlLmdvb2dsZWFwaXMuY29tL3plbm4tdXNlci11cGxvYWQvYXZhdGFyLzNhNTYyODI1MWYuanBlZw%3D%3D%252Cr_max%252Cw_90%252Cx_87%252Cy_72%2Fog-base.png)