Что такое индексированная монада?


Что это проиндексированных монады а мотивация для этой монады?

Я читал, что это помогает отслеживать побочные эффекты. Но подпись типа и документация никуда меня не ведут.

Что было бы примером того, как это может помочь отслеживать побочные эффекты (или любой другой действительный пример)?

5 91

5 ответов:

как всегда, терминология, которую используют люди, не совсем последовательна. Существует множество вдохновленных монадами, но, строго говоря, это не совсем понятия. Термин " индексированная монада "является одним из ряда (включая" монадиш "и" параметризованную монаду " (имя Atkey для них)) терминов, используемых для характеристики одного такого понятия. (Другое такое понятие, если вам интересно, - это "монада параметрического эффекта Кацуматы", индексированная моноидом, где возврат индексируется нейтрально и связывание накапливается в его индекс.)

прежде всего, давайте проверим видов.

IxMonad (m :: state -> state -> * -> *)

то есть, тип " вычисление "(или" действие", если вы предпочитаете, но я буду придерживаться" вычисление"), выглядит как

m before after value

здесь before, after :: state и value :: *. Идея состоит в том, чтобы захватить средства для безопасного взаимодействия с внешней системой, которая имеет некоторые предсказуемым понятие государства. Тип вычисления говорит вам, что состояние должно быть before он работает, что государство будет after он работает и (как с обычной монады над *), что типа values вычисление производит.

обычные биты и куски *-мудрый, как монада и state-мудрый, как играть в домино.

ireturn  ::  a -> m i i a    -- returning a pure value preserves state
ibind    ::  m i j a ->      -- we can go from i to j and get an a, thence
             (a -> m j k b)  -- we can go from j to k and get a b, therefore
             -> m i k b      -- we can indeed go from i to k and get a b

понятие "стрелка Клейсли" (функция, которая дает вычисление), таким образом, генерируется

a -> m i j b   -- values a in, b out; state transition i to j

и мы получаем состав

icomp :: IxMonad m => (b -> m j k c) -> (a -> m i j b) -> a -> m i k c
icomp f g = \ a -> ibind (g a) f

и, как всегда, законы точно гарантируют, что ireturn и icomp дайте нам категорию

      ireturn `icomp` g = g
      f `icomp` ireturn = f
(f `icomp` g) `icomp` h = f `icomp` (g `icomp` h)

или, в комедии поддельные C / Java / что угодно,

      g(); skip = g()
      skip; f() = f()
{h(); g()}; f() = h(); {g(); f()}

зачем? Моделировать "правила" взаимодействия. Например, вы не можете извлечь dvd-диск, если его нет в приводе, и вы не можете поместить dvd-диск в привод, если он уже есть. Так что

data DVDDrive :: Bool -> Bool -> * -> * where  -- Bool is "drive full?"
  DReturn :: a -> DVDDrive i i a
  DInsert :: DVD ->                   -- you have a DVD
             DVDDrive True k a ->     -- you know how to continue full
             DVDDrive False k a       -- so you can insert from empty
  DEject  :: (DVD ->                  -- once you receive a DVD
              DVDDrive False k a) ->  -- you know how to continue empty
             DVDDrive True k a        -- so you can eject when full

instance IxMonad DVDDrive where  -- put these methods where they need to go
  ireturn = DReturn              -- so this goes somewhere else
  ibind (DReturn a)     k  = k a
  ibind (DInsert dvd j) k  = DInsert dvd (ibind j k)
  ibind (DEject j)      k  = DEject j $ \ dvd -> ibind (j dvd) k

С этим на месте, мы можем определить "примитивные" команды

dInsert :: DVD -> DVDDrive False True ()
dInsert dvd = DInsert dvd $ DReturn ()

dEject :: DVDrive True False DVD
dEject = DEject $ \ dvd -> DReturn dvd

из которого собраны другие с ireturn и ibind. Теперь я могу писать (заимствование do-нотации)

discSwap :: DVD -> DVDDrive True True DVD
discSwap dvd = do dvd' <- dEject; dInsert dvd ; ireturn dvd'

но не физически невозможно

discSwap :: DVD -> DVDDrive True True DVD
discSwap dvd = do dInsert dvd; dEject      -- ouch!

кроме того, можно определить примитивные команды

data DVDCommand :: Bool -> Bool -> * -> * where
  InsertC  :: DVD -> DVDCommand False True ()
  EjectC   :: DVDCommand True False DVD

и затем создать экземпляр универсального шаблона

