|
| |||
|
|
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. |
||||||||||||||