Cada Mônada alternativa é filtrável?

8

A categoria de conjuntos é monoidal cartesiano e cocartesiano monoidal. Os tipos de isomorfismos canônicos que testemunham essas duas estruturas monoidais estão listados abaixo:

type x + y = Either x y
type x × y = (x, y)

data Iso a b = Iso { fwd :: a -> b, bwd :: b -> a }

eassoc :: Iso ((x + y) + z) (x + (y + z))
elunit :: Iso (Void + x) x
erunit :: Iso (x + Void) x

tassoc :: Iso ((x × y) × z) (x × (y × z))
tlunit :: Iso (() × x) x
trunit :: Iso (x × ()) x

Para os fins desta pergunta, defino Alternativeser um functor monoidal frouxo de Hask sob o Eithertensor para Hask sob o (,)tensor (e não mais):

class Functor f => Alt f
  where
  union :: f a × f b -> f (a + b)

class Alt f => Alternative f
  where
  nil :: () -> f Void

As leis são justas para um relaxador monoidal relaxado.

Associatividade:

fwd tassoc >>> bimap id union >>> union
=
bimap union id >>> union >>> fmap (fwd eassoc)

Unidade esquerda:

fwd tlunit
=
bimap nil id >>> union >>> fmap (fwd elunit)

Unidade direita:

fwd trunit
=
bimap id nil >>> union >>> fmap (fwd erunit)

Aqui está como recuperar as operações mais familiares para a Alternativeclasse de tipos em termos dos mapas de coerência da codificação laxante de função monoidal:

(<|>) :: Alt f => f a -> f a -> f a
x <|> y = either id id <$> union (Left <$> x, Right <$> y)

empty :: Alternative f => f a
empty = absurd <$> nil ()

Defino Filterablefunctors ser oplax functors monoidais de Hask sob o Eithertensor para Hask sob o (,)tensor:

class Functor f => Filter f
  where
  partition :: f (a + b) -> f a × f b

class Filter f => Filterable f
  where
  trivial :: f Void -> ()
  trivial = const ()

Tendo por suas leis um pouco atrasadas leis de função monoidal relaxadas:

Associatividade:

bwd tassoc <<< bimap id partition <<< partition
=
bimap partition id <<< partition <<< fmap (bwd eassoc)

Unidade esquerda:

bwd tlunit
=
bimap trivial id <<< partition <<< fmap (bwd elunit)

Unidade direita:

bwd trunit
=
bimap id trivial <<< partition <<< fmap (bwd erunit)

Definindo funções padrão de filtro-y como mapMaybee filterem termos do codificador oplax monoidal deixado como um exercício para o leitor interessado:

mapMaybe :: Filterable f => (a -> Maybe b) -> f a -> f b
mapMaybe = _

filter :: Filterable f => (a -> Bool) -> f a -> f a
filter = _

A questão é esta: é tudo Alternative Monadtambém Filterable?

Podemos digitar tetris para uma implementação:

instance (Alternative f, Monad f) => Filter f
  where
  partition fab = (fab >>= either return (const empty), fab >>= either (const empty) return)

Mas essa implementação é sempre legal? Às vezes é legal (para alguma definição formal de "às vezes")? Provas, contra-exemplos e / ou argumentos informais seriam todos muito úteis. Obrigado.

Asad Saeeduddin
fonte
Pessoalmente, eu ficaria surpreso se fosse sempre válido. Certamente, às vezes é válido no sentido de que existem functores para os quais é válido, mas tenho a duvidar de que seja uma classe particularmente interessante.
dfeuer 18/03
@dfeuer Você tem algum contra-exemplo em mente para o qual obviamente não é válido? Talvez isso seja instrutivo.
Asad Saeeduddin 18/03
Tenho certeza de que essa é sempre uma instância legal, apenas do desdobramento das definições e de algumas reescrições triviais (sugerindo assim que as Filterableleis são bastante fracas). @AsadSaeeduddin Considere adquirir algumas habilidades de prova do teorema interativo para que você possa estender a mentalidade "tipos de uso, não o cérebro" a provas também!
Li-yao Xia

Respostas:

3

Aqui vai um argumento que apoia amplamente sua bela ideia.

Parte um: mapMaybe

Meu plano aqui é reafirmar o problema em termos de mapMaybe, esperando que isso nos leve a um terreno mais familiar. Para fazer isso, usarei algumas Eitherfunções do utilitário -juggling:

