Coyoneda trick

[Debasish Ghosh]

Hello all -

I was looking at the PR https://github.com/scalaz/scalaz/pull/938 that Runar did to simplify the free monad representation in scalaz 7.2.x.

Prior to 7.2.x we had to supply a Coyoneda to get the functor for the type constructor. The current implementation has simplified it a lot and the public interface looks simpler as well. 

One of the commits in the PR says "Reworked Free monad to always use the coyoneda trick". My question is what is the coyoneda trick that this comment refers to ? And how does the current implementation get the Functor that we require for getting the free monad.

Any help will be appreciated ..

Cheers.

--

Debasish Ghosh
http://manning.com/ghosh2

http://manning.com/ghosh

Twttr: @debasishg
Blog: http://debasishg.blogspot.com
Code: http://github.com/debasishg

[Pascal Voitot Dev]

Hi Debasish,

Minus my limited math knowledge, the new Free representation is just a Free (Lan g) where Lan is the Left Kan of g AKA Coyoneda...

My explanation wouldn't be very clear compared to the one in http://okmij.org/ftp/Haskell/extensible/more.pdf, end of Paragraph 2.4 where the equivalence is shown... so read it there IMHO ;)

Pascal

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scalaz+un...@googlegroups.com.
To post to this group, send email to sca...@googlegroups.com.
Visit this group at https://groups.google.com/group/scalaz.
For more options, visit https://groups.google.com/d/optout.

[debasish]

Thanks Pascal for the pointer .. I need to read the paper for a complete understanding .. 

IIUC currently we don't need the Functor or the explicit Coyoneda since the encoding of Free itself has something that's isomorphic to CY ? Is this true ?

Thanks.

[Pascal Voitot Dev]

Le 18 avr. 2016 3:20 PM, "debasish" <ghosh.d...@gmail.com> a écrit :
>
> Thanks Pascal for the pointer .. I need to read the paper for a complete understanding .. 
>
> IIUC currently we don't need the Functor or the explicit Coyoneda since the encoding of Free itself has something that's isomorphic to CY ? Is this true ?
>

Isomorphic to CY, I'm not sure but isomorphic to FreeC, clearly... So yes Functor isn't needed anymore... Which is kind of magic and fantastic fact :)

[debasish]

Which is kind of magic and fantastic fact

Yes .. that's the magic I am trying to understand :-). I am going through the Free er monads paper and kind of understand why we don't need the Functor constraint for Monad(FFree f), but still not clear how this trick is applied to the scalaz Free implementation.

Thanks.

[Runar Bjarnason]

Hi Debasish,

I give a somewhat detailed description of this here: http://blog.higher-order.com/blog/2013/11/01/free-and-yoneda/

The `IO` type given there is the `Free` type in Scalaz 7.2. The `Free` type given there is the `Free` type as it looked like in Scalaz 7.1.

The "coyoneda trick" is that this type is a functor for any given `F`.

trait Coyoneda[F[_],A] {

  type I

  def fi: F[I]

  def k: I => A

}

In fact, it's a free functor:

def cata[G[_]:Functor,A](f: F ~> G): Coyoneda[F,A] => G[A] =

  c => Functor[G].map(f(c.fi))(k)

  

It used to be that `Free` was defined so that Free[F,?] was a monad given a Functor[F]. Now it's defined so that `Coyoneda` is baked right in, so Free[F?] in Scalaz 7.2 is a monad for any type constructor `F`, with no need to prove that it's a functor. By "baked right in", I mean that Free in Scalaz 7.2 is defined as the equivalent of Free[Coyoneda[F,?], A] in Scalaz 7.1.

HTH,

Rúnar

[Debasish Ghosh]

Thanks Runar .. that makes it clear .. 

[Christopher Allen]

To find prior art in Haskell, you want the google search query: Operational monad coyoneda

Operational in Haskell is Free (Coyoneda f)

The Coyoneda provides a sort of degenerate Functor and it's worth observing how Free (IO a) and Operational (IO a) vary in behavior (in Haskell - cannot speak to how Scalaz works) to get a sense of this.

http://stackoverflow.com/a/14295488

https://www.reddit.com/r/haskell/comments/29wyr8/is_there_a_relation_between_the_operational_monad/cipayvg

Hope this helps,

Chris Allen

[Debasish Ghosh]

Thanks Chris for the explanation and the links .. will help for sure ..