Todos os contêineres de tamanho fixo são fortes monitores funcionais e / ou vice-versa?

A Applicativeclasse typeclass representa funcores monoidais relaxados que preservam a estrutura monoidal cartesiana na categoria de funções digitadas.

Em outras palavras, dados os isomorfismos canônicos que testemunham que (,)formam uma estrutura monoidal:

-- Implementations left to the motivated reader
assoc_fwd :: ((a, b), c) -> (a, (b, c))
assoc_bwd :: (a, (b, c)) -> ((a, b), c)

lunit_fwd :: ((), a) -> a
lunit_bwd :: a -> ((), a)

runit_fwd :: (a, ()) -> a
runit_bwd :: a -> (a, ())

A classe de tipo e suas leis podem ser equivalentemente escritas assim:

class Functor f => Applicative f
  where
  zip :: (f a, f b) -> f (a, b)
  husk :: () -> f ()

-- Laws:

-- assoc_fwd >>> bimap id zip >>> zip
-- =
-- bimap zip id >>> zip >>> fmap assoc_fwd

-- lunit_fwd
-- =
-- bimap husk id >>> zip >>> fmap lunit_fwd

-- runit_fwd
-- =
-- bimap id husk >>> zip >>> fmap runit_fwd

Pode-se perguntar como seria um functor oplax monoidal em relação à mesma estrutura:

class Functor f => OpApplicative f
  where
  unzip :: f (a, b) -> (f a, f b)
  unhusk :: f () -> ()

-- Laws:

-- assoc_bwd <<< bimap id unzip <<< unzip
-- =
-- bimap unzip id <<< unzip <<< fmap assoc_bwd

-- lunit_bwd
-- =
-- bimap unhusk id <<< unzip <<< fmap lunit_bwd

-- runit_bwd
-- =
-- bimap id unhusk <<< unzip <<< fmap runit_bwd

Se pensarmos nos tipos envolvidos nas definições e leis, a verdade decepcionante será revelada; OpApplicativenão é uma restrição mais específica do que Functor:

instance Functor f => OpApplicative f
  where
  unzip fab = (fst <$> fab, snd <$> fab)
  unhusk = const ()

No entanto, embora todo Applicativefunctor (realmente, qualquer um Functor) seja trivial OpApplicative, não há necessariamente uma boa relação entre laxidades Applicativee OpApplicativeoplaxidades. Para que possamos procurar fortes monoides na estrutura monoidal cartesiana:

class (Applicative f, OpApplicative f) => StrongApplicative f

-- Laws:
-- unhusk . husk = id
-- husk . unhusk = id
-- zip . unzip = id
-- unzip . zip = id

A primeira lei acima é trivial, pois o único habitante do tipo () -> () é a função de identidade ativada ().

No entanto, as três leis restantes e, portanto, a própria subclasse, não são triviais. Especificamente, nem todo Applicativeé um exemplo legal dessa classe.

Aqui estão alguns Applicativefunctores para os quais podemos declarar casos legais de StrongApplicative:

• Identity
• VoidF
• (->) r
• Monoid m => (,) m (ver respostas)
• Vec (n :: Nat)
• Stream (infinito)

E aqui estão alguns Applicatives para os quais não podemos:

• []
• Either e
• Maybe
• NonEmptyList

O padrão aqui sugere que a StrongApplicativeclasse é, de certo modo, a FixedSizeclasse, onde "tamanho fixo" ^* significa que a multiplicidade ^** de habitantes dea um habitante de f aé fixa.

Isso pode ser afirmado como duas conjecturas:

• Cada Applicative representação de um contêiner de "tamanho fixo" de elementos de seu argumento de tipo é uma instância deStrongApplicative
• Não StrongApplicativeexiste nenhuma instância em que o número de ocorrências de apossa variar

Alguém pode pensar em contra-exemplos que refutam essas conjecturas, ou algum raciocínio convincente que demonstra por que são verdadeiros ou falsos?

