箭头完全等同于应用函子？

Question

根据着名的论文,成语是不经意的,箭头是一丝不苟的,monad是混杂的,箭头的表达能力(没有任何额外的类型)应该在应用函子和monad之间严格地说:monads相当于ArrowApply,并且Applicative应该等同于纸张称为"静态箭头".但是,我不清楚这种"静态"意味着什么限制.

玩弄的问题有三种类型类,我是能够建立应用性函子和箭头,这是我在与知名等价的上下文中呈现之间的等价Monad和ArrowApply.这种结构是否正确？(我在厌倦之前证明了大部分的箭法).这是不是意味着Arrow并且Applicative完全一样？

{-# LANGUAGE TupleSections, NoImplicitPrelude #-}
import Prelude (($), const, uncurry)

-- In the red corner, we have arrows, from the land of * -> * -> *
import Control.Category
import Control.Arrow hiding (Kleisli)

-- In the blue corner, we have applicative functors and monads,
-- the pride of * -> *
import Control.Applicative
import Control.Monad

-- Recall the well-known result that every monad yields an ArrowApply:
newtype Kleisli m a b = Kleisli{ runKleisli :: a -> m b}

instance (Monad m) => Category (Kleisli m) where
    id = Kleisli return
    Kleisli g . Kleisli f = Kleisli $ g <=< f

instance (Monad m) => Arrow (Kleisli m) where
    arr = Kleisli . (return .)
    first (Kleisli f) = Kleisli $ \(x, y) -> liftM (,y) (f x)

instance (Monad m) => ArrowApply (Kleisli m) where
    app = Kleisli $ \(Kleisli f, x) -> f x

-- Every arrow arr can be turned into an applicative functor
-- for any choice of origin o
newtype Arrplicative arr o a = Arrplicative{ runArrplicative :: arr o a }

instance (Arrow arr) => Functor (Arrplicative arr o) where
    fmap f = Arrplicative . (arr f .) . runArrplicative

instance (Arrow arr) => Applicative (Arrplicative arr o) where
    pure = Arrplicative . arr . const

    Arrplicative af <*> Arrplicative ax = Arrplicative $
        arr (uncurry ($)) . (af &&& ax)

-- Arrplicatives over ArrowApply are monads, even
instance (ArrowApply arr) => Monad (Arrplicative arr o) where
    return = pure
    Arrplicative ax >>= f =
        Arrplicative $ (ax >>> arr (runArrplicative . f)) &&& id >>> app

-- Every applicative functor f can be turned into an arrow??
newtype Applicarrow f a b = Applicarrow{ runApplicarrow :: f (a -> b) }

instance (Applicative f) => Category (Applicarrow f) where
    id = Applicarrow $ pure id
    Applicarrow g . Applicarrow f = Applicarrow $ (.) <$> g <*> f

instance (Applicative f) => Arrow (Applicarrow f) where
    arr = Applicarrow . pure
    first (Applicarrow f) = Applicarrow $ first <$> f

Answer 1

每个应用程序产生一个箭头,每个箭头产生一个应用程序,但它们不相等.如果你有一个箭头arr和一个态射,arr a b那么就不会产生一个arr o (a \to b)复制其功能的态射.因此,如果您通过应用程序往返,则会丢失一些功能.

应用是幺正的仿函数.箭头也是类别,或类似地,在算子类别中的幺半群.这两个概念之间没有天然的联系.如果你能原谅我的轻浮:在Hask中,事实证明箭头中的pro-functor的仿函数部分是一个幺正的仿函数,但这种构造必然会忘记"pro"部分.

当你从箭头转到应用程序时,你忽略了一个箭头部分,它接受输入并只使用处理输出的部分.许多有趣的箭头以某种方式使用输入部分,因此通过将它们转换为应用程序,您放弃了有用的东西.

也就是说,在实践中,我发现应用更好的抽象来工作,而且几乎总能做到我想要的.理论上箭头更强大,但我并没有发现自己在实践中使用它们.

Answer 2

让我们将IO applicative functor与IO monad的Kleisli箭头进行比较.

您可以使用箭头打印上一个箭头读取的值:

runKleisli ((Kleisli $ \() -> getLine) >>> Kleisli putStrLn) ()

但你不能用applicative functor做到这一点.使用applicative仿函数,所有效果都会在将函数函数应用于仿函数中的参数之前发生.函数中的函数不能使用函数中的参数值来"调整"它自己的效果,可以这么说.

Answer 3

(我已将以下内容发布到我的博客上,并附带了扩展介绍)

Tom Ellis建议考虑一个涉及文件I/O的具体示例,所以让我们使用三个类型类比较它的三种方法.为简单起见,我们只关心两个操作:从文件中读取字符串并将字符串写入文件.文件将通过其文件路径标识:

type FilePath = String

Monadic I/O.

我们的第一个I/O接口定义如下:

data IOM ? ? ? ?
instance Monad IOM
readFile ? FilePath ? IOM String
writeFile ? FilePath ? String ? IOM ()

使用此接口,我们可以将文件从一个路径复制到另一个路径:

copy ? FilePath ? FilePath ? IOM ()
copy from to = readFile from >>= writeFile to

但是,我们可以做的远不止于此:我们操作的文件的选择可能取决于上游的影响.例如,下面的函数采用包含文件名的索引文件,并将其复制到给定的目标目录:

copyIndirect ? FilePath ? FilePath ? IOM ()
copyIndirect index target = do
    from ? readFile index
    copy from (target ?/? to)

另一方面,这意味着无法预先知道将由给定值操纵的文件名集action ? IOM ?.通过"前期",我的意思是编写纯函数的能力fileNames :: IOM ? ? [FilePath].

当然,对于非基于IO的monad(例如我们有某种提取器函数的monad ? ? ? ?),这种区别变得有点模糊,但是考虑尝试提取信息而不评估其影响仍然是有意义的. monad(例如,我们可以问"我们可以在Reader ? ?没有?手头类型值的情况下知道什么？").

在monad这个意义上我们无法真正进行静态分析的原因是因为绑定右侧的函数位于Haskell函数的空间中,因此完全不透明.

因此,让我们尝试将我们的界面限制为仅仅是一个应用程序仿函数.

应用I/O.

data IOF ? ? ? ?
instance Applicative IOF
readFile ? FilePath ? IOF String
writeFile ? FilePath ? String ? IOF ()

由于IOF不是一个单子,就没有办法来撰写readFile和writeFile,所以我们可以用这个接口做的是无论是从文件中读取,然后纯后处理的内容,或者写入文件; 但是没有办法将文件的内容写入另一个文件.

如何改变类型writeFile？

writeFile? ? FilePath ? IOF (String ? ())

这个界面的主要问题是虽然它可以写出类似的东西

copy ? FilePath ? FilePath ? IOF ()
copy from to = writeFile? to ?*? readFile from

它导致了各种令人讨厌的问题,因为它String ? ()是一个将字符串写入文件的可怕模型,因为它打破了参照透明度.例如,您希望out.txt运行此程序后的内容是什么？

(? write ? [write "foo", write "bar", write "foo"]) ?$? writeFile? "out.txt"

箭头化I/O的两种方法

首先,让我们得到两个基于箭头的I/O接口,而不是(事实上,不能)带来任何新的东西:Kleisli IOM和Applicarrow IOF.

以IOM模数为基础的Kleisli箭头是:

readFile ? Kleisli IOM FilePath String
writeFile ? Kleisli IOM (FilePath, String) ()

由于writeFile输入仍然包含文件名和内容,我们仍然可以写copyIndirect(为简单起见,使用箭头符号).请注意甚ArrowApply至Kleisli IOM没有使用实例.

copyIndirect ? Kleisli IOM (FilePath, FilePath) ()
copyIndirect = proc (index, target) ? do
    from ? readFile ? index
    s ? readFile ? from
    writeFile ? (to, s)

的Applicarrow的IOF是:

readFile ? FilePath ? Applicarrow IOF () String
writeFile ? FilePath ? String ? Applicarrow IOF () ()

这当然仍表现出了不能构成同样的问题readFile和writeFile.

一个适当的箭头化I/O接口

如果我们从头开始,尝试在两者之间创建一些东西,我们使用Haskell函数的位置和我们制作箭头的位置,那么如何改变IOM或IOF转换为箭头呢？采取以下界面:

data IOA ? ? ? ? ? ?
instance Arrow IOA
readFile ? FilePath ? IOA () String
writeFile ? FilePath ? IOA String ()

因为writeFile从箭头的输入端获取内容,我们仍然可以实现copy:

copy ? FilePath ? FilePath ? IOA () ()
copy from to = readFile from >>> writeFile to

然而,另一个论点writeFile是纯函数的,因此它不能依赖于例如的输出readFile; 因此copyIndirect无法使用此 Arrow界面实现.

如果我们改变这个论点,这也意味着虽然我们事先无法知道什么会最终被写入文件(在运行完整的IOA管道本身之前),但我们可以静态地确定将被修改的文件名集合.

结论

Monad对静态分析是不透明的,而应用函子在表达动态时间数据依赖性方面很差.事实证明,箭头可以在两者之间提供一个最佳点:通过仔细选择纯粹的功能和箭头化的输入,可以创建一个界面,允许动态行为的正确相互作用和静态分析的适应性.