Является ли каждая альтернативная монада фильтруемой? - PullRequest
Новая
       115

Является ли каждая альтернативная монада фильтруемой?

8 голосов
/ 18 марта 2020

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

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 тензор к Хаску при тензоре (,) (и не более): 

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

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

l aws как раз для слабого моноидального функтора.

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

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

Имея для своего l aws только обратный слабый моноидальный функтор l aws:

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

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)

Определение стандартной функции фильтра Например, 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)

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

1 Ответ

3 голосов
/ 22 марта 2020

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

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

Мой план состоит в том, чтобы переосмыслить проблему в терминах 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

(первые три имени я взял из relude и четвертое из ошибок . Кстати, ошибок предлагает maybeToRight и rightToMaybe как note и hush соответственно, в Control.Error.Util.)

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

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

Важно, что мы также можем go другим способом около: 

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

Это говорит о том, что имеет смысл пересчитать ваш l aws с точки зрения mapMaybe. Имея тождество l aws, это дает нам отличный повод полностью забыть о 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 является c относительно значений 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: 

mapMaybe (Just . f) = fmap f

То Filterable также имеет составной закон: 

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

Можем ли мы вывести его из нашего l aws? Давайте начнем с [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] эквивалентен закону композиции witherable 's Filterable.

На данный момент мы можем использовать закон композиции для работы с [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, что является очень хорошим результатом. Вот резюме l aws: 

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

Как отмечают увядшие документы, это функтор l aws для функтора из Kleisli Maybe to 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 l aws говорит, что mapMaybe - это отображение морфизма функтора от Клейсли Может до Хаск . Поскольку композиция функторов является функтором, а (=<<) является отображением морфизма функтора из Kleisli f в Hask , (maybe empty return .) является отображением морфизма функтора из Клейсли Может быть до Клейсли f достаточно для mapMaybeAM, чтобы быть законным. Соответствующий функтор l aws: 

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. Как это бывает, есть класс для альтернативных монад: MonadPlus. Соответственно, рестайлинговый 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

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

mzero >>= f = mzero  -- Left zero

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

(Кстати, Control.Monad обеспечивает 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 были связаны между собой изоморфизмами union / partition и nil / trivial. Наличие union и partition в качестве взаимных инверсий возможно, но довольно ограниченно, учитывая, что union . partition отбрасывает некоторую информацию о расположении элементов для большой доли экземпляров. Что касается другого изоморфизма, trivial . nil является тривиальным, но nil . trivial интересен тем, что подразумевает, что существует только одно значение f Void, то есть то, что справедливо для значительной доли экземпляров Filterable. Бывает, что существует версия MonadPlus этого условия. Если мы потребуем это для любого u ... 

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, хотя есть веские причины оспаривать его статус как закона этого конкретного класса.

...