Возможна ли фильтрация всех альтернативных монад?

Категория множеств является как декартовой моноидальной, так и кокартовой моноидальной. Типы канонических изоморфизмов, свидетельствующих об этих двух моноидальных структурах, перечислены ниже:

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

Для целей этого вопроса я определяю Alternative как слабый моноидальный функтор от Hask с тензором Either до Hask с тензором (,) (и не более):

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

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

Это те же законы, что и для слабого моноидального функтора.

Ассоциативность:

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

Левый блок:

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

Правый блок:

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

Вот как восстановить более знакомые операции для класса типов Alternative в терминах карт когерентности нестрогого моноидального кодирования функторов:

(<|>) :: 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 ()

Я определяю функторы Filterable как моноидальные функторы oplax от Hask под тензором Either до Hask под тензором (,):

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 ()

Имея в качестве своих законов только обратные нестрогие моноидальные законы функторов:

Ассоциативность:

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

Левый блок:

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

Правый блок:

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

Определение стандартных функций filter-y, таких как mapMaybe и filter в терминах кодирования моноидального функтора oplax, оставлено в качестве упражнения для заинтересованного читателя:

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

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

Вопрос в следующем: каждый Alternative Monad также Filterable?

Мы можем ввести тетрис как путь к реализации:

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

Но всегда ли такая реализация законна? Законно ли это иногда (для некоторого формального определения «иногда»)? Доказательства, контрпримеры и / или неформальные аргументы были бы очень полезны. Спасибо.

Asad Saeeduddin 18.03.2020 источник

comment

Лично я был бы очень удивлен, если бы он всегда действовал. Конечно, иногда действителен в том смысле, что существуют функторы, для которых он действителен, но я склонен сомневаться, что это особенно интересный класс. - dfeuer 18.03.2020

comment

@dfeuer Есть ли у вас контрпримеры, для которых это явно не верно? Возможно, это будет поучительно. - Asad Saeeduddin 18.03.2020

comment

Я почти уверен, что это всегда законный пример, просто из-за развертывания определений и некоторой тривиальной переписывания (таким образом, предполагая, что законы Filterable довольно слабы). @AsadSaeeduddin Подумайте о том, чтобы научиться некоторым интерактивным навыкам доказательства теорем, чтобы вы могли расширить возможности использования, а не свой умственный склад ума, на доказательства! - Li-yao Xia 18.03.2020

Ответы (1)

arrow_upward
3
arrow_downward

Вот аргумент, который в целом поддерживает вашу прекрасную идею.

Часть первая: карта

Мой план здесь состоит в том, чтобы переформулировать проблему в терминах mapMaybe, надеясь, что это приведет нас к более знакомой теме. Для этого я воспользуюсь несколькими служебными функциями Either-жонглирования:

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

(Первые три имени я взял из повторно установить, а четвертый - от errors. Кстати, errors предлагает maybeToRight и rightToMaybe как note и hush соответственно в _ 8_.)

Как вы отметили, mapMaybe можно определить в терминах partition:

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

Важно отметить, что мы также можем пойти другим путем:

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

Это говорит о том, что имеет смысл изменить ваши законы с точки зрения mapMaybe. Благодаря законам об идентичности это дает нам отличный повод полностью забыть о trivial:

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

Что касается ассоциативности, мы можем использовать rightToMaybe и leftToMaybe, чтобы разделить закон на три уравнения, по одному для каждого компонента, который мы получаем из последовательных разделов:

-- 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]

Параметричность означает, что mapMaybe не зависит от Either значений, с которыми мы здесь имеем дело. Если это так, мы можем использовать наш небольшой арсенал Either изоморфизмов, чтобы перемешать вещи и показать, что [I] эквивалентно [II], а [III] эквивалентно [V]. Теперь мы свелись к трем уравнениям:

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]

Параметричность позволяет нам проглотить fmap в [I]:

mapMaybe (rightToMaybe . bwd elunit) = id

Однако это просто ...

mapMaybe Just = id

... что эквивалентно закону сохранения / идентичности из Filterable пользователя witherable:

mapMaybe (Just . f) = fmap f

У этого Filterable также есть закон композиции:

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