data CommandIxMonad :: (state -> state -> * -> *) ->
                        state -> state -> * -> * where
  CReturn  :: a -> CommandIxMonad c i i a
  (:?)     :: c i j a -> (a -> CommandIxMonad c j k b) ->
                CommandIxMonad c i k b

instance IxMonad (CommandIxMonad c) where
  ireturn = CReturn
  ibind (CReturn a) k  = k a
  ibind (c :? j)    k  = c :? \ a -> ibind (j a) k

фактически, мы сказали, что такое примитивные стрелки Клейсли (что такое "домино"), а затем построили над ними подходящее понятие "последовательность вычислений".

обратите внимание, что для каждой индексированной монады m, "без изменения диагонали"m i i - это монада, но в целом, m i j нет. Кроме того, значения не индексируются, но вычисления индексируются, поэтому индексированная монада-это не просто обычная идея монады, созданная для какой-либо другой категории.

теперь взгляните еще раз на тип стрелки Клейсли

a -> m i j b

мы знаем, что мы должны быть в состоянии i для начала, и мы прогнозируем, что любое продолжение будет начинаться от государства j. Мы много знаем об этой системе! Это не рискованная операция! Когда мы вставляем dvd в дисковод, он входит! Dvd-привод не получает никакого слова о том, в каком состоянии находится после каждой команды.

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

какой инструмент лучше?

type f :-> g = forall state. f state -> g state

class MonadIx (m :: (state -> *) -> (state -> *)) where
  returnIx    :: x :-> m x
  flipBindIx  :: (a :-> m b) -> (m a :-> m b)  -- tidier than bindIx

страшные печенье? Не совсем, по двум причинам. Во-первых, это больше похоже на то, что такое монада, потому что это и монада, но над (state -> *), а не *. Во-вторых, если вы посмотрите тип стрелы Клейсли,

a :-> m b   =   forall state. a state -> m b state

вы получаете тип вычислений с условиеa и постусловия b, как в старой доброй логике Хоара. Утверждения в логике программ заняли менее полувека, чтобы пересечь переписку Карри-Говарда и стать типами Хаскелла. Тип returnIx говорит:" Вы можете достичь любого постусловия, которое выполняется, просто ничего не делая", что является правилом логики Хоара для"пропуска". Соответствие композиция-это правило логики Хоара для ";".

давайте закончим, посмотрев на тип bindIx, вводя все кванторы.

bindIx :: forall i. m a i -> (forall j. a j -> m b j) -> m b i

эти forallS имеют противоположную полярность. Мы выбираем начальное состояние i, и вычисление, которое может начинаться с i, с постусловием a. Мир выбирает любое промежуточное состояние j его любит, но он должен дать нам доказательства того, что постусловие b держит, и от любого такого положения, мы можем снести дальше делать b удерживайте. Таким образом, в последовательности, мы можем достичь условия b государственной i. Отпустив нашу хватку на" после " состояний, мы можем моделировать непредсказуемой вычислений.

и IxMonad и MonadIx полезны. Обе модели валидности интерактивных вычислений относительно изменяющегося состояния предсказуемы и непредсказуемы соответственно. Предсказуемость ценна, когда вы можете ее получить, но непредсказуемость иногда является фактом жизни. Обнадеживающе, затем этот ответ дает некоторое представление о том, что такое индексированные монады, предсказывая, когда они начинают быть полезными и когда они останавливаются.

есть по крайней мере три способа определить индексированную монаду, которую я знаю.

я буду ссылаться на эти параметры как индексированные монады à la X, где X колеблется над компьютерными учеными Бобом Атки, Конором Макбрайдом и Домиником Орчардом, как я склонен думать о них. Части этих конструкций имеют гораздо более длинную историю и более приятные интерпретации через теорию категорий, но я впервые узнал о них, связанных с этими именами, и я пытаюсь чтобы сохранить этот ответ от получения слишком эзотерика.

Atkey

стиль индексированной монады Боба Атки должен работать с 2 дополнительными параметрами, чтобы иметь дело с индексом монады.

С этим вы получаете определения, которые люди бросили в других ответах:

class IMonad m where
  ireturn  ::  a -> m i i a
  ibind    ::  m i j a -> (a -> m j k b) -> m i k b

мы также можем определить индексированные комонады à la Atkey. Я на самом деле получаю много пробега из тех на lens кода.

Макбрайд

следующая форма индексированной монады-это определение Конора Макбрайда из его статьи "Клейсли стрелы возмутительной Фортуны". Вместо этого он использует один параметр для индекса. Это делает индексированное определение монады довольно умной формой.