maybeToRight :: a -> Maybe b -> Either a b
rightToMaybe :: Either a b -> Maybe b
leftToMaybe :: Either a b -> Maybe a
flipEither :: Either a b -> Either b a

(Peguei os três primeiros nomes de relude e o quarto de erros . A propósito, os erros oferecem maybeToRighte rightToMaybecomo notee hushrespectivamente, em Control.Error.Util.)

Como você observou, mapMaybepode ser definido em termos de partition:

mapMaybe :: Filterable f => (a -> Maybe b) -> f a -> f b
mapMaybe f = snd . partition . fmap (maybeToRight () . f)

Fundamentalmente, também podemos fazer o contrário:

partition :: Filterable f => f (Either a b) -> (f a, f b)
partition = mapMaybe leftToMaybe &&& mapMaybe rightToMaybe

Isso sugere que faz sentido reformular suas leis em termos de mapMaybe. Com as leis de identidade, isso nos dá uma ótima desculpa para esquecer completamente trivial:

-- Left and right unit
mapMaybe rightToMaybe . fmap (bwd elunit) = id  -- [I]
mapMaybe leftToMaybe . fmap (bwd erunit) = id   -- [II]

Quanto à associatividade, podemos usar rightToMaybee leftToMaybedividir a lei em três equações, uma para cada componente que obtemos das partições sucessivas:

-- Associativity
mapMaybe rightToMaybe . fmap (bwd eassoc)
    = mapMaybe rightToMaybe . mapMaybe rightToMaybe  -- [III]
mapMaybe rightToMaybe . mapMaybe leftToMaybe . fmap (bwd eassoc)
    = mapMaybe leftToMaybe . mapMaybe rightToMaybe   -- [IV]
mapMaybe leftToMaybe . fmap (bwd eassoc)
    = mapMaybe leftToMaybe . mapMaybe leftToMaybe    -- [V]

Parametridade significa mapMaybeé agnóstico em relação aos Eithervalores com os quais estamos lidando aqui. Sendo assim, podemos usar nosso pequeno arsenal de Eitherisomorfismos para embaralhar as coisas e mostrar que [I] é equivalente a [II] e [III] é equivalente a [V]. Agora, temos três equações:

mapMaybe rightToMaybe . fmap (bwd elunit) = id       -- [I]
mapMaybe rightToMaybe . fmap (bwd eassoc)
    = mapMaybe rightToMaybe . mapMaybe rightToMaybe  -- [III]
mapMaybe rightToMaybe . mapMaybe leftToMaybe . fmap (bwd eassoc)
    = mapMaybe leftToMaybe . mapMaybe rightToMaybe   -- [IV]

A parametridade nos permite engolir o fmapin [I]:

mapMaybe (rightToMaybe . bwd elunit) = id

Isso, no entanto, é simplesmente ...

mapMaybe Just = id

... o que equivale à lei de conservação / identidade da da witherable 'sFilterable :

mapMaybe (Just . f) = fmap f

Que Filterabletambém tem uma lei de composição:

-- The (<=<) is from the Maybe monad.
mapMaybe g . mapMaybe f = mapMaybe (g <=< f)

Também podemos derivar este de nossas leis? Vamos começar de [III] e, mais uma vez, a parametridade faz seu trabalho. Este é mais complicado, então vou anotá-lo na íntegra:

mapMaybe rightToMaybe . fmap (bwd eassoc)
    = mapMaybe rightToMaybe . mapMaybe rightToMaybe  -- [III]

-- f :: a -> Maybe b; g :: b -> Maybe c
-- Precomposing fmap (right (maybeToRight () . g) . maybeToRight () . f)
-- on both sides:
mapMaybe rightToMaybe . fmap (bwd eassoc)
  . fmap (right (maybeToRight () . g) . maybeToRight () . f)
    = mapMaybe rightToMaybe . mapMaybe rightToMaybe 
      . fmap (right (maybeToRight () . g) . maybeToRight () . f)

mapMaybe rightToMaybe . mapMaybe rightToMaybe 
  . fmap (right (maybeToRight () . g) . maybeToRight () . f)  -- RHS
mapMaybe rightToMaybe . fmap (maybeToRight () . g)
  . mapMaybe rightToMaybe . fmap (maybeToRight () . f)
