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

问题描述

我们知道免费的monad是有用的，像 Operational 这样的软件包可以让您轻松定义新monads，只需关心应用程序特定的效果，而不是一元结构本身。

我们可以很容易地定义自由箭头，类似于自由单体的定义：

  { - ＃LANGUAGE GADTs＃ - } 
模块FreeA 
（FreeA，效果
）其中
 
导入前导隐藏（（。），id）
导入Control.Category 
导入Control.Arrow 
导入Control.Applicative 
导入Data.Monoid 
 
 data FreeA eff ab其中
 Pure ::（a  - > b） - > FreeA eff a b 
效果:: eff a b  - > FreeA eff a b 
 Seq :: FreeA eff a b  - > FreeA eff b c  - > FreeA eff a c 
 Par :: FreeA eff a 1 b 1  - > FreeA eff a 2 b 2  - > FreeA eff（a 1，a 2）（b 1，b 2）
 
效果:: eff a b  - > FreeA eff ab 
效果=效果
 
实例类别（FreeA eff）其中
 id = Pure id 
（。）=翻转序列
 
实例Arrow（FreeA eff）其中
 arr = Pure 
 first f = Par f id 
 second f = Par id f 
（***）= Par 
  

我的问题是，在自由箭头上最有用的通用操作是什么？

  { - ＃LANGUAGE Rank2Types＃ - } 
 {$＃$} $对于我的特定应用程序，我需要以下两种特殊情况： - ＃LANGUAGE ScopedTypeVariables＃ - } 
 analyze :: forall f eff ao b o r r。 （Applicative f，Monoid r）
 => （a b a eff a b  - > f r）
  - > FreeA eff a 0 b 0  - > f r 
分析visit = go 
 where 
 go :: forall a b。 FreeA eff a b  - > f r 
 go arr =案例arr 
 Pure _  - >纯空白
 Seq f 1 f 2  - > mappend< $>去f 1< *>去f 2 
 Par f 1 f 2  - > mappend< $>去f 1< *>去f 2 
效果eff  - >请浏览eff 
 
 evalA :: forall eff arr ao b 0。 （Arrow arr）=> （a b a eff a b  - > arr a b） - > FreeA eff a 0 b 0  - > arr a 0 b 0 
 evalA exec =去
其中
去::所有a b。 FreeA eff a b  - > arr a b 
 go freeA = case freeA of 
 Pure f  - > arr f 
 Seq f 1 f 2  - >去f 2。去f 1 
 Par f 1 f 2  - >去f 1 ***去f 2 
效果eff  - >但是我没有任何关于为什么这些（而不是其他人）会是理论上的论点有用的。
解决方案
一个免费的函子是一个健忘的函子。对于附加，你需要有同构（自然在 x 和 y 中）：
 （Free y：〜> x）<  - > （y：〜>忘记x）
  
这是什么类别？忘记的仿函数忘记了 Arrow 实例，所以它从 Arrow 实例的类别到所有双函数的类别。自由仿函数是另一种方式，它将任何双函数变成免费的箭头实例。
 
 
 
 haskell类型bifunctors类别中的箭头是：
 
 
  type x：〜> y =全部a b。 x a b  - > yab 
  
类似于箭头实例，但添加了箭头约束。由于健忘函子只会忘记约束，所以我们不需要在Haskell中表示它。这将上面的同构变成两个函数：
 
 
  leftAdjunct ::（FreeA x：〜> y） - > x：〜> y 
 rightAdjunct :: Arrow y => （x：〜> y）→> FreeA x：〜> y 
  
  leftAdjunct 也应该有一个 Arrow y 约束，但事实证明它在实现中从不需要。实际上，有一个非常简单的实现方式，就更有用的单位：
  unit :: x：〜> FreeA x 
 
 leftAdjunct f = f。单位
  
 单位是您的效果和 rightAdjunct 是您的 evalA 。所以你有完全的功能所需的功能！您需要证明 leftAdjunct 和 rightAdjunct 是同构的。最简单的方法是证明 rightAdjunct unit = id ，在你的情况下 evalA effect = id ，很简单。
 
 
 
那么分析呢？这就是专门用于常量箭头的 evalA ，并且生成的 Monoid 约束专用于可应用的monoid。 I.e。 
 
 
 分析visit = getApp。 getConstArr。 evalA（ConstArr。Ap。visit）
  
 with  
 
 
  newtype ConstArr mab = ConstArr {getConstArr :: m} 
  
和 Ap 来自 redurs包。
 
编辑：我几乎忘了，FreeA应该是一个更高阶的仿函数！ Edit2：第二个想法也可以用 rightAdjunct 和 unit 。 
  hfmap ::（x：〜> y） - > FreeA x：〜> FreeA y 
 hfmap f = evalA（effect。f）
  
顺便说一句：还有另一个我最近定义了一个自由函数的方法，为此我在Hackage上放了一个包。它不支持kind  *  - > *  - > * （编辑：它现在！），但代码可以适应自由箭头： 
 
 
  newtype FreeA eff ab = FreeA {runFreeA :: forall arr。箭头arr => （eff：〜> arr）→> arr a b} 
 evalA f a = runFreeA a f 
效果a = FreeA $ \k-> k a 
 
实例类别（FreeA f）其中
 id = FreeA $ const id 
 FreeA f。 FreeA g = FreeA $ \k  - > f k。 （FreeA f）其中
 arr f = FreeA $ const（arr f）
 first（FreeA f）= FreeA $ \k  - >第一（f k）
秒（FreeA f）= FreeA $ \k  - >秒（f k）
 FreeA f *** FreeA g = FreeA $ \k  - > f k *** g k 
 FreeA f&&& FreeA g = FreeA $ \k  - > f k&&& gk 
  
如果您不需要自省，您的 FreeA 优惠，这个 FreeA 可能会更快。
 
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.

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.
解决方案
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)
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.

The haskell type of arrows in the category of bifunctors is:
type x :~> y = forall a b. x a b -> y a b
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 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 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.

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)
with
newtype ConstArr m a b = ConstArr { getConstArr :: m }
and Ap from the reducers package.

Edit: I almost forgot, FreeA should be a higher order functor! Edit2: 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 * -> * -> * (Edit: 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
If you don't need the introspection your FreeA offers, this FreeA is probably faster.

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