对自由箭头的有用操作 [英] Useful operations on free arrows

问题描述

我们知道免费的 monad 很有用，而像 Operational 这样的包通过只关心特定于应用程序的效果，而不是一元结构本身.

We know free monads are useful, and packages like Operational make it easy to define new monads by only caring about the application-specific effects, not the monadic structure itself.

我们可以很容易地定义自由箭头"，类似于定义自由 monad 的方式:

We can easily define "free arrows" analogous to how free monads are defined:

{-# LANGUAGE GADTs #-}
module FreeA
       ( FreeA, effect
       ) where

import Prelude hiding ((.), id)
import Control.Category
import Control.Arrow
import Control.Applicative
import Data.Monoid

data FreeA eff a b where
    Pure :: (a -> b) -> FreeA eff a b
    Effect :: eff a b -> FreeA eff a b
    Seq :: FreeA eff a b -> FreeA eff b c -> FreeA eff a c
    Par :: FreeA eff a₁ b₁ -> FreeA eff a₂ b₂ -> FreeA eff (a₁, a₂) (b₁, b₂)

effect :: eff a b -> FreeA eff a b
effect = Effect

instance Category (FreeA eff) where
    id = Pure id
    (.) = flip Seq

instance Arrow (FreeA eff) where
    arr = Pure
    first f = Par f id
    second f = Par id f
    (***) = Par

我的问题是，对自由箭头最有用的通用操作是什么?对于我的特定应用程序，我需要这两种特殊情况:

My question is, what would be the most useful generic operations on free arrows? For my particular application, I needed special cases of these two:

{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE ScopedTypeVariables #-}
analyze :: forall f eff a₀ b₀ r. (Applicative f, Monoid r)
        => (forall a b. eff a b -> f r)
        -> FreeA eff a₀ b₀ -> f r
analyze visit = go
  where
    go :: forall a b. FreeA eff a b -> f r
    go arr = case arr of
        Pure _ -> pure mempty
        Seq f₁ f₂ -> mappend <$> go f₁ <*> go f₂
        Par f₁ f₂ -> mappend <$> go f₁ <*> go f₂
        Effect eff -> visit eff

evalA :: forall eff arr a₀ b₀. (Arrow arr) => (forall a b. eff a b -> arr a b) -> FreeA eff a₀ b₀ -> arr a₀ b₀
evalA exec = go
  where
    go :: forall a b. FreeA eff a b -> arr a b
    go freeA = case freeA of
        Pure f -> arr f
        Seq f₁ f₂ -> go f₂ . go f₁
        Par f₁ f₂ -> go f₁ *** go f₂
        Effect eff -> exec eff

但我没有任何关于为什么这些(而不是其他)有用的理论论据.

but I don't have any theoretical arguments on why these (and not others) would be the useful ones.

推荐答案

自由函子与健忘函子相邻.对于附加，您需要具有同构(在 x 和 y 中是自然的):

A free functor is left adjoint to a forgetful functor. For the adjunction you need to have the isomorphism (natural in x and y):

(Free y :~> x) <-> (y :~> Forget x)

这应该属于什么类别?健忘函子忘记了 Arrow 实例，所以它从 Arrow 实例的类别到所有二元函子的类别.而自由函子则相反，它将任何二元函子变成一个自由的 Arrow 实例.

In what category should this be? The forgetful functor forgets the Arrow instance, so it goes from the category of Arrow instances to the category of all bifunctors. And the free functor goes the other way, it turns any bifunctor into a free Arrow instance.

双函子范畴中箭头的haskell类型是:

The haskell type of arrows in the category of bifunctors is:

type x :~> y = forall a b. x a b -> y a b

Arrow 实例类别中的箭头相同，但增加了 Arrow 约束.由于健忘函子只会忘记约束，所以我们不需要在 Haskell 中表示它.这将上述同构转化为两个函数:

It's the same for arrows in the category of Arrow instances, but with addition of Arrow constraints. Since the forgetful functor only forgets the constraint, we don't need to represent it in Haskell. This turns the above isomorphism into two functions:

leftAdjunct :: (FreeA x :~> y) -> x :~> y
rightAdjunct :: Arrow y => (x :~> y) -> FreeA x :~> y

leftAdjunct 也应该有一个 Arrow y 约束，但结果证明在实现中从来不需要它.就更有用的unit而言，实际上有一个非常简单的实现:

leftAdjunct should also have an Arrow y constraint, but it turns out it is never needed in the implementation. There's actually a very simple implementation in terms of the more useful unit:

unit :: x :~> FreeA x

leftAdjunct f = f . unit

unit 是你的 effect 而 rightAdjunct 是你的 evalA.因此，您完全拥有了附加功能所需的功能！您需要证明 leftAdjunct 和 rightAdjunct 是同构的.最简单的方法是证明rightAdjunct unit = id，在你的例子中evalA effect = id，这很简单.

unit is your effect and rightAdjunct is your evalA. So you have exactly the functions needed for the adjunction! You'd need to show that leftAdjunct and rightAdjunct are isomorphic. The easiest way to do that is to prove that rightAdjunct unit = id, in your case evalA effect = id, which is straightforward.

analyze 怎么样?那是 evalA 专用于常量箭头，结果 Monoid 约束专用于 applicative monoid.即

What about analyze? That's evalA specialized to the constant arrow, with the resulting Monoid constraint specialized to the applicative monoid. I.e.

analyze visit = getApp . getConstArr . evalA (ConstArr . Ap . visit)

与

newtype ConstArr m a b = ConstArr { getConstArr :: m }

和 Ap 来自 reducers 包.(从 GHC 8.6 开始，它也在 Data.Monoid 的基础中)

and Ap from the reducers package. ( since GHC 8.6 it is also in base in Data.Monoid)

我差点忘了，FreeA 应该是一个高阶函子！Edit2:再想一想，也可以用 rightAdjunct 和 unit 来实现.

I almost forgot, FreeA should be a higher order functor! Which, on second thought, can also be implemented with rightAdjunct and unit.

hfmap :: (x :~> y) -> FreeA x :~> FreeA y
hfmap f = evalA (effect . f)

顺便说一句:还有另一种定义自由函子的方法，为此我放了一个 包最近被黑客攻击.它不支持种类 * ->* ->*(现在可以了！)，但代码可以适应自由箭头:

By the way: There's another way to define free functors, for which I put a package on Hackage recently. It does not support kind * -> * -> * ( it does now!), but the code can be adapted to free arrows:

newtype FreeA eff a b = FreeA { runFreeA :: forall arr. Arrow arr => (eff :~> arr) -> arr a b }
evalA f a = runFreeA a f
effect a = FreeA $ k -> k a

instance Category (FreeA f) where
  id = FreeA $ const id
  FreeA f . FreeA g = FreeA $ k -> f k . g k

instance Arrow (FreeA f) where
  arr f = FreeA $ const (arr f)
  first (FreeA f) = FreeA $ k -> first (f k)
  second (FreeA f) = FreeA $ k -> second (f k)
  FreeA f *** FreeA g = FreeA $ k -> f k *** g k
  FreeA f &&& FreeA g = FreeA $ k -> f k &&& g k

如果您不需要 FreeA 提供的内省，这个 FreeA 可能会更快.

If you don't need the introspection your FreeA offers, this FreeA is probably faster.

这篇关于对自由箭头的有用操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！