mapMaybe (rightToMaybe . maybeToRight () . g)
 . mapMaybe (rightToMaybe . maybeToRight () . f)
mapMaybe g . mapMaybe f

mapMaybe rightToMaybe . fmap (bwd eassoc)
  . fmap (right (maybeToRight () . g) . maybeToRight () . f)  -- LHS
mapMaybe (rightToMaybe . bwd eassoc 
    . right (maybeToRight () . g) . maybeToRight () . f)
mapMaybe (rightToMaybe . bwd eassoc 
    . right (maybeToRight ()) . maybeToRight () . fmap @Maybe g . f)
-- join @Maybe
--     = rightToMaybe . bwd eassoc . right (maybeToRight ()) . maybeToRight ()
mapMaybe (join @Maybe . fmap @Maybe g . f)
mapMaybe (g <=< f)  -- mapMaybe (g <=< f) = mapMaybe g . mapMaybe f

Na outra direção:

mapMaybe (g <=< f) = mapMaybe g . mapMaybe f
-- f = rightToMaybe; g = rightToMaybe
mapMaybe (rightToMaybe <=< rightToMaybe)
    = mapMaybe rightToMaybe . mapMaybe rightToMaybe
mapMaybe (rightToMaybe <=< rightToMaybe)  -- LHS
mapMaybe (join @Maybe . fmap @Maybe rightToMaybe . rightToMaybe)
-- join @Maybe
--     = rightToMaybe . bwd eassoc . right (maybeToRight ()) . maybeToRight ()
mapMaybe (rightToMaybe . bwd eassoc 
    . right (maybeToRight ()) . maybeToRight ()
      . fmap @Maybe rightToMaybe . rightToMaybe)
mapMaybe (rightToMaybe . bwd eassoc 
    . right (maybeToRight () . rightToMaybe) 
      . maybeToRight () . rightToMaybe)
mapMaybe (rightToMaybe . bwd eassoc)  -- See note below.
mapMaybe rightToMaybe . fmap (bwd eassoc)
-- mapMaybe rightToMaybe . fmap (bwd eassoc)
--     = mapMaybe rightToMaybe . mapMaybe rightToMaybe

(Observação: enquanto maybeToRight () . rightToMaybe :: Either a b -> Either () bnão estiver id, na derivação acima os valores à esquerda serão descartados de qualquer maneira, portanto, é justo eliminá-lo como se fosse id.)

Assim [III] é equivalente à lei composição de witherable s' Filterable.

Neste ponto, podemos usar a lei de composição para lidar com [IV]:

mapMaybe rightToMaybe . mapMaybe leftToMaybe . fmap (bwd eassoc)
    = mapMaybe leftToMaybe . mapMaybe rightToMaybe   -- [IV]
mapMaybe (rightToMaybe <=< leftToMaybe) . fmap (bwd eassoc)
    = mapMaybe (letfToMaybe <=< rightToMaybe)
mapMaybe (rightToMaybe <=< leftToMaybe . bwd eassoc)
    = mapMaybe (letfToMaybe <=< rightToMaybe)
-- Sufficient condition:
rightToMaybe <=< leftToMaybe . bwd eassoc = letfToMaybe <=< rightToMaybe
-- The condition holds, as can be directly verified by substiuting the definitions.

Basta mostrar que sua classe equivale a uma formulação bem estabelecida de Filterable, o que é um resultado muito bom. Aqui está um resumo das leis:

mapMaybe Just = id                            -- Identity
mapMaybe g . mapMaybe f = mapMaybe (g <=< f)  -- Composition

Como observam os documentos ocultáveis , essas são leis de um functor de Kleisli Maybe a Hask .

Parte dois: Alternativa e Mônada

Agora podemos responder à sua pergunta real, que era sobre mônadas alternativas. Sua implementação proposta partitionfoi:

partitionAM :: (Alternative f, Monad f) => f (Either a b) -> (f a, f b)
partitionAM
    = (either return (const empty) =<<) &&& (either (const empty) return =<<)

Seguindo meu plano mais amplo, mudarei para a mapMaybeapresentação:

mapMaybe f
snd . partition . fmap (maybeToRight () . f)
snd . (either return (const empty) =<<) &&& (either (const empty) return =<<)
    . fmap (maybeToRight () . f)
