Действительно ли операционная изоморфна свободной монаде?

Question

Доказательств

В этом сообщении Tekmo подчеркивает, что мы можем доказать, что ExitSuccess выходит, потому что (я полагаю) это как Const функтор для этого конструктора (он не несет x так fmap ведет себя как const).

С операционным пакетом Tekmo's TeletypeF может быть переведено что-то вроде этого:

data TeletypeI a where
    PutStrLn :: String -> TeletypeI ()
    GetLine :: TeletypeI String
    ExitSuccess :: TeletypeI ()

Я читал, что операционная изоморфна свободной монаде, но можем ли мы доказать здесь, что ExitSuccess выходит? Мне кажется, что он страдает от той же проблемы, что и exitSuccess :: IO () и, в частности, если бы мы должны были написать для него интерпретатор, нам нужно было бы написать его так, как если бы он не выходил:

eval (ExitSuccess :>>= _) = exitSuccess

Сравните с бесплатной версией монады, которая не содержит шаблонов:

run (Free ExitSuccess) = exitSuccess

Лень

В учебнике " Операционная монада" Апфельмус упоминает недостаток:

Монада состояний, представленная как s -> (a,s), может справиться с некоторыми бесконечными программами, такими как

evalState (sequence . repeat . state $ \s -> (s,s+1)) 0

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

Это верно и для свободных монад?

Answer 1

(Позвольте мне получить главный приз, смело комбинируя предыдущие ответы.;-))

Ключевое наблюдение таково: докажите, что именно? Формулировка с точки зрения Free TeletypeF позволяет доказать следующее:

Каждый переводчик для программ типа Free TeletypeF a должен выйти, когда он сталкивается с ExitSuccess инструкция. Другими словами, мы автоматически получаем алгебраический закон

 interpret (exitSuccess >>= k) = interpret exitSuccess

Таким образом Free Монада на самом деле позволяет запекать определенные алгебраические законы в тип.

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

Конечно, вы можете доказать, что любой конкретный интерпретатор удовлетворяет закону, например, потому что он использует сопоставление с шаблоном подстановки. Sjoerd Visscher отмечает, что вы также можете применить это в системе типов, изменив тип возвращаемого значения ExitSuccess в Void, Тем не менее, это не работает для других законов, которые могут быть превращены в свободные монады, например, закон распределения для mplus инструкция.

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

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

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

Answer 2

Ответ - да, но только если вы используете другой перевод TeletypeF:

data TeletypeI a where
    PutStrLn :: String -> TeletypeI ()
    GetLine :: TeletypeI String
    ExitSuccess :: TeletypeI Void

Аргумент TeletypeI это то, что операция будет / должна предоставить остальной части программы. Это тип аргумента продолжения k в

eval (ExitSuccess :>>= k) = ...

Так как нет значений типа Voidмы можем быть уверены, что k никогда не будет называться. (Как всегда, мы должны игнорировать undefined Вот.)

Эквивалентный тип:

data TeletypeI a where
    PutStrLn :: String -> TeletypeI ()
    GetLine :: TeletypeI String
    ExitSuccess :: TeletypeI a

Теперь мы должны предоставить значение k это соответствует любому типу, и мы не можем этого сделать. Это может быть более практичным, так как singleton ExitSuccess теперь имеет гибкий тип Program TeletypeI a,

Так же, exitSuccess можно исправить, указав тип IO Void, или же IO a,

Answer 3

Ответ - нет, вы не можете доказать, что операционная программа игнорирует остальную часть программы на exitSuccess, контрастировать TeletypeI с TeletypeF чтобы понять почему. Я перепишу TeletypeF в нотации GADT для более простого сравнения

data TeletypeF x where                     | data TeletypeI x where
  PutStrLn :: String -> x  -> TeletypeF x  |   PutStrLn :: String -> TeletypeI ()
  GetLine :: (String -> x) -> TeletypeF x  |   GetLine :: TeletypeI String
  ExitSuccess ::              TeletypeF x  |   ExitSuccess :: TeletypeI ()

С помощью TeletypeFМы можем создавать актуальные программы прямо сейчас:

GetLine (\str -> PutStrLn (map toUpper str) ExitSuccess)

TeletypeI не имеет способа ссылаться на "остальную часть программы" так же, как TeletypeF делает.

-- TeletypeF:
GetLine (\str -> "rest of program" goes here)
-- or
PutStrLn someString ("rest of program" goes here)
-- or
ExitSuccess -- there is no "rest of program" slot provided

поскольку TeletypeI не хватает этой информации "остальной части программы", вы больше не можете получить какие-либо знания, когда вы сталкиваетесь ExitSuccess,

-- TeletypeI
PutStrLn someString -- no information about "rest of program"
-- or
GetLine -- no information about "rest of program"
-- or
ExitSuccess -- no information about "rest of program"

То, что допускается как "остальная часть программы", полностью зависит от Program тип, который ничего не знает о наборе команд, к которому он применяется. Это просто позволяет вам связывать инструкции вместе и завершать через Return,