O que significa a lei da Naturalidade para Traversables?

8

A lei da naturalidade afirma que:

t . traverse f == traverse (t . f) -- for every applicative transformer t

Agora, para o RHS da lei, se f tem o tipo Applicative a => x -> a y, então t deve ser do tipo (Applicative a, Applicative b) => a y -> b y, devido à composição da função.

Para LHS, travessia f tem o tipo (Applicative a, Traversable c) => c x -> a (c y). Mas como a travessia f é composta com t. transversal f, t deve ser do tipo (cx -> a (cy)) -> b y.

Agora, para o LHS, t tem o tipo a (cy) -> by, mas a partir do RHS, ele tem o tipo ay -> b y. Como é que a lei soa sob uma perspectiva de tipo?

Editar: corrigido o tipo t no LHS

user4132
fonte
Corrigido o tipo de t na dedução do LHS. Ainda não tenho certeza de como a lei segue.
user4132

Respostas:

6

Eu acho que o que você perdeu é que tdeveria ser uma transformação natural (que provavelmente também deve ter algumas propriedades de preservação da estrutura). As transformações naturais são quantificadas, da seguinte forma:

t :: forall z. a z -> b z   -- "t is an N.T. from a ~> b"

À direita, instanciamos isso em y, para obter t :: a y -> b y; à esquerda, instanciamos c ypara obter a (c y) -> b (c y). A maneira como penso é que uma transformação natural muda a camada externa, não importa o que esteja dentro. As leis da naturalidade sempre falam sobre relacionamentos entre as diferentes maneiras pelas quais algo é instanciado.

t                :: forall z. a z -> b z

f                :: x -> a y
t                :: a y -> b y           -- instantiated at y
t . f            :: x -> b y
traverse (t . f) :: c x -> b (c y)

traverse f       :: c x -> a (c y)
t                :: a (c y) -> b (c y)   -- instantiated at (c y)
t . traverse f   :: c x -> b (c y)
luqui
fonte