ocamlで二進表現の型定義どうするのってぐぐってもそれらしい解説がついてるのが見つからなかったんだけど、やっぱり考えぬいて(アニメ見ながら3時間くらい考えた)以下の結論に至った。
type bnats = X | Y of bnats | Z of bnats type bnat = A | B of bnats 0 = A 1 = B X 11 = B (Y X) 101011 = B (Y (Y (Z (Y (Z X)))))
とりあえず二進表現と型表現の桁の順序は逆になっていて、Aは値としての0、Xは一番上の桁の1、Yは途中の桁の1、Zは途中の桁の0という感じ。Bはbnatsを引き受けてbnatの振りをする役。コンストラクタ5つって美しくないなぁと思ったけど、でも仕方ない。これの四則演算を実装するのがさらにめんどい。以上。