если мы определим естественное преобразование с использованием параметричности следующим образом

type a ~> b = forall i. a i -> b i 

тогда мы можем записать определение Макбрайда как

class IMonad m where
  ireturn :: a ~> m a
  ibind :: (a ~> m b) -> (m a ~> m b)

это выглядит совсем иначе, чем у Atkey, но это больше похоже на нормальную монаду, вместо того, чтобы строить монаду на (m :: * -> *), мы строим его на (m :: (k -> *) -> (k -> *).

интересно, что вы можете фактически восстановить стиль индексированной монады Atkey от Mcbride's, используя умный тип данных, который McBride в своем неподражаемом стиле выбирает, чтобы сказать, что вы должны читать как "AT key".

data (:=) :: a i j where
   V :: a -> (a := i) i

теперь вы можете решить, что

ireturn :: IMonad m => (a := j) ~> m (a := j)

что расширяет к

ireturn :: IMonad m => (a := j) i -> m (a := j) i

может быть вызван только тогда, когда j = i, а затем тщательное чтение ibind может вернуть вас так же, как Atkey's ibind. Вам нужно обойти эти (:=) структуры данных, но они восстанавливают мощность презентации Atkey.

С другой стороны, презентация Atkey недостаточно сильна, чтобы восстановить все варианты использования версии McBride. Власть была строго завоевана.

еще одна приятная вещь заключается в том, что индексированная монада Макбрайда явно является монада, это просто монада на другой категории функторов. Он работает над эндофункторами в категории функторов от (k -> *) до (k -> *) а не категория функторов из * до *.

веселое упражнение является выяснение того, как сделать Макбрайд в Atkey преобразования для индексированных comonads. Я лично использую тип данных "At" для конструкции "at key" в статье Макбрайда. Я действительно подошел к Бобу Атки на ICFP 2013 и упомянул, что я бы вывернул его наизнанку и превратил в"пальто". Он казался явно встревоженным. В моей голове эта фраза звучала лучше. =)

сад

http://www.cl.cam.ac.uk/~dao29 / ixmonad/ixmonad-fita14. pdf

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

blueToRed  :: State S ()
blueToBlue :: State S ()

foo :: State S ()
foo = do blueToRed
         blueToBlue

запуск Ошибка времени выполнения, так как второе действие ожидает синий государство. Мы хотели бы предотвратить это статически. Индексированная монада выполняет эту задачу:

data Red
data Blue

-- assume a new indexed State monad
blueToRed  :: State S Blue Red  ()
blueToBlue :: State S Blue Blue ()

foo :: State S ?? ?? ()
foo = blueToRed `ibind` \_ ->
      blueToBlue          -- type error

тип ошибки срабатывает, потому что второй индекс blueToRed (Red) отличается от первого индексом blueToBlue (Blue).

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

data State old new a = State (old -> (new, a))

вы можете использовать, чтобы построить государство, которое является статически неоднородных стек. Операции будут иметь тип

push :: a -> State old (a,old) ()
pop  :: State (a,new) new a

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

openFile :: IO any FilesAccessed ()
newIORef :: a -> IO any any (IORef a)
-- no operation of type :: IO any NoAccess _

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

тогда как" стандартное " монадическое значение имеет тип Monad m => m a значение в индексированной монаде будет IndexedMonad m => m i j a здесь i и j являются индексными типами, так что i - Это тип индекса в начале монадического вычисления и j В конце вычислений. В некотором смысле, вы можете думать о i как своего рода тип ввода и j как тип вывода.

используя State в качестве примера, вычисление состояния State s a поддерживает состояние типа s на протяжении всего вычисления и возвращает результат типа a. Индексированная версия,IndexedState i j a, является вычислением с сохранением состояния, где состояние может измениться на другой тип во время вычисления. Начальное состояние имеет вид i и состояние и конец вычисления имеет тип j.

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

возможно, важно посмотреть, как индексирование используется в зависимых типах (например, в agda). Это может объяснить, как индексирование помогает в целом, а затем перевести этот опыт на монады.

индексирование позволяет устанавливать связи между отдельными экземплярами типов. Затем вы можете рассуждать о некоторых значениях, чтобы установить, выполняется ли эта связь.

например (в agda) вы можете указать, что некоторые натуральные числа связаны с _<_ и тип говорит, какие номера они. Затем вы можете потребовать, чтобы какая-то функция получила свидетеля, который m < n, потому что только тогда эта функция работает корректно и без предоставления такого свидетеля, программа не скомпилируется.

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

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