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

9

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
Asad Saeeduddin
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Samuel Liew
Uma definição possível de "tamanho fixo" seria "representável". Todos os functores representáveis ​​são fortes aplicativos no sentido descrito aqui, porque (->) rsão e são isomórficos da maneira certa.
Daniel Wagner
@DanielWagner Acho que você precisa mais do que apenas um isomorfismo para herdar o forte aplicativo (->) r; você precisa dos componentes do isomorfismo para preservar a forte estrutura aplicativa. Por alguma razão, a Representableclasse de tipo em Haskell possui uma tabulate . return = returnlei misteriosa (que nem sequer faz sentido para os functores não monádicos), mas fornece 1/4 de condições que precisamos dizer tabulatee zipsão morfismos de uma categoria adequada de monoides. . Os outros três são leis extras que você precisa exigir.
Asad Saeeduddin
Desculpe, isso deve ser " tabulatee indexsão morfismos de uma categoria adequada ..."
Asad Saeeduddin
@AsadSaeeduddin A maneira como a lei é declarada nos documentos é estranhamente específica, talvez, mas acontece que exigir returnnão é um problema sério. cotraverse getConst . Consté uma implementação padrão para return/ pureem termos de Distributivee, uma vez que as distribuições / representantes têm forma fixa, essa implementação é única.
duplode 10/03

Respostas:

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

bradrn
fonte
Hum. É realmente claro que "só pode existir um valor distinto do tipo f ()" implica "o número de ocorrências de anão pode variar" na presença de GADTs sofisticados e outras coisas?
Daniel Wagner
@DanielWagner Verificou-se que “o número de ocorrências de anão pode variar” não é uma condição suficiente para uma StrongApplicativeinstância; por exemplo, data Writer w a = Writer (w,a)tem multiplicidade não variável de a, mas não é a StrongApplicative. Você realmente precisa que a forma do functor seja invariável, o que acredito ser uma consequência de f ()ser um singleton.
bradrn 9/03
Não tenho certeza se vejo como isso é relevante. Na resposta, ao confirmar a segunda conjectura, você argumenta que "aplicativo forte" implica "um distinto f ()" implica "número de ocorrências de anão pode variar". Estou objetando que o último passo desse argumento não é claramente verdadeiro; por exemplo, considere data Weird a where One :: a -> Weird a; None :: Weird Bool. Há um valor distinto do tipo Weird (), mas diferentes construtores têm números variáveis ​​de as por dentro. (Não é um contra-exemplo completo aqui porque Functoré difícil, mas como sabemos que não pode ser corrigido?)
Daniel Wagner
@DanielWagner Bom ponto que Weird ()é um singleton, mas não é de forma fixa. Mas Weirdnão é um Functor, então não pode ser de StrongApplicativequalquer maneira. Suponho que a conjectura relevante seria: se ffor um Functor, f ()ser um singleton implica fuma forma fixa ? Eu suspeito fortemente que isso seja verdade, mas como você observou, ainda não tenho nenhuma prova.
bradrn 10/03
5

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.

Asad Saeeduddin
fonte
5

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)
Daniel Wagner
fonte
Atualmente ponderando: instance StrongApplicative f => Representable f where type Rep f = forall x. f x -> x. indexé fácil. Ainda não elaborei o truque tabulate, mas parece tentadoramente próximo.
Daniel Wagner
Em discussão com @AsadSaeeduddin, também consegui encontrar essa mesma StrongApplicativeinstância, mas não pude provar as leis. Parabéns por descobrir! Tentei fazer a Representableinstância também StrongApplicative, mas não consegui pensar em um bom Reptipo - ficaria curioso para saber como você forall x. f x -> xconsegue isso.
bradrn 10/03
@bradrn Lembre-se de que a hipótese é que essas coisas têm um conjunto fixo de "orifícios" nos quais os elementos se encaixam. Então as funções do tipo forall x. f x -> xsão exatamente aquelas funções que escolhem um furo e retornam o valor nesse furo. (E, ao pensar em como implementar tabulate, propus uma objeção ao tipo unhusk; veja comentários sobre a própria pergunta para obter detalhes.)
Daniel Wagner
Obrigado @DanielWagner! Essa é uma abordagem muito inteligente - eu não teria pensado nisso.
bradrn 10/03
Depois de tentar implementá-lo, não acho que estou convencido de que forall x. f x -> xfuncionará como Rep. Meu raciocínio é que, usando isso Rep, você pode escrever indexpara qualquer tipo, não apenas um StrongApplicative- por isso suspeito que forall x. f x -> xpossa ser muito geral.
bradrn 10/03