(either (const empty) return =<<) . fmap (maybeToRight () . f)
(either (const empty) return . maybeToRight . f =<<)
(maybe empty return . f =<<)

E assim podemos definir:

mapMaybeAM :: (Alternative f, Monad f) => (a -> Maybe b) -> f a -> f b
mapMaybeAM f u = maybe empty return . f =<< u

Ou, em uma ortografia sem ponto:

mapMaybeAM = (=<<) . (maybe empty return .)

Alguns parágrafos acima, observei que as Filterableleis dizem que mapMaybeé o mapeamento morfístico de um functor de Kleisli Maybe a Hask . Dado que a composição de functors é um functor, e (=<<)é o mapeamento morphism de um functor de Kleisli f a Hask , (maybe empty return .)sendo o mapeamento morphism de um functor de Kleisli Talvez a Kleisli f suficiente para mapMaybeAMser legal. As leis relevantes do functor são:

maybe empty return . Just = return  -- Identity
maybe empty return . g <=< maybe empty return . f
    = maybe empty return . (g <=< f)  -- Composition

Essa lei de identidade é válida, então vamos nos concentrar na composição:

maybe empty return . g <=< maybe empty return . f
    = maybe empty return . (g <=< f)
maybe empty return . g =<< maybe empty return (f a)
    = maybe empty return (g =<< f a)
-- Case 1: f a = Nothing
maybe empty return . g =<< maybe empty return Nothing
    = maybe empty return (g =<< Nothing)
maybe empty return . g =<< empty = maybe empty return Nothing
maybe empty return . g =<< empty = empty  -- To be continued.
-- Case 2: f a = Just b
maybe empty return . g =<< maybe empty return (Just b)
    = maybe empty return (g =<< Just b)
maybe empty return . g =<< return b = maybe empty return (g b)
maybe empty return (g b) = maybe empty return (g b)  -- OK.

Portanto, mapMaybeAMé lícito se maybe empty return . g =<< empty = emptyfor o caso g. Agora, se emptyfor definido como absurd <$> nil (), como você fez aqui, podemos provar que, f =<< empty = emptypara qualquer f:

f =<< empty = empty
f =<< empty  -- LHS
f =<< absurd <$> nil ()
f . absurd =<< nil ()
-- By parametricity, f . absurd = absurd, for any f.
absurd =<< nil ()
return . absurd =<< nil ()
absurd <$> nil ()
empty  -- LHS = RHS

Intuitivamente, se emptyestiver realmente vazio (como deve ser, dada a definição que estamos usando aqui), não haverá valores fa serem aplicados e, portanto, f =<< emptynão poderá resultar em nada além deempty .

Uma abordagem diferente aqui seria analisar a interação das classes Alternativee Monad. Quando isso acontece, há uma classe para monads alternativas: MonadPlus. Por conseguinte, um reestilizado mapMaybepode ser assim:

-- Lawful iff, for any f, mzero >>= maybe empty mzero . f = mzero
mmapMaybe :: MonadPlus m => (a -> Maybe b) -> m a -> m b
mmapMaybe f m = m >>= maybe mzero return . f

Embora existam opiniões variadas sobre qual conjunto de leis é mais apropriado MonadPlus, uma das leis para as quais ninguém parece se opor é ...

mzero >>= f = mzero  -- Left zero

... que é precisamente a propriedade de emptydiscutirmos alguns parágrafos acima. A legalidade demmapMaybe segue imediatamente a partir da lei zero esquerda.

(Aliás, Control.Monadfornecemfilter :: MonadPlus m => (a -> Bool) -> m a -> m a , que corresponde ao filterque podemos definir usandommapMaybe .)

Em suma:

Mas essa implementação é sempre legal? Às vezes é legal (para alguma definição formal de "às vezes")?

Sim, a implementação é legal. Esta conclusão depende do emptyfato de estar vazio, como deveria, ou da mônada alternativa relevante após o zero à esquerdaMonadPlus lei , que se resume a praticamente a mesma coisa.

Vale ressaltar que Filterablenão é subsumido por MonadPlus, como podemos ilustrar com os seguintes contra-exemplos:

  • ZipList: filtrável, mas não uma mônada. A Filterableinstância é igual à das listas, mesmo que Alternativediferente.

  • Map: filtrável, mas nem mônada nem aplicativo. De fato, Mapnem sequer pode ser aplicável porque não há uma implementação sensata do pure. No entanto, tem o seu próprio empty.

  • MaybeT f: enquanto suas instâncias Monade Alternativeprecisam fser uma mônada, e uma emptydefinição isolada precisaria de pelo menos Applicative, a Filterableinstância requer apenas Functor f(tudo se torna filtrável se você Maybeinserir uma camada nela).

