Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет Journal de Chaource ([info]lj_chaource)
@ 2018-04-03 22:02:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Some polynomial functors are not monadic
Contrary to what I thought before (I thought all pointed polynomial functors are monadic), now I found simple examples of polynomial functors that are definitely not monadic.

A first example is F(A) = A * A + A * A * A. More generally, A^m + A^n, unless m == n.

The intuitive reason they are not monadic is that F(A) is isomorphic to the co-product (F_m -> A) + (F_n -> A) where F_k is a finite type with just k different values. Taken separately, each of (F_k -> A) is a monad. Generally, a co-product of two different monads is not a monad. In this case, one can check that the co-product (r1 -> A) + (r2 -> A) does not have any implementations of `join` when the types r1 and r2 are different and unrelated (no natural transformations r1 -> r2 or r2 -> r1). In the case of F_k, there are of course such natural transformations, but they are not "canonical enough" (they arbitrarily duplicate or discard data) and so the resulting implementation of `join` does not satisfy the monad's laws.

I also checked by exhaustive search that F(A) = A*A + A*A*A does not have an implementation of `unit` and `join` that satisfies the laws of the monad. My previous (mistaken) belief that all such functors were monadic was based on checking that `unit` and `bind` can be implemented, without checking the laws.

However, the exhaustive search was computer-based and could be incorrect. I am still not 100% certain that A*A + A*A*A is not a monad, but it doesn't look very likely at this point.

This raises the question of how to recognize whether a given polynomial functor is a monad. Doing exhaustive search on all possible implementations of `unit` and `join` is too time-consuming because there is an exponential number of such implementations.


(Читать комментарии) (Добавить комментарий)