* Percebo que não defini corretamente o adjetivo "tamanho fixo". Infelizmente, a tarefa é um pouco circular. Não conheço nenhuma descrição formal de um contêiner de "tamanho fixo" e estou tentando criar um.StrongApplicativeé a minha melhor tentativa até agora.

Para avaliar se essa é uma boa definição, no entanto, preciso de algo para compará-la. Dada uma definição formal / informal do que significa para um functor ter um determinado tamanho ou multiplicidade em relação aos habitantes de seu tipo de argumento, a questão é se a existência de umStrongApplicative instância distingue precisamente os funcetores de tamanho fixo e variável.

Não estando ciente de uma definição formal existente, estou fazendo um apelo à intuição ao usar o termo "tamanho fixo". No entanto, se alguém já conhece um formalismo existente para o tamanho de um functor e pode compararStrongApplicative a ele, tanto melhor.

** Por "multiplicidade", refiro-me, em sentido lato, a "quantos" elementos arbitrários do tipo de parâmetro do functor ocorrem em um habitante do tipo de codomain do functor. Isso não leva em consideração o tipo específico ao qual o functor é aplicado e, portanto, não considera nenhum habitante específico do tipo de parâmetro.

Não ser preciso quanto a isso causou alguma confusão nos comentários, então aqui estão alguns exemplos do que eu consideraria o tamanho / multiplicidade de vários functores:

• VoidF: fixo, 0
• Identity: fixo, 1
• Maybe: variável, mínimo 0, máximo 1
• []: variável, mínimo 0, máximo infinito
• NonEmptyList: variável, mínimo 1, máximo infinito
• Stream: fixo, infinito
• Monoid m => (,) m: fixo, 1
• data Pair a = Pair a a: fixo, 2
• Either x: variável, mínimo 0, máximo 1
• data Strange a = L a | R a: fixo, 1

• CadaApplicative representação de um contêiner de "tamanho fixo" de elementos de seu argumento de tipo é uma instância deStrongApplicative
• Não StrongApplicativeexiste nenhuma instância em que o número de ocorrências de apossa variar

Alguém pode pensar em contra-exemplos que refutam essas conjecturas, ou algum raciocínio convincente que demonstra por que são verdadeiros ou falsos?

Não tenho certeza sobre essa primeira conjectura e, com base em discussões com @AsadSaeeduddin, é provável que seja difícil provar, mas a segunda conjectura é verdadeira. Para ver o porquê, considere a StrongApplicativelei husk . unhusk == id; isto é, para todos x :: f (), husk (unhusk x) == x. Mas, em Haskell, unhusk == const ()para que a lei é equivalente a dizer para todos x :: f (), husk () == x. Mas isso, por sua vez, implica que só pode existir um valor distinto do tipo f (): se houvesse dois valores x, y :: f (), então x == husk ()e husk () == y, portanto,x == y . Mas se houver apenas um f ()valor possível , ele fdeverá ter uma forma fixa. (por exemplo data Pair a = Pair a a, para , existe apenas um valor do tipo Pair (), sendo este Pair () (), mas existem vários valores do tipo Maybe ()ou[()] .)husk . unhusk == idimplica que fdeve ter uma forma fixa.

Podemos responder pelo menos uma dessas perguntas de forma negativa:

Todo aplicativo que representa um contêiner de "tamanho fixo" de elementos de seu argumento de tipo é uma instância de StrongApplicative

De fato, um dos exemplos de um lícito StrongApplicativena questão original está errado. O aplicativo escritor Monoid => (,) mnão éStrongApplicative , por exemplo husk $ unhusk $ ("foo", ()) == ("", ()) /= ("foo", ()).

Da mesma forma, o exemplo de um contêiner de tamanho fixo:

data Strange a = L a | R a

da multiplicidade fixa 1, não é um aplicativo forte, porque se definirmos husk = Leftentãohusk $ unhusk $ Right () /= Right () , e vice-versa. Uma maneira equivalente de ver isso é que esse é apenas o aplicativo de gravação para sua escolha de monóide Bool.

