型レベルで値の個数の範囲を指定できるリストを使ってFinger Treeを実装する - GHCの型チェックプラグインを活用する - Qiita

はじめにの前に これは2020年のアドベントカレンダーの18日目の記事です。「値の個数の範囲を型レベルで指定できるリスト」を作って、使ってみましたという話なのですが、なにやらつめこみすぎた感じがあります。作るだけじゃつまらないし、使うだけでもつまらないというところで、まず内容が多くなり、まともに使うためには「型チェックプラグイン」が必要という話で内容が倍増し、さらに「型チェックプラグイン」を実装するうえで「試しながら実装する」ためにパーサが必要だよねという話で、Packrat Parserの説明も追加したという、お祭りさわぎになってしまいました。最終的には みたいな関数を作ります。「要素が3個から12個のリストを『要素が2個から3個のリスト』を1個から4個含むリスト」に分割する関数です。「ふつうのリストだと要素の個数の範囲を型でしぼれなくて気持ち悪い」という特殊なタイプの需要に対応していま

[igrep]

"Packrat Parserでは、それぞれの文法要素について、それぞれの「解析の対象における位置」での解析の結果として「取得できる値」と「つぎに解析する位置」のペアを保存しておくことで、O(n)時間での解析"