はじめに Recursion schemes(再帰スキーム)とは，再帰的なデータ構造に対する汎用コンビネータの総称のことである．ところで， recursion schemes から導出される再帰構造を捉えた Functor (代数) による再帰データの表現は，コンパイラやインタプリタでASTを扱う際便利な場合が多い．しかし，この表現は相互再帰に弱いという欠点がある．ここでは，高階代数で同様のことを考えることにより，この欠点を克服する手法を紹介する． なお，以下のものを想定している． GHCのバージョン: 8.6.3 前提とするGHC拡張 BlockArguments DataKinds DeriveFunctor FlexibleInstances FlexibleContexts FunctionalDependencies GADTs LambdaCase MultiParamType

本記事は Haskell (その2) Advent Calendar 2018 16日目の記事です。 本記事では、Haskell Symposium 2017 で発表された Algebraic graphs with class (functional pearl)1 という論文および、その実装である algebraic-graphs パッケージを紹介していきます。 提案されている Algebraic graphs （本記事では代数グラフと呼ぶことにします）は、これまでのグラフ表現に代わり、グラフの接続関係を加法や乗法（に似た表現）で表すことで、不正な形式のグラフの構築を型レベルで抑止し、グラフに対する様々な操作をエレガントに表現しています。 これまでのグラフ表現 ここで言うグラフとは、棒グラフや曲線グラフのようなものでなく2、有向グラフのような点とか矢印からなるものを指します。 グラフ理