Existe um morfismo de mônada sem identidade M ~> M que é monadicamente natural em M?

Sabe-se que transformações naturais com assinatura de tipo a -> adevem ser funções de identidade. Isto segue o lema de Yoneda, mas também pode ser derivado diretamente. Essa pergunta pede a mesma propriedade, mas morfismos de mônada, em vez de transformações naturais.

Considere morfismos de mônada M ~> Nentre mônadas. (Essas são transformações naturais M a -> N aque preservam as operações da mônada de ambos os lados. Essas transformações são os morfismos na categoria de mônadas.) Podemos perguntar se existe um morfismo da mônada e :: (Monad m) => m a -> m aque funcione da mesma maneira para todas as mônadas m. Em outras palavras, um morfismo da mônada edeve ser monadicamente natural no parâmetro do tipo mônada m.

A lei da naturalidade monádica diz que, para qualquer morfismo de mônada f: M a -> N a entre duas mônadas M e N, devemos ter f . e = e . fparâmetros de tipo adequados.

A questão é: podemos provar que tal edeve ser uma função de identidade ou existe um contra-exemplo de um morfismo de mônada sem identidade edefinido como

  e :: (Monad m) => m a -> m a
  e ma = ...

Uma tentativa fracassada de definir isso eé:

 e ma = do
         _ <- ma
         x <- ma
         return x

Outra tentativa fracassada é

 e ma = do
         x <- ma
         _ <- ma
         return x

Ambas as tentativas têm a assinatura de tipo correta, mas não cumprem as leis de moradismo da mônada.

Parece que o lema de Yoneda não pode ser aplicado a este caso, porque não há morfismos de mônada Unit ~> Monde Unitestá a mônada unitária. Também não consigo encontrar nenhuma prova diretamente.

Eu acho que você já esgotou todas as possibilidades interessantes. Qualquer Monad m => m a -> m afunção que possamos definir será inevitavelmente assim:

e :: forall m a. Monad m => m a -> m a
e u = u >>= k
    where
    k :: a -> m a
    k = _

Em particular, se k = return, e = id. Para enão ser id, kdeve usar de u maneira não trivial (por exemplo, k = const ue k = flip fmap u . constcorresponder a suas duas tentativas). Nesse caso, porém, os uefeitos serão duplicados, levando ea deixar de ser um morfismo da mônada para várias opções de mônada m. Sendo assim, o único morfismo da mônada totalmente polimórfico na mônada é id.

Vamos tornar o argumento mais explícito.

Por uma questão de clareza, mudarei para a apresentação join/ return/ fmappor um momento. Queremos implementar:

e :: forall m a. Monad m => m a -> m a
e u = _

Com o que podemos preencher o lado direito? A escolha mais óbvia é u. Por si só, isso significa e = id, o que não parece interessante. No entanto, como também temos join, returne fmap, existe a opção de raciocinar indutivamente, tendo ucomo caso base. Digamos que temos alguns v :: m a, construídos usando os meios que temos em mãos. Além de vsi, temos as seguintes possibilidades:

1. join (return v), que é ve, portanto, não nos diz nada de novo;

2. join (fmap return v), o que também é v; e

3. join (fmap (\x -> fmap (f x) w) v), para alguns outros w :: m acriados de acordo com nossas regras, e alguns f :: a -> a -> a. (Adicionar mcamadas ao tipo de f, como em a -> a -> m ae joins extras para removê-las não levaria a lugar algum, pois teríamos que mostrar a procedência dessas camadas e as coisas acabariam se reduzindo para os outros casos.)

O único caso interessante é o nº 3. Neste ponto, vou pegar um atalho:

join (fmap (\x -> fmap (f x) w) v)
    = v >>= \x -> fmap (f x) w
    = f <$> v <*> w

Qualquer ulado não- direito, portanto, pode ser expresso na forma f <$> v <*> w, com ve wsendo uma uou mais iterações desse padrão, chegando finalmente a us nas folhas. Expressões aplicativas desse tipo, no entanto, têm uma forma canônica, obtida usando as leis aplicáveis ​​para reassociar todos os usos da (<*>)esquerda, que neste caso devem ser assim ...

c <$> u <*> ... <*> u

... com as reticências representando zero ou mais ocorrências adicionais de useparadas por <*>e csendo uma a -> ... -> a -> afunção da aridade apropriada. Como aé totalmente polimórfico, cdeve, por parametridade, ser uma constfunção semelhante a que escolhe um de seus argumentos. Sendo assim, qualquer expressão pode ser reescrita em termos de (<*)e (*>)...

u *> ... <* u

... com as reticências representando zero ou mais ocorrências adicionais de useparadas por um *>ou outro <*, não havendo *>o direito de a <*.

Voltando ao início, todas as idimplementações não candidatas devem ter a seguinte aparência:

e u = u *> ... <* u

Também queremos eser um morfismo de mônada. Como conseqüência, também deve ser um morfismo aplicado. Em particular:

-- (*>) = (>>) = \u v -> u >>= \_ -> v
e (u *> v) = e u *> e v

Isso é:

(u *> v) *> ... <* (u >* v) = (u *> ... <* u) *> (v *> ... <* v)

Agora temos um caminho claro para um contra-exemplo. Se usarmos as leis aplicativas para converter ambos os lados para a forma canônica, vamos (ainda) acabar com intercalados us e vs no lado esquerdo, e com todos vs após todos os us no lado direito. Isso significa que a propriedade não se aplica a mônadas como IO, Stateou Writer, independentemente de quantas (*>)e (<*)existem e, ou exatamente quais valores são escolhidos pelas constfunções semelhantes de ambos os lados. Uma demonstração rápida:

GHCi> e u = u *> u <* u  -- Canonical form: const const <$> u <*> u <*> u
GHCi> e (print 1 *> print 2)
1
2
1
2
1
2
GHCi> e (print 1) *> e (print 2)
1
1
1
2
2
2