Как называется эта особая структура функторов?

Question

Предположим, что F - аппликативный функтор с дополнительными законами (с синтаксисом Haskell):

1. pure (const ()) <*> m === pure ()
2. pure (\a b -> (a, b)) <*> m <*> n === pure (\a b -> (b, a)) <*> n <*> m
3. pure (\a b -> (a, b)) <*> m <*> m === pure (\a -> (a, a)) <*> m

Как называется структура, если мы опускаем (3.)?

Где я могу найти больше информации об этих законах / структурах?

Комментарии к комментариям

Функторы, удовлетворяющие (2.), часто называют коммутативными.

Вопрос в том, подразумевает ли (1.) (2.) и как эти структуры можно описать. Меня особенно интересуют структуры, которые удовлетворяют (1-2.), Но не (3.)

Примеры:

• Читательская монада удовлетворяет (1-3.)
• Писательская монада на коммутативном моноиде удовлетворяет только (2.)
• Монада F приведенный ниже удовлетворяет (1-2.), но не (3.)

Значение F:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE RankNTypes #-}
import Control.Monad.State

newtype X i = X Integer deriving (Eq)

newtype F i a = F (State Integer a) deriving (Monad)

new :: F i (X i)
new = F $ modify (+1) >> gets X

evalF :: (forall i . F i a) -> a
evalF (F m) = evalState m 0

Мы экспортируем только типы X, F, new, evalFи случаи.

Убедитесь, что выполняется следующее:

• liftM (const ()) m === return ()
• liftM2 (\a b -> (a, b)) m n === liftM2 (\a b -> (b, a)) n m

С другой стороны, liftM2 (,) new new не может быть заменено liftM (\a -> (a,a)) new:

test = evalF (liftM (uncurry (==)) $ liftM2 (,) new new)
    /= evalF (liftM (uncurry (==)) $ liftM (\a -> (a,a)) new)

Комментарии к ответу CA McCann

У меня есть набросок доказательства того, что (1.) подразумевает (2.)

pure (,) <*> m <*> n

знак равно

pure (const id) <*> pure () <*> (pure (,) <*> m <*> n)

знак равно

pure (const id) <*> (pure (const ()) <*> n) <*> (pure (,) <*> m <*> n)

знак равно

pure (.) <*> pure (const id) <*> pure (const ()) <*> n <*> (pure (,) <*> m <*> n)

знак равно

pure const <*> n <*> (pure (,) <*> m <*> n)

=... =

pure (\_ a b -> (a, b)) <*> n <*> m <*> n

= см. ниже =

pure (\b a _ -> (a, b)) <*> n <*> m <*> n

=... =

pure (\b a -> (a, b)) <*> n <*> m

знак равно

pure (flip (,)) <*> n <*> m

наблюдение

Для недостающей части сначала рассмотрим

pure (\_ _ b -> b) <*> n <*> m <*> n

=... =

pure (\_ b -> b) <*> n <*> n

=... =

pure (\b -> b) <*> n

=... =

pure (\b _ -> b) <*> n <*> n

=... =

pure (\b _ _ -> b) <*> n <*> m <*> n

лемма

Мы используем следующую лемму:

pure f1 <*> m  ===   pure g1 <*> m
pure f2 <*> m  ===   pure g2 <*> m

подразумевает

pure (\x -> (f1 x, f2 x)) m  ===  pure (\x -> (g1 x, g2 x)) m

Я мог доказать эту лемму только косвенно.

Недостающая часть

С помощью этой леммы и первого наблюдения мы можем доказать

pure (\_ a b -> (a, b)) <*> n <*> m <*> n

знак равно

pure (\b a _ -> (a, b)) <*> n <*> m <*> n

которая была недостающей частью.

Вопросы

Это уже где-то доказано (возможно, в обобщенном виде)?

замечания

(1.) влечет (2.), но в остальном (1-3.) Независимы.

Чтобы доказать это, нам нужно еще два примера:

• Монада G приведенное ниже удовлетворяет (3.), но не (1-2.)
• Монада G' приведенный ниже удовлетворяет (2-3.), но не (1.)

Значение G:

newtype G a = G (State Bool a) deriving (Monad)

putTrue :: G ()
putTrue = G $ put True

getBool :: G Bool
getBool = G get

evalG :: G a -> a
evalG (G m) = evalState m False

Мы экспортируем только тип G, putTrue, getBool, evalGи Monad пример.

Определение G' похоже на определение G со следующими отличиями:

Мы определяем и экспортируем execG:

execG :: G' a -> Bool
execG (G m) = execState m False

Мы не экспортируем getBool,

Answer 1

Ваш первый закон - очень строгое требование; это означает, что функтор не может иметь никакой выделенной "формы", независимой от параметрической части. Это исключает любой функтор, который содержит дополнительные значения (State, Writerи т. д.), а также любой функтор, использующий типы сумм (Either, []и т. д.). Так что это ограничивает нас такими вещами, как контейнеры фиксированного размера.

Ваш второй закон требует коммутативности, что означает, что порядок вложения (то есть состав функтора) не имеет значения. На самом деле это может подразумеваться из первого закона, поскольку мы уже знаем, что функтор не может содержать никакой информации, кроме параметрических значений, и вам явно требуется сохранить ее здесь.

Ваш третий закон требует, чтобы функтор также был идемпотентом, что означает, что вложение чего-либо в себя с помощью fmap эквивалентно самому себе. Это, вероятно, подразумевает, что если функтор также является монадой, join подразумевает своего рода "взятие диагонали". В основном это означает, что liftA2 (,) должен вести себя как zip, не декартово произведение.

Второе и третье вместе означают, что как бы много "примитивов" ни было у функтора, любая композиция эквивалентна объединению не более одного из каждого примитива в любом порядке. И первое подразумевает, что если вы выбрасываете параметрическую информацию, любая комбинация примитивов такая же, как и вообще отсутствие использования.

Итак, я думаю, что у вас есть класс функторов, изоморфныйReader, То есть функторы, где f a описывает значения типа a индексируется некоторым другим типом, таким как подмножество натуральных чисел (для контейнеров фиксированного размера) или произвольным типом (как с Reader).

К сожалению, я не уверен, как убедительно доказать большинство вышесказанного.