タイプ代数とクヌスの上向き矢印の表記

Question

this questionとthis blog postを読むと、タイプ代数とそれを乱用する方法についての詳細がわかりました。

基本的には、

1）私たちは、さらにとしてEither A Bタイプと考えることができます：A+B

2）当社は、乗算として順序対(A,B)と考えることができます：A*B

3）私たちが考えることができます関数のA -> B累乗として：B^A

ここには明らかなパターンがあります：Multiplicatイオンは繰り返し加算され、べき乗は繰り返し乗算される。これにより、指数としてKnuth to define the up arrow↑、繰返し累乗として↑↑、繰り返し↑↑で↑↑↑などとなりました。したがって、10↑↑↑↑10は巨大な数値です。

私の質問は次のとおりです。↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑代数データで表すことができる方法 タイプ？ ↑は無限の数の引数を持つ関数でなければならないようですが、あまり意味がありません。 A↑Bは、単に[A] -> Bとなるため、A↑↑↑↑Bは[[[[A]]]]->Bですか？

あなたがAckerman functionのようになるか、またはhypergrowth functionsのいずれかを説明できる場合、ボーナスポイント。

Answer 1

最も明白なレベルでは、

((...(a -> a) -> ...) -> a) -- iterated b times 

と↑↑Bを特定することができましたし、↑↑↑bはそうすべては、いくつかの長期の用語で表現することができるだけで

(a↑↑(a↑↑(...(a↑↑(a↑↑a))...))) -- iterated b times 

です関数型（したがって、非常に長いタプル型として...）。しかし、普遍的なHaskell型（基数が...または↑のものを超えている）の上で、任意の上向き矢印シンボルのための便利な表現はないと思います。 （より大きい、再帰的なデータ型に行くことなく）基底のセットのサイズに指数関数的により大きい組み合わせ依存性を持つオブジェクト...おそらくコンビナトリアルセット理論にそのようなオブジェクトがいくつかありますか？ （あなたの質問はタイプに特有のものよりもセットのサイズの詳細[私へ]そうです。）

（Wikipedia page you linkedが既にアッカーマン関数にこれらのオブジェクトを接続します。）