Tương tự như monads miễn phí cho Profunctors

Question

Chúng tôi có thể xác định data Free f a = Pure a | Free (f (Free f a)) và do đó có Functor f => Monad (Free f).

Nếu chúng tôi xác định data T f a b = R a | S b | T (f a (T f a b)) chúng tôi có một số tương tự M vì vậy Profunctor f => M (T f a), trong đó class Profunctor f where dimap :: (a -> b) -> (c -> d) -> f b c -> f a d?

Tôi đã tự hỏi kể từ khi tôi ghi chú Data.Comp.Term.Context và Free là đẳng cấu về tương tự tiềm năng cho Data.Comp.Param.Term.Context.

Answer 1

Vì vậy, tôi nghĩ rằng tôi figured it out: M ~ Monad ☺

instance Profunctor f => Functor (T f a) where 
    fmap f (In m) = In (dimap id (fmap f) m) 
    fmap f (Hole x) = Hole (f x) 
    fmap f (Var v) = Var v 

instance Profunctor f => Applicative (T f a) where 
    pure = Hole 
    (<*>) = ap 

instance Profunctor f => Monad (T f a) where 
    In m >>= f = In ((>>= f) <$> m) 
    Hole x >>= f = f x 
    Var v >>= _ = Var v 

Có vẻ rõ ràng trong hindthought.

Answer 2

Có một khái niệm phù hợp hơn về việc tạo điều miễn phí từ một giáo sư. Sau đó, chúng tôi có thể làm việc bằng cách tương tự.

Một monoid miễn phí, Y, được tạo bởi một tập X có thể được coi là giải pháp cho phương trình "Y = 1 + XY". Trong ký hiệu Haskell đó là

data List a = Nil | Cons a (List a) 

Một đơn nguyên miễn phí, M, tạo ra bởi các functor F có thể được coi là giải pháp cho phương trình "M = 1 + FM", nơi các sản phẩm "FM' là các thành phần của functors. 1 chỉ là functor sắc. Trong ký hiệu Haskell đó là

data Free f a = Pure a | Free (f (Free a)) 

Làm một cái gì đó miễn phí từ một profunctor P nên trông giống như một giải pháp, A, "A = 1 + PA". sản phẩm này "PA" là 1 tiêu chuẩn composition of profunctors. 1 là "danh tính" profunctor, (->). Vì vậy, chúng tôi nhận được

data Free p a b = Pure (a -> b) | forall x.Free (p a x) (Free p x b) 

Đây cũng là một profunctor:

instance Profunctor b => Profunctor (Free b) where 
    lmap f (Pure g) = Pure (g . f) 
    lmap f (Free g h) = Free (lmap f g) h 
    rmap f (Pure g) = Pure (f . g) 
    rmap f (Free g h) = Free g (rmap f h) 

Nếu profunctor là mạnh mẽ thì như vậy là phiên bản miễn phí:

instance Strong p => Strong (Free p) where 
    first' (Pure f) = Pure (first' f) 
    first' (Free f g) = Free (first' f) (first' g) 

Nhưng những gì thực sự là Free p? Nó thực sự là một thứ gọi là pre-arrow. Hạn chế, profunctors mạnh mẽ miễn phí là mũi tên:

instance Profunctor p => Category (Free p) where 
    id = Pure id 
    Pure f . Pure g = Pure (f . g) 
    Free g h . Pure f = Free (lmap f g) h 
    Pure f . Free g h = Free g (Pure f . h) 
    f . Free g h = Free g (f . h) 

instance (Profunctor p, Strong p) => Arrow (Free p) where 
    arr = Pure 
    first = first' 

trực giác bạn có thể nghĩ đến một phần tử của một profunctor P a b như uống một điều -ish a đến một điều -ish b, ví dụ kinh điển được đưa ra bởi (->). Free P là một chuỗi chưa được đánh giá của các yếu tố này với các loại trung gian tương thích (nhưng không thể quan sát được).