Pertanyaan Operasi yang bermanfaat pada panah bebas


Kami tahu monads gratis berguna, dan paket seperti Operasional membuatnya mudah untuk mendefinisikan monad baru dengan hanya peduli tentang efek spesifik aplikasi, bukan struktur monadik itu sendiri.

Kita dapat dengan mudah mendefinisikan "panah bebas" analog dengan bagaimana monad gratis didefinisikan:

{-# 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

Pertanyaan saya adalah, operasi generik apa yang paling berguna pada panah bebas? Untuk aplikasi khusus saya, saya perlu kasus khusus dari keduanya:

{-# 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

tetapi saya tidak memiliki argumen teoritis tentang mengapa ini (dan bukan yang lain) akan menjadi yang berguna.


32
2017-08-17 07:11


asal


Jawaban:


Sebuah functor gratis dibiarkan berdampingan dengan functor yang lentur. Untuk adjungsi Anda perlu memiliki isomorfisma (alami di x dan y):

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

Dalam kategori apa ini? Fungsi yang lupa melupakan Arrow Misalnya, jadi itu pergi dari kategori Arrow contoh untuk kategori semua bifunctors. Dan fungsi gratis berjalan dengan cara lain, ternyata bifunctor apa pun menjadi gratis Arrow contoh.

Jenis panah haskell dalam kategori bifunctors adalah:

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

Ini sama untuk panah dalam kategori Arrow contoh, tetapi dengan penambahan Arrow kendala. Karena functor yang melupakan hanya melupakan batasannya, kita tidak perlu merepresentasikannya di Haskell. Ini mengubah isomorfisma di atas menjadi dua fungsi:

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

leftAdjunct juga harus memiliki Arrow y kendala, tetapi ternyata hal itu tidak pernah diperlukan dalam pelaksanaannya. Sebenarnya ada implementasi yang sangat sederhana dalam hal yang lebih bermanfaat unit:

unit :: x :~> FreeA x

leftAdjunct f = f . unit

unit itu kamu effect dan rightAdjunct itu kamu evalA. Jadi Anda memiliki fungsi yang dibutuhkan untuk sambungan! Anda harus menunjukkan itu leftAdjunct dan rightAdjunct bersifat isomorfik. Cara termudah untuk melakukannya adalah membuktikannya rightAdjunct unit = id, dalam kasus Anda evalA effect = id, yang mudah.

Bagaimana dengan analyze? Itu evalA khusus untuk panah konstan, dengan hasil Monoid kendala khusus untuk monoid aplikatif. Yaitu.

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

dengan

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

dan Ap dari paket reduksi.

Edit: Saya hampir lupa, FreeA harus menjadi functor order yang lebih tinggi! Edit2: Yang, pada pemikiran kedua, juga bisa diimplementasikan dengan rightAdjunct dan unit.

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

By the way: Ada cara lain untuk menentukan functor gratis, yang saya meletakkan paket di Hackage baru saja. Itu tidak mendukung baik * -> * -> * (Edit: sekarang!), Tetapi kode dapat disesuaikan dengan panah gratis:

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

Jika Anda tidak membutuhkan introspeksi Anda FreeA menawarkan, ini FreeA mungkin lebih cepat.


27
2017-08-24 22:26