Parte três: vazia

Nesse ponto, ainda podemos nos perguntar o tamanho de um papel empty, ou nil, realmente desempenha Filterable. Não é um método de classe e, no entanto, a maioria das instâncias parece ter uma versão sensata dele por aí.

A única coisa que podemos ter certeza é que, se o tipo filtrável tiver habitantes, pelo menos um deles será uma estrutura vazia, porque sempre podemos pegar qualquer habitante e filtrar tudo:

chop :: Filterable f => f a -> f Void
chop = mapMaybe (const Nothing)

A existência de chop, embora não signifique que haverá um único nil valor vazio, ou que chopsempre dará o mesmo resultado. Considere, por exemplo, MaybeT IOcuja Filterableinstância possa ser pensada como uma maneira de censurar os resultados dos IOcálculos. A instância é perfeitamente lícita, embora choppossa produzir MaybeT IO Voidvalores distintos que carregam IOefeitos arbitrários .

Em uma nota final, de ter aludido a possibilidade de trabalhar com fortes functors monoidais, de modo que Alternativee Filterableestão ligados por fazer union/ partitione nil/ trivialisomorfismos. Ter unione partitioncomo inverso mútuo é concebível, mas bastante limitador, dado que union . partitiondescarta algumas informações sobre o arranjo dos elementos para uma grande parcela de instâncias. Quanto ao outro isomorfismo, trivial . nilé trivial, mas nil . trivialé interessante, pois implica que há apenas um único f Voidvalor, algo que vale para uma parcela considerável de Filterableinstâncias. Acontece que existe uma MonadPlusversão dessa condição. Se exigirmos isso, para qualquer u...

absurd <$> chop u = mzero

... e, em seguida, substitua o mmapMaybeda parte dois, obtemos:

absurd <$> chop u = mzero
absurd <$> mmapMaybe (const Nothing) u = mzero
mmapMaybe (fmap absurd . const Nothing) u = mzero
mmapMaybe (const Nothing) u = mzero
u >>= maybe mzero return . const Nothing = mzero
u >>= const mzero = mzero
u >> mzero = mzero

Essa propriedade é conhecida como lei zero correta MonadPlus, embora haja boas razões para contestar seu status como uma lei dessa classe específica.

duplicar
fonte
Obrigado por reservar um tempo para escrever isso! Ainda não tive tempo de analisar tudo isso, mas é justo dizer que o resumo é: "não sem leis adicionais relacionadas às instâncias Monade Alternative"?
Asad Saeeduddin 25/03
@AsadSaeeduddin Yup. MonadPlus(possivelmente visto através da caracterização quase semicondutora ) estabelece uma conexão entre Alternativee Monadque o "função monoidal sem adornos de caracterização Hask-com- (,)para Hask-com- Either" não oferece. De qualquer forma, ainda estou me perguntando se há algo mais profundo sobre como empty, que parece estranho à Filterabledefinição simples e ainda parece bastante adequado, aparece aqui.
duplode 25/03
emptyfaz parte da definição de Alternative. O Alternativee Filterablepode ser mais intimamente relacionado, exigindo que unionseja o inverso de partition(e vice-versa), e que trivialseja o inverso de nil(e vice-versa). Isso é chamado de "forte função monoidal".
Asad Saeeduddin 26/03
@AsadSaeeduddin Para algumas das Filterableinstâncias comuns , essa propriedade seria muito forte, pois partitionpode ser com perdas. Por exemplo, (union . partition) [L 7, R 2, L 1, R 6]é [L 7, L 1, R 2, R 6]. A parte trivial/ nilacabaria resumindo-se a ter apenas um f Voidvalor, o que parece mais favorável. Em MonadPlustermos, corresponde à lei do direito zero contestada m >> mzero = mzero, que, por exemplo, vale para listas, mas não para analisadores.
duplode 26/03
1
@AsadSaeeduddin Anexei uma seção destilando meus pensamentos empty. Esta é possivelmente a atualização final :)
duplode