Являются ли свободные монады церковными цифрами?

Комментатор недавно заявил :

Свободные монады - это церковные числа , просто использующие (Эндо-) функторы вместо функций!

Он продолжает объяснять это говоря:

Они оба являются эндофунктом (ион|или), составленным 0-n раз

Я получаю, что церковные цифры - это набор анонимных функциональных композиций, с композицией для каждого числа. Я просто не понимаю, как это относится к свободным монадам.

Мой вопрос:: Являются ли свободные монады церковными числами?

1 2
monads free-monad

1 ответ:

Вроде того.

Обобщение церковных числительных состоит в том, что числительное n является f^n, где f - эндоморфизм (стрелка, домен и кодомен которой являются одним и тем же объектом) в некоторойкатегории и f^n означает "составлять f с самим собой n раз". Обычные церковные числа относятся к категории множеств , где стрелки являются функциями, Поэтому, например, число 3, примененное к f и x, является f(f(f(x))). Например, если f(x) = x + 10, то 3 f 0 является 30.

В категориикатегорий стрелки являютсяфункторами . Там число 3, примененное к некоторому функтору f и объекту x (например, типу), снова является f(f(f(x))). Если f является, например, конструктором типа f x = Int => x, то 3 f String является Int => Int => Int => String, типом функций, которые принимают три аргумента Int и возвращают a String.

Теперь для функтора f, Free f является лисвободной монадой , порожденной f, где экземпляр типа Free f x либо просто x или f (Free f x). Таким образом, он будет иметь вид формы f(f(f(...(x))), композиции из нуля или более fs, примененной к x.

Таким образом, дело не в том, что "свободные монады-это церковные числа", а в том, что свободная монада-это конструкция типа на некотором функторе, и церковные числа на этом функторе встраиваются в этот тип.
3