Portanto, existem aplicativos de "tamanho fixo" que não são StrongApplicative. StrongApplicativeAinda não se sabe se todos os s são de tamanho fixo.

Vamos considerar functors representáveis ​​como nossa definição de "contêiner de tamanho fixo":

class Representable f where
    type Rep f
    tabulate :: (Rep f -> a) -> f a
    index :: f a -> Rep f -> a

O real Representabletem algumas leis e superclasses, mas, para os fins desta resposta, precisamos de apenas duas propriedades:

tabulate . index = id
index . tabulate = id

(Ok, também precisamos de um cumpridor da lei instance StrongApplicative ((->) r). Fácil, você já concorda que ele existe.)

Se tomarmos essa definição, posso confirmar essa conjectura 1:

Cada Applicativerepresentação de um contêiner de "tamanho fixo" de elementos de seu argumento de tipo é uma instância [cumpridora da lei] deStrongApplicative

é verdade. Aqui está como:

instance Representable f => Applicative f where
    zip (fa, fb) = tabulate (zip (index fa, index fb))
    husk = tabulate . husk

instance Representable f => OpApplicative f where
    unzip fab = let (fa, fb) = unzip (index fab) in (tabulate fa, tabulate fb)
    unhusk = unhusk . index

instance Representable f => StrongApplicative f

Há muitas leis para provar, mas vou me concentrar apenas nas quatro grandes que StrongApplicativeadicionam - você provavelmente já acredita nas iniciais Applicativee OpApplicative, se não acredita , as provas são parecidas com as abaixo ( que por sua vez se parecem bastante). Para maior clareza, vou usar zipf, huskfetc. para a instância de função, e zipr, huskr, etc. para a instância representável, para que possa manter o controle de qual é qual. (E para que seja fácil verificar se não consideramos o que estamos tentando provar como suposição! Não há problema unhuskf . huskf = idem provarunhuskr . huskr = id , mas seria errado supor unhuskr . huskr = idnessa mesma prova.)

A prova de cada lei procede basicamente da mesma maneira: desenrole as definições, descarte o isomorfismo que Representablelhe fornece e use a lei análoga para funções.

unhuskr . huskr
= { def. of unhuskr and huskr }
(unhuskf . index) . (tabulate . huskf)
= { index . tabulate = id }
unhuskf . huskf
= { unhuskf . huskf = id }
id

huskr . unhuskr
= { def. of huskr and unhuskr }
(tabulate . huskf) . (unhuskf . index)
= { huskf . unhuskf = id }
tabulate . index
= { tabulate . index = id }
id

zipr (unzipr fab)
= { def. of unzipr }
zipr (let (fa, fb) = unzipf (index fab) in (tabulate fa, tabulate fb))
= { def. of zipr }
let (fa, fb) = unzipf (index fab) in tabulate (zipf (index (tabulate fa), index (tabulate fb)))
= { index . tabulate = id }
let (fa, fb) = unzipf (index fab) in tabulate (zipf (fa, fb))
= { def. of (fa, fb) }
tabulate (zipf (unzipf (index fab)))
= { zipf . unzipf = id }
tabulate (index fab)
= { tabulate . index = id }
fab

unzipr (zipr (fa, fb))
= { def. of zipr }
unzipr (tabulate (zipf (index fa, index fb)))
= { def. of unzipr }
let (fa', fb') = unzipf (index (tabulate (zipf (index fa, index fb))))
in (tabulate fa', tabulate fb')
= { index . tabulate = id }
let (fa', fb') = unzipf (zipf (index fa, index fb))
in (tabulate fa', tabulate fb')
= { unzipf . zipf = id }
let (fa', fb') = (index fa, index fb)
in (tabulate fa', tabulate fb')
= { def. of fa' and fb' }
(tabulate (index fa), tabulate (index fb))
= { tabulate . index = id }
(fa, fb)