Можем ли мы также вывести это из наших законов? Начнем с [III] и еще раз заставим параметричность делать свое дело. Этот посложнее, поэтому я запишу его полностью:

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

В обратном направлении:

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

(Примечание: хотя maybeToRight () . rightToMaybe :: Either a b -> Either () b не id, в выводе выше левые значения в любом случае будут отброшены, поэтому будет справедливо вычеркнуть его, как если бы это было id.)

Таким образом, [III] эквивалентен закону композиции Filterable объекта witherable.

На этом этапе мы можем использовать закон композиции для работы с [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.

Этого достаточно, чтобы показать, что ваш класс соответствует устоявшейся формулировке Filterable, что является очень хорошим результатом. Вот краткое изложение законов:

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

Как отмечается в witherable документации, это законы функторов для функтора от Kleisli Maybe до Hask.

Часть вторая: альтернатива и монада

Теперь мы можем ответить на ваш вопрос об альтернативных монадах. Предложенная вами реализация partition была:

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

Следуя своему более широкому плану, я перейду к mapMaybe презентации:

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 =<<)

Итак, мы можем определить:

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

Или, без точки написания:

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

Несколькими абзацами выше я заметил, что Filterable законы гласят, что mapMaybe является отображением морфизма функтора из Kleisli Maybe в Hask. Поскольку композиция функторов является функтором, а (=<<) является отображением морфизма функтора из Клейсли f в Hask, (maybe empty return .) является отображением морфизма функтора из Kleisli Maybe до Kleisli f достаточно, чтобы mapMaybeAM было законным. Соответствующие законы функторов:

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

Этот закон идентичности выполняется, поэтому давайте сосредоточимся на композиционном:

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.

Следовательно, mapMaybeAM законно тогда и только тогда, когда maybe empty return . g =<< empty = empty для любого g. Теперь, если empty определен как absurd <$> nil (), как вы сделали здесь, мы можем доказать, что f =<< empty = empty для любого 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

Интуитивно понятно, что если empty действительно пусто (как и должно быть, учитывая определение, которое мы здесь используем), не будет значений для f, к которым можно применить, и поэтому f =<< empty не может привести ни к чему, кроме empty.

Другой подход здесь был бы во взаимодействии классов Alternative и Monad. Как оказалось, существует класс для альтернативных монад: _ 66_. Соответственно, рестайлинговый mapMaybe может выглядеть так:

-- 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

Хотя существуют разные мнения о том, какой свод законов наиболее подходит для MonadPlus, один из законов, против которого, кажется, никто не возражает, это ...

mzero >>= f = mzero  -- Left zero

... что в точности является свойством empty, которое мы обсуждали несколькими абзацами выше. Законность mmapMaybe следует непосредственно из закона левого нуля.

(Между прочим, _ 73_ предоставляет mfilter :: MonadPlus m => (a -> Bool) -> m a -> m a, который соответствует filter, который мы можем определить с помощью mmapMaybe.)

В итоге:

Но всегда ли такая реализация законна? Законно ли это иногда (для некоторого формального определения «иногда»)?

Да, реализация законна. Этот вывод зависит от того, что empty действительно пусто, как и должно быть, или от соответствующей альтернативной монады, соответствующей закону левого нуля MonadPlus, который сводится примерно к одному и тому же.

Стоит подчеркнуть, что Filterable не входит в MonadPlus, что мы можем проиллюстрировать следующими контрпримерами:

ZipList: фильтруемый, но не монада. Экземпляр Filterable такой же, как и экземпляр для списков, хотя экземпляр Alternative отличается.
Map: фильтруемый, но ни монада, ни аппликатив. Фактически, Map не может быть даже аппликативным, потому что не существует разумной реализации pure. Однако у него есть свой empty.
MaybeT f: в то время как его экземпляры Monad и Alternative требуют, чтобы f был монадой, а для изолированного empty определения потребуется как минимум Applicative, для экземпляра Filterable требуется только Functor f (все становится фильтруемым, если вы вставите в него слой Maybe).

Часть третья: пусто

На этом этапе можно все еще задаться вопросом, насколько большую роль empty или nil действительно играет в Filterable. Это не метод класса, и все же в большинстве случаев, похоже, есть разумная его версия.

