Kleislis & Monad Transformsers

gistfile1.weechatlog

(08:14:03 PM) nuttycom: dobblego: if you're about, there is something I'd like to learn from you. :)
(08:14:12 PM) dobblego: I have 15 minutes
(08:14:17 PM) nuttycom: I'd like to learn the meaning of "kleisli"
(08:14:27 PM) dobblego: it's the monad transformer for Function1
(08:14:35 PM) dobblego: A => F[B]
(08:14:59 PM) dobblego: it gives some useful properties
(08:15:14 PM) dobblego: if F is a monad, then A => F[?] is a monad
(08:15:31 PM) copumpkin: another view is that every monad gives rise to a category
(08:15:42 PM) copumpkin: where you have identity and composition like you do with regular functions
(08:16:09 PM) copumpkin: except composition is (A => M[B], B => M[C]): A => M[C]
(08:16:22 PM) copumpkin: or the other order if you prefer
(08:16:26 PM) nuttycom: Monad transformers are something for which I still do not have an intuition. I've heard it said that that they allow composition of monads of different classes (using the term class here loosely) but that's something I need to learn as well.
(08:16:46 PM) copumpkin: well the thing about monads is that they don't really compose
(08:16:53 PM) copumpkin: if you have F[_] and G[_] are functors
(08:16:58 PM) copumpkin: F[G[_]] is magically a functor too
(08:17:00 PM) copumpkin: same with applicatives
(08:17:07 PM) copumpkin: but if M[_] N[_] are monads
(08:17:12 PM) dobblego: transformers are "workarounds" for the fact that monads do not compose
(08:17:15 PM) copumpkin: M[N[_]] isn't necessarily a monad
(08:17:36 PM) nuttycom: Ah, I see. So how do the transformers work around this limitation?
(08:17:49 PM) dobblego: by transforming each specific monad
(08:17:55 PM) dobblego: e.g. Function1 => Kleisli
(08:17:56 PM) copumpkin: well, for specific Monads, sometimes you can stick other monads inside and have monads
(08:18:03 PM) copumpkin: it just isn't true in general
(08:18:15 PM) dobblego: suppose the monad A => ?
(08:18:21 PM) nuttycom: So, monad transformers compose in general?
(08:18:27 PM) dobblego: hmm no
(08:18:33 PM) dobblego: Option is a monad
(08:18:35 PM) nuttycom: Yes
(08:18:43 PM) dobblego: F[Option[?]] is a monad if F is a monad
(08:18:57 PM) dobblego: (trust me for now)
(08:19:09 PM) nuttycom: Actually that seems relatively straightforward.
(08:19:16 PM) dobblego: however, F[G[?]] is not a monad if F and G are monads (in general)
(08:19:29 PM) dobblego: which means we have to be specific to transform each monad e.g. Option
(08:20:02 PM) dobblego: in other words, if you were to write the F[Option[?]] monad transformer implementation, you would use Option-specific functionality in the implementation
(08:20:18 PM) dobblego: Kleisli[A, F, ?] transforms Function1[A, ?]
(08:20:27 PM) dobblego: just like F[Option[?]] transformers Option[?]
(08:21:33 PM) dobblego: "F[G[?]] is not a $X if F and G are $Xs (in general)"
(08:21:40 PM) dobblego: for X=monad, the above statement is not true
(08:21:53 PM) dobblego: for X=applicative functor, the statement is true
(08:22:29 PM) dobblego: maybe I need another post in the series of scala exercises
(08:23:29 PM) nuttycom: I think that I'm close to understanding, but yes, and exercise would be very helpful. Something that cannot be done without the use of a transformer.
(08:23:55 PM) dobblego: all things would be done -- transformers just make it helpful
(08:24:18 PM) dobblego: they are a convenience in the face of an existing immutable law
(08:25:38 PM) nuttycom: In that case, perhaps an example with and without the use of the transformer, and then an exercise?
(08:26:06 PM) dobblego: "Fact: Monads do not compose. What's the next best thing?" -- transformers are a candidate for an answer to this question
(08:26:22 PM) dobblego: yeah I gave amacleod an exercise on it recently -- he got it eventually
(08:26:37 PM) dobblego: are you comfortable with monads in general?
(08:26:49 PM) nuttycom: Yes.
(08:26:57 PM) dobblego: should be a cinch then
(08:27:15 PM) dobblego: suppose trait Monad ...
(08:27:30 PM) dobblego: you could easily write: val OptionMonad: Monad[Option] = ...
(08:27:45 PM) dobblego: case class OptionTrans[F[_], A](v: F[Option[A]])
(08:28:45 PM) dobblego: def OptionTransMonad[F[_]: Monad]: Monad[({type lam[a] = F[Option[a]]}#lam] = ...
(08:28:51 PM) dobblego: that's the next step
(08:29:00 PM) dobblego: then:
(08:29:00 PM) nuttycom: Okay, I can implement that.
(08:29:12 PM) dobblego: case class Function1T[A, F[_], B](v: A => F[B])
(08:29:23 PM) dobblego: oh wait
(08:29:32 PM) dobblego: def OptionTransMonad[F[_]: Monad]: Monad[({type lam[a] = OptionT[F, a]}#lam] = ...
(08:29:58 PM) dobblego: def Function1TransMonad[A, F, [_]: Monad]: Monad[({type lam[a] = Function1Trans[A, F, a]}#lam] = ...
(08:30:20 PM) nuttycom: Marvelous. Thank you.
(08:30:31 PM) dobblego: type Kleisli[A, F, B] = Function1Trans[A, F, B]
(08:30:36 PM) dobblego: same same
(08:32:07 PM) nuttycom: I'll implement these, then if an exercise where I can see the utilization of these (with and without) occurs to you, please let me know.
(08:32:41 PM) dobblego: well, I can think of an easy utility for Kleisli
(08:32:58 PM) dobblego: the Map[K, V].get function: K => Option[V]
(08:33:10 PM) dobblego: that's the same thing as: Kleisli[K, Option, V]
(08:33:34 PM) dobblego: so you can compose them easily, treat as a monad, etc.
(08:34:35 PM) nuttycom: There's a step I'm missing with that. Is there, in that case, an instance of Kleisli for Map or something?
(08:35:25 PM) nuttycom: I see how Kleisli[K, Option, V] can compose, but relating it to Map is puzzling.
(08:35:32 PM) dobblego: no, it's just a data type being returned from Map.get
(08:35:49 PM) dobblego: Map[K, V].get currently returns A => Option[V] right?
(08:36:31 PM) dobblego: let us imagine our own Map implementation
(08:36:32 PM) nuttycom: K => Option[V], yes.
(08:36:38 PM) dobblego: we could alter that type
(08:36:39 PM) nuttycom: Ah, I understand.
(08:36:49 PM) dobblego: and we'd get a bit more convenience
(08:36:52 PM) nuttycom: Map[K, V].get _
(08:37:19 PM) dobblego: if we call >=>: Kleisli[A, F, B] => Kleisli[B, F, C] => Kleisli[A, F, C] (for any monad F)
(08:37:20 PM) nuttycom: In our implementation, this would return Kleisli[K, Option, v]
(08:37:33 PM) dobblego: val g = map1.get >=> map2.get
(08:37:36 PM) dobblego: right
(08:37:36 PM) nuttycom: Very nice. I can use that.
(08:37:49 PM) dobblego: there are heaps of other examples like this
(08:38:43 PM) dobblego: gotta go, later!
(08:38:49 PM) nuttycom: Thanks again!