2024-03-20: data-reifyを実装していた
やったこと
diary
そろそろsrc/posts
ディレクトリのファイル数が多くなりすぎて微妙な気がしているので、階層を入れられるようにしたい。
当初はこんなに続けると思わなかったしなぁ。
Miranda
そういえばPPLでakrさんに「Mirandaには昔unfree algebraがあった」という話を聞いたのでソースを探してみた。
自然数の定義をzero | succ(n) | pred(n)
としたときにsucc(pred(n))
のような値をn
に自動で変換する規則を導入できる型らしい。
データ構造に規則があるからfreeではなくunfree algebraらしい。
この辺が出典の気がする。
Turner, David A. "Miranda: A non-strict functional language with polymorphic types." Conference on Functional Programming Languages and Computer Architecture. Berlin, Heidelberg: Springer Berlin Heidelberg, 1985.
https://www.cs.kent.ac.uk/people/staff/dat/miranda/nancypaper.pdf
Unfree algebrasという章があって、そこに確かに次のような記述があった。
int ::= Zero | Suc int | Pred int
...
Suc (Pred n) => n
Pred (Suc n) => n
なるほど。
Scala
過去にHaskellのdata-reify
をScalaで実装した気がするのだけど、どうも公開していないっぽいのでもう一度考えている。
別に難しくはない。
とりあえず実装してみた。
https://gist.github.com/makenowjust/0db9575569956b079305762cfd6f16fb
MuRef
は Applicative + Traverse + Coalgebra
なはずなので、そういう気持ちで書いた。