ASTのための高階代数を元にした recursion schemes - Qiita

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

[lotz84]

冒頭のrecursion schemeの説明も分かりやすい。DSLの例から相互再帰・recursion schemes for higher algebra導入までの考え方も自然で、色々応用できそうな気がする。続編のパーサとインタプリタも楽しみ！