是真的运作同构于一个免费的单子?(Is operational really isomorphic

2019-08-06 08:43发布

证明

在这个博客中,Tekmo使得我们可以证明一点ExitSuccess退出,因为(我相信)它就像Const仿函数为构造器(它不携带x所以fmap行为就像const )。

随着业务包,Tekmo的TeletypeF可能被翻译是这样的:

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

我读过的操作是同构的一个免费的单子,但我们可以在这里,证明ExitSuccess退出? 在我看来,它从完全一样的问题,因为遭受exitSuccess :: IO ()做,特别是如果我们写了一个解释,我们就需要把它写这样,如果它没有退出:

eval (ExitSuccess :>>= _) = exitSuccess

相较于免费的单子版本,它不涉及任何模式通配符:

run (Free ExitSuccess) = exitSuccess

怠惰

在操作单子教程 apfelmus提到一个缺点:

表示为s的状态单子 - >(A,S)可以与一些无限方案像应付

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

而指令方式的列表没有有史以来处理,由于只有最后的返回指令可以返回值的希望。

这是真的免费单子呢?

Answer 1:

(请允许我大胆地结合以前的答案舀大奖。;-))

关键的观察是:证明什么 ? 在条款的制定Free TeletypeF使我们能够证明下列内容:

类型的节目每一个解释 Free TeletypeF a当它遇到了必须退出ExitSuccess指令。 换句话说,我们自动获得的代数法

  interpret (exitSuccess >>= k) = interpret exitSuccess 

因此, Free单子实际上允许将特定的代数法律烤成的类型。

相比之下,操作方法不限制的语义ExitSuccess ,也没有相关的法律代数,涉及到每一个解释。 这是可能遇到此指令时写解释说出口,但它也可以编写解释说没有。

当然,你可以证明,任何特定的解释器通过检查符合法律规定,例如,因为它使用通配符模式匹配。 Sjoerd Visscher的观察,你可以在类型系统中通过改变返回类型也执行这一ExitSuccessVoid 。 然而,这并不对可用于烤成免费的单子,比如分配律其他法律工作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 。 对比TeletypeITeletypeF明白。 我会改写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



文章来源: Is operational really isomorphic to a free monad?