Единственное, в чем мы можем быть уверены, это то, что если фильтруемый тип вообще имеет жителей, по крайней мере одно из них будет пустой структурой, потому что мы всегда можем взять любого жителя и отфильтровать все:

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

Однако наличие chop не означает, что будет одиночное nil пустое значение или что chop всегда будет выдавать один и тот же результат. Рассмотрим, например, MaybeT IO, чей Filterable экземпляр можно рассматривать как способ цензуры результатов IO вычислений. Экземпляр является совершенно законным, хотя chop может давать различные MaybeT IO Void значения, которые несут произвольные IO эффекты.

В заключение, вы упомянули возможность работы с сильные моноидальные функторы, так что Alternative и Filterable связаны путем создания изоморфизмов _112 _ / _ 113_ и _114 _ / _ 115_. Использование union и partition в качестве взаимных инверсий возможно, но довольно ограничивает, учитывая, что union . partition отбрасывает некоторую информацию о расположении элементов для большой доли экземпляров. Что касается другого изоморфизма, trivial . nil тривиален, но nil . trivial интересен тем, что подразумевает, что существует только одно значение f Void, что справедливо для значительной части Filterable экземпляров. Бывает, что есть MonadPlus версия этого условия. Если мы того потребуем, для любого _124 _...

absurd <$> chop u = mzero

... а затем подставляем mmapMaybe из второй части, получаем:

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

Это свойство известно как закон нулевого права MonadPlus, хотя есть веские причины оспорить его статус закона. этого конкретного класса.

duplode 22.03.2020

comment

Спасибо, что нашли время написать об этом! У меня еще не было времени пройти через все это, но будет справедливо сказать, что краткое изложение таково: разве без дополнительных законов, касающихся случаев Monad и Alternative? - Asad Saeeduddin; 25.03.2020

comment

@AsadSaeeduddin Ага. MonadPlus (возможно, видно через почти полукольцевую характеристику) устанавливает связь между Alternative и Monad, которую не предлагает простой моноидальный функтор от Hask-with-(,) к Hask-with-Either характеризации. В любом случае, мне все еще интересно, есть ли что-то более глубокое в том, как empty, который выглядит чуждым голому Filterable определению, но все же кажется вполне подходящим, появляется здесь. - duplode; 25.03.2020

comment

empty является частью определения Alternative. Alternative и Filterable могут быть более тесно связаны, если потребовать, чтобы union был инверсией partition (и наоборот), а trivial был обратным nil (и наоборот). Это то, что называется сильным моноидальным функтором. - Asad Saeeduddin; 26.03.2020

comment

@AsadSaeeduddin Для некоторых распространенных экземпляров Filterable это свойство было бы слишком сильным, поскольку partition может быть с потерями. Например, (union . partition) [L 7, R 2, L 1, R 6] это [L 7, L 1, R 2, R 6]. Часть _5 _ / _ 6_ в конечном итоге сводится к тому, чтобы иметь только одно значение f Void, что кажется более приемлемым. В терминах MonadPlus это соответствует закону оспариваемого правого нуля m >> mzero = mzero, который, например, справедлив для списков, но не для синтаксических анализаторов. - duplode; 26.03.2020

comment

Да, не каждый фильтруемый обладает этим свойством, точно так же, как не каждый слабый моноидальный функтор является сильным моноидальным. Вот почему имеет смысл использовать обе концепции. - Asad Saeeduddin; 26.03.2020

comment

@AsadSaeeduddin То, что я упустил в первый раз: если empty = absurd <$> nil (), то мы можем доказать f =<< empty = empty для любого f, что означает, что нам не обязательно полагаться на MonadPlus закон левого нуля здесь. - duplode; 29.03.2020

comment

@AsadSaeeduddin Я добавил раздел, в котором изложены мои мысли о empty. Возможно, это последнее обновление :) - duplode; 10.04.2020

comment

Благодарим за терпение и все идеи. Я начал пытаться следовать вашим рассуждениям, скопировав их в Agda, я приму ответ, как только это будет сделано. - Asad Saeeduddin; 10.04.2020

Возможна ли фильтрация всех альтернативных монад?

Ответы (1)

Часть первая: карта

Часть вторая: альтернатива и монада

Часть третья: пусто

Похожие вопросы