Skip to content

Instantly share code, notes, and snippets.

@SystemFw

SystemFw/Free conversation.md

Last active October 17, 2023 09:57
Show Gist options
  • Save SystemFw/deb56c93e37af6a1fb1b48f878256b6b to your computer and use it in GitHub Desktop.
Save SystemFw/deb56c93e37af6a1fb1b48f878256b6b to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. SystemFw revised this gist Aug 9, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -258,7 +258,7 @@ _Fabio Labella @SystemFw_
    Exactly, `A` is the return type of the whole program. `B` is the return type of each individual instructions, that's why we need the polymorphism. And, for Category Theory reasons that are (as I hope I've proved) not necessary to understand how `Free` works to an usable extent, `Translator` is the natural transformation:
    ```scala
    trait ~>[F[_], G[_]] {
    def apply[A](f: F[A]): F[B]
    def apply[A](f: F[A]): G[A]
    }
    ```
    What is there left that confuses you in your original question?
  2. SystemFw revised this gist Aug 9, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -247,7 +247,7 @@ _Fabio Labella @SystemFw_
    Not quite. Within the body of `foldMap`, we pattern match on `Free`, which is a program containing instructions.
    So `apply` is called on each of the instructions: `Get` is translated to `Task[Option[String]]`, `Put` is translated to `Task[Unit]`, and so on.

    After doing this translation (whic is the `map`, in `foldMap`), we combine the resulting instructions in the same way they were combined in the original program.
    After doing this translation (which is the `map`, in `foldMap`), we combine the resulting instructions in the same way they were combined in the original program.
    _____
    _Balaji Sivaraman @balajisivaraman_

  3. SystemFw revised this gist Aug 8, 2017. 1 changed file with 57 additions and 78 deletions.
    135 changes: 57 additions & 78 deletions Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -94,7 +94,9 @@ _____
    _Fabio Labella @SystemFw_

    yes, but `IO` and `Task` can do anything Scala can do:
    `Task.delay { // all scala code can fit here, e.g. println()}`
    ```scala
    Task.delay { // all scala code can fit here, e.g. println()}
    ```
    _____
    _Balaji Sivaraman @balajisivaraman_

    @@ -123,29 +125,20 @@ Okay. Normally (as per the YT presentations and my understanding) when we interp
    _____
    _Fabio Labella @SystemFw_

    > when we interpret a Free program, we get something of type A (
    No, that's incorrect
    a `Free monad` is always translated into another `Monad`
    the other `Monad` then does what's needed to produce an `A`
    the only exception is when some examples use `Id`, with side effects
    _____
    _Balaji Sivaraman @balajisivaraman_
    > when we interpret a Free program, we get something of type A

    Okay. Thanks for the clarification. Now I get it.
    _____
    _Fabio Labella @SystemFw_

    that's wrong, and I don't like there are so many examples of this, even on the cats website
    No, that's incorrect. A `Free monad` is always translated into another `Monad`; the other `Monad` then does what's needed to produce an `A`. The only exception is when some examples use `Id`, with side effects:that's wrong, and I don't like there are so many examples of this, even on the cats website
    _____
    _Balaji Sivaraman @balajisivaraman_

    Okay. Thanks for the clarification. Now I get it.
    Ah, that's what threw me off. I'll keep it in mind going forward.
    _____
    _Fabio Labella @SystemFw_

    cool, now let's see how the interpretation function looks in code
    yeah, but without getting too technical, that sentence in quotes above is actually what being `free` means
    anyway, the most common way to interpret a `Free` program (there are others) is through `foldMap`
    yeah, but without getting too technical, that sentence in quotes above is actually what being `free` means.

    Cool, now let's see how the interpretation function looks in code; the most common way to interpret a `Free` program (there are others) is through `foldMap`:
    ```scala
    trait Free[F[_], A] {
    //...
    @@ -160,26 +153,29 @@ The F here is Instr and the G here is Task.
    _____
    _Fabio Labella @SystemFw_

    Yes.
    > if you give me a way to translate each instruction in `Instr[]` into an instruction in `Target[]`
    that's F ~> G, I'll explain more about it in a second
    >I will translate each program in Free[Instr, A]

    that's `F ~> G`, I'll explain more about it in a second

    >I will translate each program in `Free[Instr, A]`

    that's why `foldMap` is on `Free`

    > (implicit gmonad: Monad[G])

    as long as the target is a monad
    yes
    _____
    _Balaji Sivaraman @balajisivaraman_

    Ok, that makes sense.
    _____
    _Fabio Labella @SystemFw_

    now the implementation of `foldMap` is not important for the end user
    what's important is why we need `~>`
    this might be a bit tricky to understand, but it's doable
    so what you want is pass to `foldMap` something that can translate each instruction in `Instr[_]` to something in `Task[_]`
    which is normally written as a pattern match
    how would you write that? any ideas?
    now the implementation of `foldMap` is not important for the end user,what's important is why we need `~>`. This might be a bit tricky to understand, but it's doable.

    So what you want is pass to `foldMap` something that can translate each instruction in `Instr[_]` to something in `Task[_]`,
    which is normally written as a pattern match. How would you write that? Any ideas?
    I'm only interested in the signature, the implementation doesn't really matter
    _____
    _Balaji Sivaraman @balajisivaraman_
    @@ -188,145 +184,128 @@ Just taking a shot, `def translator[A](instr: Instr[A): Task[A]`
    _____
    _Fabio Labella @SystemFw_

    that's the most reasonable assumption, but it doesn't work
    `translator` takes a type parameter `B` (let's rename it to `B` to avoid confusing it with the `A` in `Free`)
    if you do `foldMap(translator)`
    you will need to specify the type `B` (e.g. `foldMap(translator[Int]`)
    what type do you assign to `B`, instead of the bogus `Int` I put there?
    That's the most reasonable assumption, but it doesn't work.
    `translator` takes a type parameter `B` (let's rename it to `B` to avoid confusing it with the `A` in `Free`), so if you do `foldMap(translator)` you will need to specify the type `B` (e.g. `foldMap(translator[Int]`).
    What type do you assign to `B`, instead of the bogus `Int` I put there?
    _____
    _Balaji Sivaraman @balajisivaraman_

    Hmmm, my guess is we don't have one yet. We want it to work for all possible Bs, now and in the future.
    _____
    _Fabio Labella @SystemFw_

    wow
    that's the correct answer!
    we want to pass in a _polymorphic function_
    so when we pass `translator`, we want to keep its polymorphism
    because we will only specialise once we have a specific instruction
    this difference can be made specific in types, but scala doesn't give you a nice notation for it
    I'm going to write it in Haskell for a second, but it should be ok:
    wow, that's the correct answer! We want to pass in a _polymorphic function_, so that when we pass `translator`, we want to keep its polymorphism, because we will only specialise once we have a specific instruction.

    This difference can be made specific in types, but scala doesn't give you a nice notation for it. I'm going to write it in Haskell for a second, but it should be ok:
    ```haskell
    theTranslatorYouHave :: forall f g b. (f b -> g b) -- f b = Instr[B], g b = Task[B]

    theTranslatorYouWant: forall f g. (forall b. f b -> g b)
    ```
    which basically means
    which basically means:

    > we know what `F[_]` and `G[_]` are when we pass `translator` to `foldMap` (`Instr[_]` and `Task[_]` respectively), so we can specialise them, but we want to still be polymorphic in `B`, because only the body of `foldMap` knows how to specialise `B`

    Does this make any sense? (btw, very impressive that you came up with "Hmmm, my guess is we don't have one yet. We want it to work for all possible Bs, now and in the future.", this is a deep concept that normally takes time to sink in)

    "we know what `F[_]` and `G[_]` are when we pass `translator` to `foldMap` (`Instr[_]` and `Task[_]` respectively), so we can specialise them, but we want to still be polymorphic in `B`, because only the body of `foldMap` knows how to specialise `B`"
    does this make any sense? (btw, very impressive that you came up with "Hmmm, my guess is we don't have one yet. We want it to work for all possible Bs, now and in the future.", this is a deep concept that normally takes time to sink in)
    so it should be clear I hope that just a normal function can't work as an argument to `foldMap`, because we want it to work for all possible `B`, now and in the future
    So it should be clear I hope that just a normal function can't work as an argument to `foldMap`, because we want it to work for all possible `B`, now and in the future
    _____
    _Balaji Sivaraman @balajisivaraman_

    Thank you. Yes, because when we call foldMap, we won't have a specialized B. That will only come in higher up the chain when someone calls us. So when we write it, we want it to work for anything that could be passed in. Hopefully that is right.
    _____
    _Fabio Labella @SystemFw_

    yes, it's roughly right
    the ability to pass polymorphic functions around, without losing their polymorphism
    is called _higher-rank polymorphism_
    scala does not have such a feature
    however, we can work our way around it
    let's create a trait
    Yes, it's roughly right. The ability to pass polymorphic functions around, without losing their polymorphism, is called _higher-rank polymorphism_. Scala does not have such a feature, but we can work our way around it.

    Let's create a trait:
    ```scala
    trait Translator[F[_], G[_]] {
    def apply[B](in: F[B]): G[B]
    }
    ```
    now we can write
    Now we can write:
    ```scala
    def translator: Translator[Instr, Task] = new Translator[Instr, Task] {
    def apply[B](in: Instr[B]): Task[B] = in match {
    case Put(k, v) => Task.delay (DB.put(k, v))
    case Get(k) => Task.delay(DB.get(k))
    }
    ```
    we can then say `ourFree.foldMap(translator)`
    notice that the type of translator doesn't mention `B`, but only `Instr` and `Task`
    the apply method is still polymorphic in every `B`, so the body of `foldMap` can call it, and it'll work
    does this make sense?
    and then say `ourFree.foldMap(translator)`.

    Notice that the type of translator doesn't mention `B`, but only `Instr` and `Task`. The apply method is still polymorphic in every `B`, so the body of `foldMap` can call it, and it'll work.

    Does this make sense?
    _____
    _Balaji Sivaraman @balajisivaraman_

    Yes. I'm with you so far. Just to clarify, within the body of foldMap, we have an A, which is basically the A of the Free. And this is the A that is applied when we call Translator.apply. Is that right?
    _____
    _Fabio Labella @SystemFw_

    not quite
    within the body of `foldMap`, we pattern match on `Free`
    which is a program containing instructions
    so apply is called on each of the instructions, so `Get` is translated to `Task[Option[String]]`, `Put` is translated to `Task[Unit]`, and so on
    after doing this translation (this is the `map`, in `foldMap`)
    we combine them in the same way they were combined in the original program
    Not quite. Within the body of `foldMap`, we pattern match on `Free`, which is a program containing instructions.
    So `apply` is called on each of the instructions: `Get` is translated to `Task[Option[String]]`, `Put` is translated to `Task[Unit]`, and so on.

    After doing this translation (whic is the `map`, in `foldMap`), we combine the resulting instructions in the same way they were combined in the original program.
    _____
    _Balaji Sivaraman @balajisivaraman_

    Okay. That makes a whole lot of sense. Thanks a lot. And the translator in our case is the Natural Transformation.
    _____
    _Fabio Labella @SystemFw_

    exactly, `A` is the return type of the whole program
    `B` is the return type of each individual instructions, that's why we need the polymorphism
    for Category Theory reasons that are (as I hope I've proved) not necessary to understand how `Free` works to an usable extent, `Translator` is the natural transformation:
    Exactly, `A` is the return type of the whole program. `B` is the return type of each individual instructions, that's why we need the polymorphism. And, for Category Theory reasons that are (as I hope I've proved) not necessary to understand how `Free` works to an usable extent, `Translator` is the natural transformation:
    ```scala
    trait ~>[F[_], G[_]] {
    def apply[A](f: F[A]): F[B]
    }
    ```
    what is there left that confuses you in your original question?
    What is there left that confuses you in your original question?
    _____
    _Balaji Sivaraman @balajisivaraman_

    Nothing. I got it. (I think.) Thanks a lot. And the interpreter for Doobie is the one in transactor: ConnectionOp ~> Kleisli[M, Connection, ?]. This will translate any program in ConnectionIO to a Kleisli program. In my case, it will be a Kleisli[Task, Connection, Unit]. And when I run that, I will get a Task[Unit], which is the final output type.
    _____
    _Fabio Labella @SystemFw_

    yes
    you need the type lambda because `G[_]` is of higher kind in `~>`: you still need to be polymorphic in `B`
    Yes. You need the type lambda because `G[_]` is of higher kind in `~>`: you still need to be polymorphic in `B`
    _____
    _Balaji Sivaraman @balajisivaraman_

    Ok. So we need that to mean Kleisli[M, Connection, _], substitute whatever type you want for the underscore. I assume this is also because of a limitation of Scala.
    _____
    _Fabio Labella @SystemFw_

    so `Kleisli[M, Connection, Unit]` is wrong, you need type `Target[A] = Kleisli[M, Connection, A]` and `ConnectionOp ~> Target` (note `Target`, not `Target[Unit]`). The type lambda is a shorthand for that
    well, it's more like we put an `?`, instead of an `_`
    so it's inconsistent (`_` means several different things in the scala type system, which is unfortunate)
    but we can do it
    `Kleisli[M, Connection, _]` is written `Kleisli[M, Connection, ?]`
    and there's your type lambda
    so `Kleisli[M, Connection, Unit]` is wrong, you need type `Target[A] = Kleisli[M, Connection, A]` and `ConnectionOp ~> Target` (note `Target`, not `Target[Unit]`). The type lambda is a shorthand for that.

    Well, it's more like we put an `?`, instead of an `_`, so it's inconsistent (`_` means several different things in the scala type system, which is unfortunate), but we _can_ do it: `Kleisli[M, Connection, _]` is written `Kleisli[M, Connection, ?]`, and there's your type lambda
    _____
    _Balaji Sivaraman @balajisivaraman_

    Okay. I got it. Just to clarify, based on my reading, that would be the same astype SomeType[A] = Kleisli[M, Connection, A], which falls neatly into the "shape" G[_].
    _____
    _Fabio Labella @SystemFw_

    yes, exactly
    Yes, exactly
    _____
    _Balaji Sivaraman @balajisivaraman_

    Actually, your entire explanation from my question has made a whole lot of sense. Thank you for taking the time to do it. :grinning: I now feel I'm in a position to dig deeper into not only the fuseMap function, but also the surface-level of Doobie.
    _____
    _Fabio Labella @SystemFw_

    yes, `translate` is another variation of this pattern
    when you want to go from `Free[Lang1, A]` to `Free[Lang2, A]`
    so basically just change the instruction set
    `ConnectionIO` is `Free`
    fs2 `Stream` has (a lot of) extra machinery, but the basic idea is the same
    we parameterise over the effect `F`, and then in the end interpret to an `F[A]`
    Yes, `translate` is another variation of this pattern, when you want to go from `Free[Lang1, A]` to `Free[Lang2, A]`, so basically just changing the instruction set.

    `ConnectionIO` is `Free`. Fs2 `Stream` has (a lot of) extra machinery, but the basic idea is the same: we parameterise over the effect `F`, and then in the end interpret to an `F[A]`
    _____
    _Balaji Sivaraman @balajisivaraman_

    Okay. I got it. Thank you so much.
    _____
    _Fabio Labella @SystemFw_

    no worries
    No worries :)
    _____
    _Balaji Sivaraman @balajisivaraman_

  4. SystemFw revised this gist Aug 8, 2017. 1 changed file with 17 additions and 28 deletions.
    45 changes: 17 additions & 28 deletions Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -47,8 +47,7 @@ _Balaji Sivaraman @balajisivaraman_
    _____
    _Fabio Labella @SystemFw_

    right, let's skip Cat Theory <br>
    are you familiar with Free at all? (in code, not CT)
    right, let's skip Cat Theory. Are you familiar with Free at all? (in code, not CT)
    _____
    _Balaji Sivaraman @balajisivaraman_

    @@ -63,47 +62,38 @@ trait KVS[A]
    case class Get(k: String) extends KVS[Option[String]]
    case class Put(k: String, v: String) extends KVS[Unit]
    ```
    note that `KVS` has higher kind, i.e. `KVS[_]`, like `Option` and `List` but unlike `Int` <br>
    `Free` represent a description of a program, and it takes two type parameters <br>
    `Free[Instr[_], A]` <br>
    `Instr[_]` is your ADT, it represents the individual instructions in your mini language. It needs to be `[_]` so that we can express the fact that each instruction returns a different type (e.g. `Option[String]` for `Get`, `Unit` for `Put`) <br>
    `A` represents the return type of your mini program <br>
    so `Free[Instr[_], A]` can be seen as a program written in the mini language whose primitives are described by `Instr[_]` which, when run, will eventually result in a value of type `A` <br>
    are you with me so far?
    note that `KVS` has higher kind, i.e. `KVS[_]`, like `Option` and `List` but unlike `Int`. `Free` represent a description of a program, and it takes two type parameters: `Free[Instr[_], A]`.

    `Instr[_]` is your ADT, it represents the individual instructions in your mini language. It needs to be `[_]` so that we can express the fact that each instruction returns a different type (e.g. `Option[String]` for `Get`, `Unit` for `Put`).`A` represents the return type of your mini program.

    So `Free[Instr[_], A]` can be seen as a program written in the mini language whose primitives are described by `Instr[_]` which, when run, will eventually result in a value of type `A`. Are you with me so far?
    _____
    _Balaji Sivaraman @balajisivaraman_

    Yes. I'm able to follow it.
    _____
    _Fabio Labella @SystemFw_

    cool, now you have this data structure that represents a program
    the way we run it is by interpreting it into another, more powerful data structure
    e.g. `IO`, or `Task`
    which you can look at as a `Free` with an unlimited set of instructions
    once we have this more powerful type, we can keep composing it with other `Task` (let's pick `Task` for now)
    and finally, when we're done, we call `unsafePerformSync` at the end of the world
    and things actually happen
    is this also clear?
    Cool, now you have this data structure that represents a program. The way we run it is by interpreting it into another, more powerful data structure, e.g. `IO`, or `Task`, which you can look at as a `Free` with an unlimited set of instructions.

    Once we have this more powerful type, we can keep composing it with other `Task` (let's pick `Task` for now) and finally, when we're done, we call `unsafePerformSync` at the end of the world, and things actually happen. Is this also clear?
    _____
    _Balaji Sivaraman @balajisivaraman_

    Yeah. Except the part with "unlimited set of instructions", I'm not sure what unlimited means here.
    _____
    _Fabio Labella @SystemFw_

    it means that in `IO` you can do everything
    because `IO` encapsulates arbitrary side effects from the impure subset of Scala
    whereas in your own `Free` you can only do `Get` or `Put`
    it's a fairly poor metaphor, apologies
    it means that in `IO` you can do everything since `IO` encapsulates arbitrary side effects from the impure subset of Scala,
    whereas in your own `Free` you can only do `Get` or `Put`. It's a fairly poor metaphor, apologies.
    _____
    _Balaji Sivaraman @balajisivaraman_

    Ok. But still limited by what `IO` and `Task` can actually do right?
    _____
    _Fabio Labella @SystemFw_

    yes, but `IO` and `Task` can do anything Scala can do
    yes, but `IO` and `Task` can do anything Scala can do:
    `Task.delay { // all scala code can fit here, e.g. println()}`
    _____
    _Balaji Sivaraman @balajisivaraman_
    @@ -120,12 +110,11 @@ Ah, I'm with you so far.
    _____
    _Fabio Labella @SystemFw_

    right, so interpreting a `Free` means going from a less powerful, but more precise language, to a more powerful but less precise language
    _Natural Transformations_ are involved in the process of interpretation
    I'm going to try to explain this interpretation in english, then we can move to code
    let's say `Instr[_]` is your ADT, and `Target[_]` is any `Monad` (we will pick Task)
    interpreting `Free` means
    "if you give me a way to translate each _instruction_ in `Instr[_]` into an instruction in `Target[_]`, I will translate each _program_ in `Free[Instr, A]` into a program in `Target[A]`"
    right, so interpreting a `Free` means going from a less powerful, but more precise language, to a more powerful but less precise language. _Natural Transformations_ are involved in the process of interpretation: I'm going to try to explain this interpretation in english, then we can move to code.

    let's say `Instr[_]` is your ADT, and `Target[_]` is any `Monad` (we will pick Task). Interpreting `Free` means:
    > if you give me a way to translate each _instruction_ in `Instr[_]` into an instruction in `Target[_]`, I will translate each _program_ in `Free[Instr, A]` into a program in `Target[A]`
    does this sentence make sense?
    _____
    _Balaji Sivaraman @balajisivaraman_
  5. SystemFw revised this gist Aug 8, 2017. 1 changed file with 6 additions and 6 deletions.
    12 changes: 6 additions & 6 deletions Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -63,12 +63,12 @@ trait KVS[A]
    case class Get(k: String) extends KVS[Option[String]]
    case class Put(k: String, v: String) extends KVS[Unit]
    ```
    note that `KVS` has higher kind, i.e. `KVS[_]`, like `Option` and `List` but unlike `Int`
    `Free` represent a description of a program, and it takes two type parameters
    `Free[Instr[_], A]`
    `Instr[_]` is your ADT, it represents the individual instructions in your mini language. It needs to be `[_]` so that we can express the fact that each instruction returns a different type (e.g. `Option[String]` for `Get`, `Unit` for `Put`)
    `A` represents the return type of your mini program
    so `Free[Instr[_], A]` can be seen as a program written in the mini language whose primitives are described by `Instr[_]` which, when run, will eventually result in a value of type `A`
    note that `KVS` has higher kind, i.e. `KVS[_]`, like `Option` and `List` but unlike `Int` <br>
    `Free` represent a description of a program, and it takes two type parameters <br>
    `Free[Instr[_], A]` <br>
    `Instr[_]` is your ADT, it represents the individual instructions in your mini language. It needs to be `[_]` so that we can express the fact that each instruction returns a different type (e.g. `Option[String]` for `Get`, `Unit` for `Put`) <br>
    `A` represents the return type of your mini program <br>
    so `Free[Instr[_], A]` can be seen as a program written in the mini language whose primitives are described by `Instr[_]` which, when run, will eventually result in a value of type `A` <br>
    are you with me so far?
    _____
    _Balaji Sivaraman @balajisivaraman_
  6. SystemFw revised this gist Aug 8, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -47,7 +47,7 @@ _Balaji Sivaraman @balajisivaraman_
    _____
    _Fabio Labella @SystemFw_

    right, let's skip Cat Theory \\
    right, let's skip Cat Theory <br>
    are you familiar with Free at all? (in code, not CT)
    _____
    _Balaji Sivaraman @balajisivaraman_
  7. SystemFw revised this gist Aug 8, 2017. 1 changed file with 1 addition and 2 deletions.
    3 changes: 1 addition & 2 deletions Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -47,8 +47,7 @@ _Balaji Sivaraman @balajisivaraman_
    _____
    _Fabio Labella @SystemFw_

    right, let's skip Cat Theory

    right, let's skip Cat Theory \\
    are you familiar with Free at all? (in code, not CT)
    _____
    _Balaji Sivaraman @balajisivaraman_
  8. SystemFw revised this gist Aug 8, 2017. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -48,6 +48,7 @@ _____
    _Fabio Labella @SystemFw_

    right, let's skip Cat Theory

    are you familiar with Free at all? (in code, not CT)
    _____
    _Balaji Sivaraman @balajisivaraman_
  9. SystemFw revised this gist Aug 8, 2017. 1 changed file with 96 additions and 48 deletions.
    144 changes: 96 additions & 48 deletions Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -45,15 +45,18 @@ _Balaji Sivaraman @balajisivaraman_
    @SystemFw Apart from following the code and being taken to the natural transformation source code, not really. I also read this post (http://eed3si9n.com/learning-scalaz/Natural-Transformation.html), and got a very rudimentary idea, but the last part of that post with the Cat Theory was lost on me.

    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    right, let's skip Cat Theory
    are you familiar with Free at all? (in code, not CT)
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Have seen both Rob's presentation (https://www.youtube.com/watch?v=M5MF6M7FHPo) and Runar's (https://www.youtube.com/watch?v=M258zVn4m2M)
    , but this is my first real experience using a library with those concepts. I guess that's why I'm struggling.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    so, basically you have an ADT describing the instructions of your language
    ```scala
    trait KVS[A]
    @@ -68,10 +71,12 @@ note that `KVS` has higher kind, i.e. `KVS[_]`, like `Option` and `List` but unl
    so `Free[Instr[_], A]` can be seen as a program written in the mini language whose primitives are described by `Instr[_]` which, when run, will eventually result in a value of type `A`
    are you with me so far?
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Yes. I'm able to follow it.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    cool, now you have this data structure that represents a program
    the way we run it is by interpreting it into another, more powerful data structure
    e.g. `IO`, or `Task`
    @@ -81,32 +86,40 @@ and finally, when we're done, we call `unsafePerformSync` at the end of the worl
    and things actually happen
    is this also clear?
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Yeah. Except the part with "unlimited set of instructions", I'm not sure what unlimited means here.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    it means that in `IO` you can do everything
    because `IO` encapsulates arbitrary side effects from the impure subset of Scala
    whereas in your own `Free` you can only do `Get` or `Put`
    it's a fairly poor metaphor, apologies
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Ok. But still limited by what `IO` and `Task` can actually do right?
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    yes, but `IO` and `Task` can do anything Scala can do
    `Task.delay { // all scala code can fit here, e.g. println()}`
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    In terms of side-effects? Now I get it.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    yes, albeit they are not _side_ effects, because `Task` and `IO` encapsulate them, so nothing is happening until you explicitly run them
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Ah, I'm with you so far.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    right, so interpreting a `Free` means going from a less powerful, but more precise language, to a more powerful but less precise language
    _Natural Transformations_ are involved in the process of interpretation
    I'm going to try to explain this interpretation in english, then we can move to code
    @@ -115,26 +128,32 @@ interpreting `Free` means
    "if you give me a way to translate each _instruction_ in `Instr[_]` into an instruction in `Target[_]`, I will translate each _program_ in `Free[Instr, A]` into a program in `Target[A]`"
    does this sentence make sense?
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Okay. Normally (as per the YT presentations and my understanding) when we interpret a Free program, we get something of type A (Get interpreted would give A, Put interpreted would give Unit). Now instead of that, what we're saying is we will interpret it into another target Monad (Task) and then use Task to gain additional benefits.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    > when we interpret a Free program, we get something of type A (
    No, that's incorrect
    a `Free monad` is always translated into another `Monad`
    the other `Monad` then does what's needed to produce an `A`
    the only exception is when some examples use `Id`, with side effects
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Okay. Thanks for the clarification. Now I get it.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    that's wrong, and I don't like there are so many examples of this, even on the cats website
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Ah, that's what threw me off. I'll keep it in mind going forward.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    cool, now let's see how the interpretation function looks in code
    yeah, but without getting too technical, that sentence in quotes above is actually what being `free` means
    anyway, the most common way to interpret a `Free` program (there are others) is through `foldMap`
    @@ -146,10 +165,12 @@ anyway, the most common way to interpret a `Free` program (there are others) is
    ```
    which you should be able to reconcile with the sentence above
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    The F here is Instr and the G here is Task.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    > if you give me a way to translate each instruction in `Instr[]` into an instruction in `Target[]`
    that's F ~> G, I'll explain more about it in a second
    >I will translate each program in Free[Instr, A]
    @@ -158,10 +179,12 @@ that's why `foldMap` is on `Free`
    as long as the target is a monad
    yes
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Ok, that makes sense.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    now the implementation of `foldMap` is not important for the end user
    what's important is why we need `~>`
    this might be a bit tricky to understand, but it's doable
    @@ -170,20 +193,24 @@ which is normally written as a pattern match
    how would you write that? any ideas?
    I'm only interested in the signature, the implementation doesn't really matter
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Just taking a shot, `def translator[A](instr: Instr[A): Task[A]`
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    that's the most reasonable assumption, but it doesn't work
    `translator` takes a type parameter `B` (let's rename it to `B` to avoid confusing it with the `A` in `Free`)
    if you do `foldMap(translator)`
    you will need to specify the type `B` (e.g. `foldMap(translator[Int]`)
    what type do you assign to `B`, instead of the bogus `Int` I put there?
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Hmmm, my guess is we don't have one yet. We want it to work for all possible Bs, now and in the future.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    wow
    that's the correct answer!
    we want to pass in a _polymorphic function_
    @@ -202,10 +229,12 @@ which basically means
    does this make any sense? (btw, very impressive that you came up with "Hmmm, my guess is we don't have one yet. We want it to work for all possible Bs, now and in the future.", this is a deep concept that normally takes time to sink in)
    so it should be clear I hope that just a normal function can't work as an argument to `foldMap`, because we want it to work for all possible `B`, now and in the future
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Thank you. Yes, because when we call foldMap, we won't have a specialized B. That will only come in higher up the chain when someone calls us. So when we write it, we want it to work for anything that could be passed in. Hopefully that is right.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    yes, it's roughly right
    the ability to pass polymorphic functions around, without losing their polymorphism
    is called _higher-rank polymorphism_
    @@ -230,21 +259,25 @@ notice that the type of translator doesn't mention `B`, but only `Instr` and `Ta
    the apply method is still polymorphic in every `B`, so the body of `foldMap` can call it, and it'll work
    does this make sense?
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Yes. I'm with you so far. Just to clarify, within the body of foldMap, we have an A, which is basically the A of the Free. And this is the A that is applied when we call Translator.apply. Is that right?
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    not quite
    within the body of `foldMap`, we pattern match on `Free`
    which is a program containing instructions
    so apply is called on each of the instructions, so `Get` is translated to `Task[Option[String]]`, `Put` is translated to `Task[Unit]`, and so on
    after doing this translation (this is the `map`, in `foldMap`)
    we combine them in the same way they were combined in the original program
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Okay. That makes a whole lot of sense. Thanks a lot. And the translator in our case is the Natural Transformation.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    exactly, `A` is the return type of the whole program
    `B` is the return type of each individual instructions, that's why we need the polymorphism
    for Category Theory reasons that are (as I hope I've proved) not necessary to understand how `Free` works to an usable extent, `Translator` is the natural transformation:
    @@ -255,64 +288,79 @@ trait ~>[F[_], G[_]] {
    ```
    what is there left that confuses you in your original question?
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Nothing. I got it. (I think.) Thanks a lot. And the interpreter for Doobie is the one in transactor: ConnectionOp ~> Kleisli[M, Connection, ?]. This will translate any program in ConnectionIO to a Kleisli program. In my case, it will be a Kleisli[Task, Connection, Unit]. And when I run that, I will get a Task[Unit], which is the final output type.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    yes
    you need the type lambda because `G[_]` is of higher kind in `~>`: you still need to be polymorphic in `B`
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Ok. So we need that to mean Kleisli[M, Connection, _], substitute whatever type you want for the underscore. I assume this is also because of a limitation of Scala.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    so `Kleisli[M, Connection, Unit]` is wrong, you need type `Target[A] = Kleisli[M, Connection, A]` and `ConnectionOp ~> Target` (note `Target`, not `Target[Unit]`). The type lambda is a shorthand for that
    well, it's more like we put an `?`, instead of an `_`
    so it's inconsistent (`_` means several different things in the scala type system, which is unfortunate)
    but we can do it
    `Kleisli[M, Connection, _]` is written `Kleisli[M, Connection, ?]`
    and there's your type lambda
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Okay. I got it. Just to clarify, based on my reading, that would be the same astype SomeType[A] = Kleisli[M, Connection, A], which falls neatly into the "shape" G[_].
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    yes, exactly
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Actually, your entire explanation from my question has made a whole lot of sense. Thank you for taking the time to do it. :grinning: I now feel I'm in a position to dig deeper into not only the fuseMap function, but also the surface-level of Doobie.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    yes, `translate` is another variation of this pattern
    when you want to go from `Free[Lang1, A]` to `Free[Lang2, A]`
    so basically just change the instruction set
    `ConnectionIO` is `Free`
    fs2 `Stream` has (a lot of) extra machinery, but the basic idea is the same
    we parameterise over the effect `F`, and then in the end interpret to an `F[A]`
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Okay. I got it. Thank you so much.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    no worries
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    I will revisit both fuseMap and also poke around Doobie and Scalaz-Stream.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    Yes, the important thing is to grasp the key concepts:
    - A Free monad is always translated to another monad, which does the actual work
    - The process of interpretation takes a translation between instructions, and gives a translation between programs
    - You need higher-rank polymorphism (the trait trick)
    - everything follows by having things fit into the right shape
    _____
    Zizheng Tai @ZizhengTai
    _Zizheng Tai @ZizhengTai_

    Fabio you are a great teacher.
    _____
    Balaji Sivaraman @balajisivaraman
    _Balaji Sivaraman @balajisivaraman_

    Okay. :thumbsup:
    @ZizhengTai Indeed.
    _____
    Fabio Labella @SystemFw
    _Fabio Labella @SystemFw_

    @ZizhengTai Thank you! :-)
    I will put this in a gist for future consultation, I think conversations are a great way to learn
  10. SystemFw revised this gist Aug 8, 2017. 1 changed file with 48 additions and 49 deletions.
    97 changes: 48 additions & 49 deletions Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -44,16 +44,15 @@ _Balaji Sivaraman @balajisivaraman_

    @SystemFw Apart from following the code and being taken to the natural transformation source code, not really. I also read this post (http://eed3si9n.com/learning-scalaz/Natural-Transformation.html), and got a very rudimentary idea, but the last part of that post with the Cat Theory was lost on me.

    ________

    _____
    Fabio Labella @SystemFw
    right, let's skip Cat Theory
    are you familiar with Free at all? (in code, not CT)
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Have seen both Rob's presentation (https://www.youtube.com/watch?v=M5MF6M7FHPo) and Runar's (https://www.youtube.com/watch?v=M258zVn4m2M)
    , but this is my first real experience using a library with those concepts. I guess that's why I'm struggling.
    -----
    _____
    Fabio Labella @SystemFw
    so, basically you have an ADT describing the instructions of your language
    ```scala
    @@ -68,10 +67,10 @@ note that `KVS` has higher kind, i.e. `KVS[_]`, like `Option` and `List` but unl
    `A` represents the return type of your mini program
    so `Free[Instr[_], A]` can be seen as a program written in the mini language whose primitives are described by `Instr[_]` which, when run, will eventually result in a value of type `A`
    are you with me so far?
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Yes. I'm able to follow it.
    -----
    _____
    Fabio Labella @SystemFw
    cool, now you have this data structure that represents a program
    the way we run it is by interpreting it into another, more powerful data structure
    @@ -81,32 +80,32 @@ once we have this more powerful type, we can keep composing it with other `Task`
    and finally, when we're done, we call `unsafePerformSync` at the end of the world
    and things actually happen
    is this also clear?
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Yeah. Except the part with "unlimited set of instructions", I'm not sure what unlimited means here.
    -----
    _____
    Fabio Labella @SystemFw
    it means that in `IO` you can do everything
    because `IO` encapsulates arbitrary side effects from the impure subset of Scala
    whereas in your own `Free` you can only do `Get` or `Put`
    it's a fairly poor metaphor, apologies
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Ok. But still limited by what `IO` and `Task` can actually do right?
    -----
    _____
    Fabio Labella @SystemFw
    yes, but `IO` and `Task` can do anything Scala can do
    `Task.delay { // all scala code can fit here, e.g. println()}`
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    In terms of side-effects? Now I get it.
    -----
    _____
    Fabio Labella @SystemFw
    yes, albeit they are not _side_ effects, because `Task` and `IO` encapsulate them, so nothing is happening until you explicitly run them
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Ah, I'm with you so far.
    -----
    _____
    Fabio Labella @SystemFw
    right, so interpreting a `Free` means going from a less powerful, but more precise language, to a more powerful but less precise language
    _Natural Transformations_ are involved in the process of interpretation
    @@ -115,26 +114,26 @@ let's say `Instr[_]` is your ADT, and `Target[_]` is any `Monad` (we will pick T
    interpreting `Free` means
    "if you give me a way to translate each _instruction_ in `Instr[_]` into an instruction in `Target[_]`, I will translate each _program_ in `Free[Instr, A]` into a program in `Target[A]`"
    does this sentence make sense?
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Okay. Normally (as per the YT presentations and my understanding) when we interpret a Free program, we get something of type A (Get interpreted would give A, Put interpreted would give Unit). Now instead of that, what we're saying is we will interpret it into another target Monad (Task) and then use Task to gain additional benefits.
    -----
    _____
    Fabio Labella @SystemFw
    > when we interpret a Free program, we get something of type A (
    No, that's incorrect
    a `Free monad` is always translated into another `Monad`
    the other `Monad` then does what's needed to produce an `A`
    the only exception is when some examples use `Id`, with side effects
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Okay. Thanks for the clarification. Now I get it.
    -----
    _____
    Fabio Labella @SystemFw
    that's wrong, and I don't like there are so many examples of this, even on the cats website
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Ah, that's what threw me off. I'll keep it in mind going forward.
    -----
    _____
    Fabio Labella @SystemFw
    cool, now let's see how the interpretation function looks in code
    yeah, but without getting too technical, that sentence in quotes above is actually what being `free` means
    @@ -146,10 +145,10 @@ anyway, the most common way to interpret a `Free` program (there are others) is
    }
    ```
    which you should be able to reconcile with the sentence above
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    The F here is Instr and the G here is Task.
    -----
    _____
    Fabio Labella @SystemFw
    > if you give me a way to translate each instruction in `Instr[]` into an instruction in `Target[]`
    that's F ~> G, I'll explain more about it in a second
    @@ -158,10 +157,10 @@ that's why `foldMap` is on `Free`
    > (implicit gmonad: Monad[G])
    as long as the target is a monad
    yes
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Ok, that makes sense.
    -----
    _____
    Fabio Labella @SystemFw
    now the implementation of `foldMap` is not important for the end user
    what's important is why we need `~>`
    @@ -170,20 +169,20 @@ so what you want is pass to `foldMap` something that can translate each instruct
    which is normally written as a pattern match
    how would you write that? any ideas?
    I'm only interested in the signature, the implementation doesn't really matter
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Just taking a shot, `def translator[A](instr: Instr[A): Task[A]`
    -----
    _____
    Fabio Labella @SystemFw
    that's the most reasonable assumption, but it doesn't work
    `translator` takes a type parameter `B` (let's rename it to `B` to avoid confusing it with the `A` in `Free`)
    if you do `foldMap(translator)`
    you will need to specify the type `B` (e.g. `foldMap(translator[Int]`)
    what type do you assign to `B`, instead of the bogus `Int` I put there?
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Hmmm, my guess is we don't have one yet. We want it to work for all possible Bs, now and in the future.
    -----
    _____
    Fabio Labella @SystemFw
    wow
    that's the correct answer!
    @@ -202,10 +201,10 @@ which basically means
    "we know what `F[_]` and `G[_]` are when we pass `translator` to `foldMap` (`Instr[_]` and `Task[_]` respectively), so we can specialise them, but we want to still be polymorphic in `B`, because only the body of `foldMap` knows how to specialise `B`"
    does this make any sense? (btw, very impressive that you came up with "Hmmm, my guess is we don't have one yet. We want it to work for all possible Bs, now and in the future.", this is a deep concept that normally takes time to sink in)
    so it should be clear I hope that just a normal function can't work as an argument to `foldMap`, because we want it to work for all possible `B`, now and in the future
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Thank you. Yes, because when we call foldMap, we won't have a specialized B. That will only come in higher up the chain when someone calls us. So when we write it, we want it to work for anything that could be passed in. Hopefully that is right.
    -----
    _____
    Fabio Labella @SystemFw
    yes, it's roughly right
    the ability to pass polymorphic functions around, without losing their polymorphism
    @@ -230,21 +229,21 @@ we can then say `ourFree.foldMap(translator)`
    notice that the type of translator doesn't mention `B`, but only `Instr` and `Task`
    the apply method is still polymorphic in every `B`, so the body of `foldMap` can call it, and it'll work
    does this make sense?
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Yes. I'm with you so far. Just to clarify, within the body of foldMap, we have an A, which is basically the A of the Free. And this is the A that is applied when we call Translator.apply. Is that right?
    -----
    _____
    Fabio Labella @SystemFw
    not quite
    within the body of `foldMap`, we pattern match on `Free`
    which is a program containing instructions
    so apply is called on each of the instructions, so `Get` is translated to `Task[Option[String]]`, `Put` is translated to `Task[Unit]`, and so on
    after doing this translation (this is the `map`, in `foldMap`)
    we combine them in the same way they were combined in the original program
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Okay. That makes a whole lot of sense. Thanks a lot. And the translator in our case is the Natural Transformation.
    -----
    _____
    Fabio Labella @SystemFw
    exactly, `A` is the return type of the whole program
    `B` is the return type of each individual instructions, that's why we need the polymorphism
    @@ -255,65 +254,65 @@ trait ~>[F[_], G[_]] {
    }
    ```
    what is there left that confuses you in your original question?
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Nothing. I got it. (I think.) Thanks a lot. And the interpreter for Doobie is the one in transactor: ConnectionOp ~> Kleisli[M, Connection, ?]. This will translate any program in ConnectionIO to a Kleisli program. In my case, it will be a Kleisli[Task, Connection, Unit]. And when I run that, I will get a Task[Unit], which is the final output type.
    -----
    _____
    Fabio Labella @SystemFw
    yes
    you need the type lambda because `G[_]` is of higher kind in `~>`: you still need to be polymorphic in `B`
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Ok. So we need that to mean Kleisli[M, Connection, _], substitute whatever type you want for the underscore. I assume this is also because of a limitation of Scala.
    -----
    _____
    Fabio Labella @SystemFw
    so `Kleisli[M, Connection, Unit]` is wrong, you need type `Target[A] = Kleisli[M, Connection, A]` and `ConnectionOp ~> Target` (note `Target`, not `Target[Unit]`). The type lambda is a shorthand for that
    well, it's more like we put an `?`, instead of an `_`
    so it's inconsistent (`_` means several different things in the scala type system, which is unfortunate)
    but we can do it
    `Kleisli[M, Connection, _]` is written `Kleisli[M, Connection, ?]`
    and there's your type lambda
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Okay. I got it. Just to clarify, based on my reading, that would be the same astype SomeType[A] = Kleisli[M, Connection, A], which falls neatly into the "shape" G[_].
    -----
    _____
    Fabio Labella @SystemFw
    yes, exactly
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Actually, your entire explanation from my question has made a whole lot of sense. Thank you for taking the time to do it. :grinning: I now feel I'm in a position to dig deeper into not only the fuseMap function, but also the surface-level of Doobie.
    -----
    _____
    Fabio Labella @SystemFw
    yes, `translate` is another variation of this pattern
    when you want to go from `Free[Lang1, A]` to `Free[Lang2, A]`
    so basically just change the instruction set
    `ConnectionIO` is `Free`
    fs2 `Stream` has (a lot of) extra machinery, but the basic idea is the same
    we parameterise over the effect `F`, and then in the end interpret to an `F[A]`
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Okay. I got it. Thank you so much.
    -----
    _____
    Fabio Labella @SystemFw
    no worries
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    I will revisit both fuseMap and also poke around Doobie and Scalaz-Stream.
    -----
    _____
    Fabio Labella @SystemFw
    Yes, the important thing is to grasp the key concepts:
    - A Free monad is always translated to another monad, which does the actual work
    - The process of interpretation takes a translation between instructions, and gives a translation between programs
    - You need higher-rank polymorphism (the trait trick)
    - everything follows by having things fit into the right shape
    -----
    _____
    Zizheng Tai @ZizhengTai
    Fabio you are a great teacher.
    -----
    _____
    Balaji Sivaraman @balajisivaraman
    Okay. :thumbsup:
    @ZizhengTai Indeed.
    -----
    _____
    Fabio Labella @SystemFw
    @ZizhengTai Thank you! :-)
    I will put this in a gist for future consultation, I think conversations are a great way to learn
  11. SystemFw revised this gist Aug 8, 2017. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -45,6 +45,7 @@ _Balaji Sivaraman @balajisivaraman_
    @SystemFw Apart from following the code and being taken to the natural transformation source code, not really. I also read this post (http://eed3si9n.com/learning-scalaz/Natural-Transformation.html), and got a very rudimentary idea, but the last part of that post with the Cat Theory was lost on me.

    ________

    Fabio Labella @SystemFw
    right, let's skip Cat Theory
    are you familiar with Free at all? (in code, not CT)
  12. SystemFw revised this gist Aug 8, 2017. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -38,13 +38,13 @@ ________
    _Fabio Labella @SystemFw_

    are you familiar with ~>?
    _________n
    _________

    _Balaji Sivaraman @balajisivaraman_

    @SystemFw Apart from following the code and being taken to the natural transformation source code, not really. I also read this post (http://eed3si9n.com/learning-scalaz/Natural-Transformation.html), and got a very rudimentary idea, but the last part of that post with the Cat Theory was lost on me.

    -----
    ________
    Fabio Labella @SystemFw
    right, let's skip Cat Theory
    are you familiar with Free at all? (in code, not CT)
  13. SystemFw revised this gist Aug 8, 2017. 1 changed file with 98 additions and 99 deletions.
    197 changes: 98 additions & 99 deletions Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -38,22 +38,22 @@ ________
    _Fabio Labella @SystemFw_

    are you familiar with ~>?
    _________
    _________n

    _Balaji Sivaraman @balajisivaraman _
    _Balaji Sivaraman @balajisivaraman_

    @SystemFw Apart from following the code and being taken to the natural transformation source code, not really. I also read this post (http://eed3si9n.com/learning-scalaz/Natural-Transformation.html), and got a very rudimentary idea, but the last part of that post with the Cat Theory was lost on me.

    _________
    Fabio Labella @SystemFw 10:50
    -----
    Fabio Labella @SystemFw
    right, let's skip Cat Theory
    are you familiar with Free at all? (in code, not CT)

    Balaji Sivaraman @balajisivaraman 10:54
    -----
    Balaji Sivaraman @balajisivaraman
    Have seen both Rob's presentation (https://www.youtube.com/watch?v=M5MF6M7FHPo) and Runar's (https://www.youtube.com/watch?v=M258zVn4m2M)
    , but this is my first real experience using a library with those concepts. I guess that's why I'm struggling.

    Fabio Labella @SystemFw 10:56
    -----
    Fabio Labella @SystemFw
    so, basically you have an ADT describing the instructions of your language
    ```scala
    trait KVS[A]
    @@ -67,11 +67,11 @@ note that `KVS` has higher kind, i.e. `KVS[_]`, like `Option` and `List` but unl
    `A` represents the return type of your mini program
    so `Free[Instr[_], A]` can be seen as a program written in the mini language whose primitives are described by `Instr[_]` which, when run, will eventually result in a value of type `A`
    are you with me so far?

    Balaji Sivaraman @balajisivaraman 11:01
    -----
    Balaji Sivaraman @balajisivaraman
    Yes. I'm able to follow it.

    Fabio Labella @SystemFw 11:02
    -----
    Fabio Labella @SystemFw
    cool, now you have this data structure that represents a program
    the way we run it is by interpreting it into another, more powerful data structure
    e.g. `IO`, or `Task`
    @@ -80,61 +80,61 @@ once we have this more powerful type, we can keep composing it with other `Task`
    and finally, when we're done, we call `unsafePerformSync` at the end of the world
    and things actually happen
    is this also clear?

    Balaji Sivaraman @balajisivaraman 11:05
    -----
    Balaji Sivaraman @balajisivaraman
    Yeah. Except the part with "unlimited set of instructions", I'm not sure what unlimited means here.

    Fabio Labella @SystemFw 11:06
    -----
    Fabio Labella @SystemFw
    it means that in `IO` you can do everything
    because `IO` encapsulates arbitrary side effects from the impure subset of Scala
    whereas in your own `Free` you can only do `Get` or `Put`
    it's a fairly poor metaphor, apologies

    Balaji Sivaraman @balajisivaraman 11:07
    -----
    Balaji Sivaraman @balajisivaraman
    Ok. But still limited by what `IO` and `Task` can actually do right?

    Fabio Labella @SystemFw 11:07
    -----
    Fabio Labella @SystemFw
    yes, but `IO` and `Task` can do anything Scala can do
    `Task.delay { // all scala code can fit here, e.g. println()}`

    Balaji Sivaraman @balajisivaraman 11:08
    -----
    Balaji Sivaraman @balajisivaraman
    In terms of side-effects? Now I get it.

    Fabio Labella @SystemFw 11:08
    -----
    Fabio Labella @SystemFw
    yes, albeit they are not _side_ effects, because `Task` and `IO` encapsulate them, so nothing is happening until you explicitly run them

    Balaji Sivaraman @balajisivaraman 11:08
    -----
    Balaji Sivaraman @balajisivaraman
    Ah, I'm with you so far.

    Fabio Labella @SystemFw 11:09
    -----
    Fabio Labella @SystemFw
    right, so interpreting a `Free` means going from a less powerful, but more precise language, to a more powerful but less precise language
    _Natural Transformations_ are involved in the process of interpretation
    I'm going to try to explain this interpretation in english, then we can move to code
    let's say `Instr[_]` is your ADT, and `Target[_]` is any `Monad` (we will pick Task)
    interpreting `Free` means
    "if you give me a way to translate each _instruction_ in `Instr[_]` into an instruction in `Target[_]`, I will translate each _program_ in `Free[Instr, A]` into a program in `Target[A]`"
    does this sentence make sense?

    Balaji Sivaraman @balajisivaraman 11:16
    -----
    Balaji Sivaraman @balajisivaraman
    Okay. Normally (as per the YT presentations and my understanding) when we interpret a Free program, we get something of type A (Get interpreted would give A, Put interpreted would give Unit). Now instead of that, what we're saying is we will interpret it into another target Monad (Task) and then use Task to gain additional benefits.

    Fabio Labella @SystemFw 11:17
    -----
    Fabio Labella @SystemFw
    > when we interpret a Free program, we get something of type A (
    No, that's incorrect
    a `Free monad` is always translated into another `Monad`
    the other `Monad` then does what's needed to produce an `A`
    the only exception is when some examples use `Id`, with side effects

    Balaji Sivaraman @balajisivaraman 11:18
    -----
    Balaji Sivaraman @balajisivaraman
    Okay. Thanks for the clarification. Now I get it.

    Fabio Labella @SystemFw 11:18
    -----
    Fabio Labella @SystemFw
    that's wrong, and I don't like there are so many examples of this, even on the cats website

    Balaji Sivaraman @balajisivaraman 11:18
    -----
    Balaji Sivaraman @balajisivaraman
    Ah, that's what threw me off. I'll keep it in mind going forward.

    Fabio Labella @SystemFw 11:18
    -----
    Fabio Labella @SystemFw
    cool, now let's see how the interpretation function looks in code
    yeah, but without getting too technical, that sentence in quotes above is actually what being `free` means
    anyway, the most common way to interpret a `Free` program (there are others) is through `foldMap`
    @@ -145,45 +145,45 @@ anyway, the most common way to interpret a `Free` program (there are others) is
    }
    ```
    which you should be able to reconcile with the sentence above

    Balaji Sivaraman @balajisivaraman 11:21
    -----
    Balaji Sivaraman @balajisivaraman
    The F here is Instr and the G here is Task.

    Fabio Labella @SystemFw 11:22
    -----
    Fabio Labella @SystemFw
    > if you give me a way to translate each instruction in `Instr[]` into an instruction in `Target[]`
    that's F ~> G, I'll explain more about it in a second
    >I will translate each program in Free[Instr, A]
    that's why `foldMap` is on `Free`
    > (implicit gmonad: Monad[G])
    as long as the target is a monad
    yes

    Balaji Sivaraman @balajisivaraman 11:23
    -----
    Balaji Sivaraman @balajisivaraman
    Ok, that makes sense.

    Fabio Labella @SystemFw 11:23
    -----
    Fabio Labella @SystemFw
    now the implementation of `foldMap` is not important for the end user
    what's important is why we need `~>`
    this might be a bit tricky to understand, but it's doable
    so what you want is pass to `foldMap` something that can translate each instruction in `Instr[_]` to something in `Task[_]`
    which is normally written as a pattern match
    how would you write that? any ideas?
    I'm only interested in the signature, the implementation doesn't really matter

    Balaji Sivaraman @balajisivaraman 11:27
    -----
    Balaji Sivaraman @balajisivaraman
    Just taking a shot, `def translator[A](instr: Instr[A): Task[A]`

    Fabio Labella @SystemFw 11:27
    -----
    Fabio Labella @SystemFw
    that's the most reasonable assumption, but it doesn't work
    `translator` takes a type parameter `B` (let's rename it to `B` to avoid confusing it with the `A` in `Free`)
    if you do `foldMap(translator)`
    you will need to specify the type `B` (e.g. `foldMap(translator[Int]`)
    what type do you assign to `B`, instead of the bogus `Int` I put there?

    Balaji Sivaraman @balajisivaraman 11:30
    -----
    Balaji Sivaraman @balajisivaraman
    Hmmm, my guess is we don't have one yet. We want it to work for all possible Bs, now and in the future.

    Fabio Labella @SystemFw 11:30
    -----
    Fabio Labella @SystemFw
    wow
    that's the correct answer!
    we want to pass in a _polymorphic function_
    @@ -198,15 +198,14 @@ theTranslatorYouWant: forall f g. (forall b. f b -> g b)
    ```
    which basically means

    Fabio Labella @SystemFw 11:36
    "we know what `F[_]` and `G[_]` are when we pass `translator` to `foldMap` (`Instr[_]` and `Task[_]` respectively), so we can specialise them, but we want to still be polymorphic in `B`, because only the body of `foldMap` knows how to specialise `B`"
    does this make any sense? (btw, very impressive that you came up with "Hmmm, my guess is we don't have one yet. We want it to work for all possible Bs, now and in the future.", this is a deep concept that normally takes time to sink in)
    so it should be clear I hope that just a normal function can't work as an argument to `foldMap`, because we want it to work for all possible `B`, now and in the future

    Balaji Sivaraman @balajisivaraman 11:40
    -----
    Balaji Sivaraman @balajisivaraman
    Thank you. Yes, because when we call foldMap, we won't have a specialized B. That will only come in higher up the chain when someone calls us. So when we write it, we want it to work for anything that could be passed in. Hopefully that is right.

    Fabio Labella @SystemFw 11:41
    -----
    Fabio Labella @SystemFw
    yes, it's roughly right
    the ability to pass polymorphic functions around, without losing their polymorphism
    is called _higher-rank polymorphism_
    @@ -230,22 +229,22 @@ we can then say `ourFree.foldMap(translator)`
    notice that the type of translator doesn't mention `B`, but only `Instr` and `Task`
    the apply method is still polymorphic in every `B`, so the body of `foldMap` can call it, and it'll work
    does this make sense?

    Balaji Sivaraman @balajisivaraman 11:50
    -----
    Balaji Sivaraman @balajisivaraman
    Yes. I'm with you so far. Just to clarify, within the body of foldMap, we have an A, which is basically the A of the Free. And this is the A that is applied when we call Translator.apply. Is that right?

    Fabio Labella @SystemFw 11:52
    -----
    Fabio Labella @SystemFw
    not quite
    within the body of `foldMap`, we pattern match on `Free`
    which is a program containing instructions
    so apply is called on each of the instructions, so `Get` is translated to `Task[Option[String]]`, `Put` is translated to `Task[Unit]`, and so on
    after doing this translation (this is the `map`, in `foldMap`)
    we combine them in the same way they were combined in the original program

    Balaji Sivaraman @balajisivaraman 11:55
    -----
    Balaji Sivaraman @balajisivaraman
    Okay. That makes a whole lot of sense. Thanks a lot. And the translator in our case is the Natural Transformation.

    Fabio Labella @SystemFw 11:55
    -----
    Fabio Labella @SystemFw
    exactly, `A` is the return type of the whole program
    `B` is the return type of each individual instructions, that's why we need the polymorphism
    for Category Theory reasons that are (as I hope I've proved) not necessary to understand how `Free` works to an usable extent, `Translator` is the natural transformation:
    @@ -255,65 +254,65 @@ trait ~>[F[_], G[_]] {
    }
    ```
    what is there left that confuses you in your original question?

    Balaji Sivaraman @balajisivaraman 12:00
    -----
    Balaji Sivaraman @balajisivaraman
    Nothing. I got it. (I think.) Thanks a lot. And the interpreter for Doobie is the one in transactor: ConnectionOp ~> Kleisli[M, Connection, ?]. This will translate any program in ConnectionIO to a Kleisli program. In my case, it will be a Kleisli[Task, Connection, Unit]. And when I run that, I will get a Task[Unit], which is the final output type.

    Fabio Labella @SystemFw 12:01
    -----
    Fabio Labella @SystemFw
    yes
    you need the type lambda because `G[_]` is of higher kind in `~>`: you still need to be polymorphic in `B`

    Balaji Sivaraman @balajisivaraman 12:02
    -----
    Balaji Sivaraman @balajisivaraman
    Ok. So we need that to mean Kleisli[M, Connection, _], substitute whatever type you want for the underscore. I assume this is also because of a limitation of Scala.

    Fabio Labella @SystemFw 12:03
    -----
    Fabio Labella @SystemFw
    so `Kleisli[M, Connection, Unit]` is wrong, you need type `Target[A] = Kleisli[M, Connection, A]` and `ConnectionOp ~> Target` (note `Target`, not `Target[Unit]`). The type lambda is a shorthand for that
    well, it's more like we put an `?`, instead of an `_`
    so it's inconsistent (`_` means several different things in the scala type system, which is unfortunate)
    but we can do it
    `Kleisli[M, Connection, _]` is written `Kleisli[M, Connection, ?]`
    and there's your type lambda

    Balaji Sivaraman @balajisivaraman 12:04
    -----
    Balaji Sivaraman @balajisivaraman
    Okay. I got it. Just to clarify, based on my reading, that would be the same astype SomeType[A] = Kleisli[M, Connection, A], which falls neatly into the "shape" G[_].

    Fabio Labella @SystemFw 12:04
    -----
    Fabio Labella @SystemFw
    yes, exactly

    Balaji Sivaraman @balajisivaraman 12:10
    -----
    Balaji Sivaraman @balajisivaraman
    Actually, your entire explanation from my question has made a whole lot of sense. Thank you for taking the time to do it. :grinning: I now feel I'm in a position to dig deeper into not only the fuseMap function, but also the surface-level of Doobie.

    Fabio Labella @SystemFw 12:10
    -----
    Fabio Labella @SystemFw
    yes, `translate` is another variation of this pattern
    when you want to go from `Free[Lang1, A]` to `Free[Lang2, A]`
    so basically just change the instruction set
    `ConnectionIO` is `Free`
    fs2 `Stream` has (a lot of) extra machinery, but the basic idea is the same
    we parameterise over the effect `F`, and then in the end interpret to an `F[A]`

    Balaji Sivaraman @balajisivaraman 12:15
    -----
    Balaji Sivaraman @balajisivaraman
    Okay. I got it. Thank you so much.

    Fabio Labella @SystemFw 12:15
    -----
    Fabio Labella @SystemFw
    no worries

    Balaji Sivaraman @balajisivaraman 12:16
    -----
    Balaji Sivaraman @balajisivaraman
    I will revisit both fuseMap and also poke around Doobie and Scalaz-Stream.

    Fabio Labella @SystemFw 12:18
    -----
    Fabio Labella @SystemFw
    Yes, the important thing is to grasp the key concepts:
    - A Free monad is always translated to another monad, which does the actual work
    - The process of interpretation takes a translation between instructions, and gives a translation between programs
    - You need higher-rank polymorphism (the trait trick)
    - everything follows by having things fit into the right shape

    Zizheng Tai @ZizhengTai 12:20
    -----
    Zizheng Tai @ZizhengTai
    Fabio you are a great teacher.

    Balaji Sivaraman @balajisivaraman 12:20
    -----
    Balaji Sivaraman @balajisivaraman
    Okay. :thumbsup:
    @ZizhengTai Indeed.

    Fabio Labella @SystemFw 12:21
    -----
    Fabio Labella @SystemFw
    @ZizhengTai Thank you! :-)
    I will put this in a gist for future consultation, I think conversations are a great way to learn
  14. SystemFw revised this gist Aug 8, 2017. 1 changed file with 14 additions and 4 deletions.
    18 changes: 14 additions & 4 deletions Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,5 @@
    _Balaji Sivaraman @balajisivaraman_twitter 08:22)_
    _Balaji Sivaraman @balajisivaraman_twitter_

    Hi all, I need some help understanding a piece of Doobie code from the examples. It is the StreamingCopy one: (https://github.com/tpolecat/doobie/blob/series/0.4.x/yax/example/src/main/scala/example/StreamingCopy.scala). I am using a modified version of the fuseMap2 example from that file. Here’s how I’ve modified it for my requirements:
    ```scala
    def fuseMap[F[_]: Catchable: Monad, A, B](
    @@ -21,20 +22,29 @@ Hi all, I need some help understanding a piece of Doobie code from the examples.
    ```

    Basically, I needed to use PostgresCopyManager to do Copy, instead of insert as in the example. That’s the reason for the chunking. Also I had to run a delete query as part of the same transaction. You can see the changes for this in the above code. I was able to make modifications purely by looking at the types and functions and using a bit of intuition. It works perfectly. The only problem is I have no idea why.

    My knowledge of typed FP is basic. I can grok HKTs, understand why we do Catchable: Monad etc? But type lambdas and kind projector is where my brain becomes mush. I tried splitting up the above piece of code, but that didn’t help much, because I didn’t know how to break down the entire block that is passed to apply.

    I'm still having difficulty wrapping my head around the types:
    `val exec: ~>[Kleisli[F, Connection, ?], F] = sinkXA.exec -> ` This is the type of the exec expression. So my understanding is that we need to pass something of type Kleisli[F, Connection, A] to apply or something like that. Is that the type of the expression passed in to apply? For me, it shows the type is F[Unit]. My IntelliJ is also screwing up with the types. I also don't understand this line: `translate(λ[F ~> Kleisli[F, Connection, ?]](a => Kleisli(_ => a)))`. Would appreciate help on that?

    `val exec: ~>[Kleisli[F, Connection, ?], F] = sinkXA.exec -> `

    This is the type of the exec expression. So my understanding is that we need to pass something of type Kleisli[F, Connection, A] to apply or something like that. Is that the type of the expression passed in to apply? For me, it shows the type is F[Unit]. My IntelliJ is also screwing up with the types. I also don't understand this line: `translate(λ[F ~> Kleisli[F, Connection, ?]](a => Kleisli(_ => a)))`. Would appreciate help on that?

    I read this post (http://underscore.io/blog/posts/2016/12/05/type-lambdas.html) to get a basic understanding of type lambdas, but it's not of much help here.

    ________

    Fabio Labella @SystemFw 10:46
    _Fabio Labella @SystemFw_

    are you familiar with ~>?
    _________

    Balaji Sivaraman @balajisivaraman 10:49
    _Balaji Sivaraman @balajisivaraman _

    @SystemFw Apart from following the code and being taken to the natural transformation source code, not really. I also read this post (http://eed3si9n.com/learning-scalaz/Natural-Transformation.html), and got a very rudimentary idea, but the last part of that post with the Cat Theory was lost on me.

    _________
    Fabio Labella @SystemFw 10:50
    right, let's skip Cat Theory
    are you familiar with Free at all? (in code, not CT)
  15. SystemFw revised this gist Aug 8, 2017. 1 changed file with 4 additions and 1 deletion.
    5 changes: 4 additions & 1 deletion Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,4 @@
    Balaji Sivaraman @balajisivaraman_twitter 08:22
    _Balaji Sivaraman @balajisivaraman_twitter 08:22)_
    Hi all, I need some help understanding a piece of Doobie code from the examples. It is the StreamingCopy one: (https://github.com/tpolecat/doobie/blob/series/0.4.x/yax/example/src/main/scala/example/StreamingCopy.scala). I am using a modified version of the fuseMap2 example from that file. Here’s how I’ve modified it for my requirements:
    ```scala
    def fuseMap[F[_]: Catchable: Monad, A, B](
    @@ -26,8 +26,11 @@ I'm still having difficulty wrapping my head around the types:
    `val exec: ~>[Kleisli[F, Connection, ?], F] = sinkXA.exec -> ` This is the type of the exec expression. So my understanding is that we need to pass something of type Kleisli[F, Connection, A] to apply or something like that. Is that the type of the expression passed in to apply? For me, it shows the type is F[Unit]. My IntelliJ is also screwing up with the types. I also don't understand this line: `translate(λ[F ~> Kleisli[F, Connection, ?]](a => Kleisli(_ => a)))`. Would appreciate help on that?
    I read this post (http://underscore.io/blog/posts/2016/12/05/type-lambdas.html) to get a basic understanding of type lambdas, but it's not of much help here.

    ________

    Fabio Labella @SystemFw 10:46
    are you familiar with ~>?
    _________

    Balaji Sivaraman @balajisivaraman 10:49
    @SystemFw Apart from following the code and being taken to the natural transformation source code, not really. I also read this post (http://eed3si9n.com/learning-scalaz/Natural-Transformation.html), and got a very rudimentary idea, but the last part of that post with the Cat Theory was lost on me.
  16. SystemFw created this gist Aug 8, 2017.
    306 changes: 306 additions & 0 deletions Free conversation.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,306 @@
    Balaji Sivaraman @balajisivaraman_twitter 08:22
    Hi all, I need some help understanding a piece of Doobie code from the examples. It is the StreamingCopy one: (https://github.com/tpolecat/doobie/blob/series/0.4.x/yax/example/src/main/scala/example/StreamingCopy.scala). I am using a modified version of the fuseMap2 example from that file. Here’s how I’ve modified it for my requirements:
    ```scala
    def fuseMap[F[_]: Catchable: Monad, A, B](
    source: Process[ConnectionIO, A],
    sink: Vector[A] => ConnectionIO[B],
    delete: ConnectionIO[Unit]
    )(
    sourceXA: Transactor[F],
    sinkXA: Transactor[F]
    ): F[Unit] =
    sinkXA.exec.apply(
    source
    .transact(sourceXA)
    .chunk(10000)
    .translate(λ[F ~> Kleisli[F, Connection, ?]](a => Kleisli(_ => a)))
    .evalMap(sink(_).foldMap(sinkXA.interpret))
    .append(Process.eval_(delete.foldMap(sinkXA.interpret)))
    .run
    )
    ```

    Basically, I needed to use PostgresCopyManager to do Copy, instead of insert as in the example. That’s the reason for the chunking. Also I had to run a delete query as part of the same transaction. You can see the changes for this in the above code. I was able to make modifications purely by looking at the types and functions and using a bit of intuition. It works perfectly. The only problem is I have no idea why.
    My knowledge of typed FP is basic. I can grok HKTs, understand why we do Catchable: Monad etc? But type lambdas and kind projector is where my brain becomes mush. I tried splitting up the above piece of code, but that didn’t help much, because I didn’t know how to break down the entire block that is passed to apply.
    I'm still having difficulty wrapping my head around the types:
    `val exec: ~>[Kleisli[F, Connection, ?], F] = sinkXA.exec -> ` This is the type of the exec expression. So my understanding is that we need to pass something of type Kleisli[F, Connection, A] to apply or something like that. Is that the type of the expression passed in to apply? For me, it shows the type is F[Unit]. My IntelliJ is also screwing up with the types. I also don't understand this line: `translate(λ[F ~> Kleisli[F, Connection, ?]](a => Kleisli(_ => a)))`. Would appreciate help on that?
    I read this post (http://underscore.io/blog/posts/2016/12/05/type-lambdas.html) to get a basic understanding of type lambdas, but it's not of much help here.

    Fabio Labella @SystemFw 10:46
    are you familiar with ~>?

    Balaji Sivaraman @balajisivaraman 10:49
    @SystemFw Apart from following the code and being taken to the natural transformation source code, not really. I also read this post (http://eed3si9n.com/learning-scalaz/Natural-Transformation.html), and got a very rudimentary idea, but the last part of that post with the Cat Theory was lost on me.

    Fabio Labella @SystemFw 10:50
    right, let's skip Cat Theory
    are you familiar with Free at all? (in code, not CT)

    Balaji Sivaraman @balajisivaraman 10:54
    Have seen both Rob's presentation (https://www.youtube.com/watch?v=M5MF6M7FHPo) and Runar's (https://www.youtube.com/watch?v=M258zVn4m2M)
    , but this is my first real experience using a library with those concepts. I guess that's why I'm struggling.

    Fabio Labella @SystemFw 10:56
    so, basically you have an ADT describing the instructions of your language
    ```scala
    trait KVS[A]
    case class Get(k: String) extends KVS[Option[String]]
    case class Put(k: String, v: String) extends KVS[Unit]
    ```
    note that `KVS` has higher kind, i.e. `KVS[_]`, like `Option` and `List` but unlike `Int`
    `Free` represent a description of a program, and it takes two type parameters
    `Free[Instr[_], A]`
    `Instr[_]` is your ADT, it represents the individual instructions in your mini language. It needs to be `[_]` so that we can express the fact that each instruction returns a different type (e.g. `Option[String]` for `Get`, `Unit` for `Put`)
    `A` represents the return type of your mini program
    so `Free[Instr[_], A]` can be seen as a program written in the mini language whose primitives are described by `Instr[_]` which, when run, will eventually result in a value of type `A`
    are you with me so far?

    Balaji Sivaraman @balajisivaraman 11:01
    Yes. I'm able to follow it.

    Fabio Labella @SystemFw 11:02
    cool, now you have this data structure that represents a program
    the way we run it is by interpreting it into another, more powerful data structure
    e.g. `IO`, or `Task`
    which you can look at as a `Free` with an unlimited set of instructions
    once we have this more powerful type, we can keep composing it with other `Task` (let's pick `Task` for now)
    and finally, when we're done, we call `unsafePerformSync` at the end of the world
    and things actually happen
    is this also clear?

    Balaji Sivaraman @balajisivaraman 11:05
    Yeah. Except the part with "unlimited set of instructions", I'm not sure what unlimited means here.

    Fabio Labella @SystemFw 11:06
    it means that in `IO` you can do everything
    because `IO` encapsulates arbitrary side effects from the impure subset of Scala
    whereas in your own `Free` you can only do `Get` or `Put`
    it's a fairly poor metaphor, apologies

    Balaji Sivaraman @balajisivaraman 11:07
    Ok. But still limited by what `IO` and `Task` can actually do right?

    Fabio Labella @SystemFw 11:07
    yes, but `IO` and `Task` can do anything Scala can do
    `Task.delay { // all scala code can fit here, e.g. println()}`

    Balaji Sivaraman @balajisivaraman 11:08
    In terms of side-effects? Now I get it.

    Fabio Labella @SystemFw 11:08
    yes, albeit they are not _side_ effects, because `Task` and `IO` encapsulate them, so nothing is happening until you explicitly run them

    Balaji Sivaraman @balajisivaraman 11:08
    Ah, I'm with you so far.

    Fabio Labella @SystemFw 11:09
    right, so interpreting a `Free` means going from a less powerful, but more precise language, to a more powerful but less precise language
    _Natural Transformations_ are involved in the process of interpretation
    I'm going to try to explain this interpretation in english, then we can move to code
    let's say `Instr[_]` is your ADT, and `Target[_]` is any `Monad` (we will pick Task)
    interpreting `Free` means
    "if you give me a way to translate each _instruction_ in `Instr[_]` into an instruction in `Target[_]`, I will translate each _program_ in `Free[Instr, A]` into a program in `Target[A]`"
    does this sentence make sense?

    Balaji Sivaraman @balajisivaraman 11:16
    Okay. Normally (as per the YT presentations and my understanding) when we interpret a Free program, we get something of type A (Get interpreted would give A, Put interpreted would give Unit). Now instead of that, what we're saying is we will interpret it into another target Monad (Task) and then use Task to gain additional benefits.

    Fabio Labella @SystemFw 11:17
    > when we interpret a Free program, we get something of type A (
    No, that's incorrect
    a `Free monad` is always translated into another `Monad`
    the other `Monad` then does what's needed to produce an `A`
    the only exception is when some examples use `Id`, with side effects

    Balaji Sivaraman @balajisivaraman 11:18
    Okay. Thanks for the clarification. Now I get it.

    Fabio Labella @SystemFw 11:18
    that's wrong, and I don't like there are so many examples of this, even on the cats website

    Balaji Sivaraman @balajisivaraman 11:18
    Ah, that's what threw me off. I'll keep it in mind going forward.

    Fabio Labella @SystemFw 11:18
    cool, now let's see how the interpretation function looks in code
    yeah, but without getting too technical, that sentence in quotes above is actually what being `free` means
    anyway, the most common way to interpret a `Free` program (there are others) is through `foldMap`
    ```scala
    trait Free[F[_], A] {
    //...
    def foldMap[G](translator: F ~> G)(implicit gmonad: Monad[G]): G[A] = ???
    }
    ```
    which you should be able to reconcile with the sentence above

    Balaji Sivaraman @balajisivaraman 11:21
    The F here is Instr and the G here is Task.

    Fabio Labella @SystemFw 11:22
    > if you give me a way to translate each instruction in `Instr[]` into an instruction in `Target[]`
    that's F ~> G, I'll explain more about it in a second
    >I will translate each program in Free[Instr, A]
    that's why `foldMap` is on `Free`
    > (implicit gmonad: Monad[G])
    as long as the target is a monad
    yes

    Balaji Sivaraman @balajisivaraman 11:23
    Ok, that makes sense.

    Fabio Labella @SystemFw 11:23
    now the implementation of `foldMap` is not important for the end user
    what's important is why we need `~>`
    this might be a bit tricky to understand, but it's doable
    so what you want is pass to `foldMap` something that can translate each instruction in `Instr[_]` to something in `Task[_]`
    which is normally written as a pattern match
    how would you write that? any ideas?
    I'm only interested in the signature, the implementation doesn't really matter

    Balaji Sivaraman @balajisivaraman 11:27
    Just taking a shot, `def translator[A](instr: Instr[A): Task[A]`

    Fabio Labella @SystemFw 11:27
    that's the most reasonable assumption, but it doesn't work
    `translator` takes a type parameter `B` (let's rename it to `B` to avoid confusing it with the `A` in `Free`)
    if you do `foldMap(translator)`
    you will need to specify the type `B` (e.g. `foldMap(translator[Int]`)
    what type do you assign to `B`, instead of the bogus `Int` I put there?

    Balaji Sivaraman @balajisivaraman 11:30
    Hmmm, my guess is we don't have one yet. We want it to work for all possible Bs, now and in the future.

    Fabio Labella @SystemFw 11:30
    wow
    that's the correct answer!
    we want to pass in a _polymorphic function_
    so when we pass `translator`, we want to keep its polymorphism
    because we will only specialise once we have a specific instruction
    this difference can be made specific in types, but scala doesn't give you a nice notation for it
    I'm going to write it in Haskell for a second, but it should be ok:
    ```haskell
    theTranslatorYouHave :: forall f g b. (f b -> g b) -- f b = Instr[B], g b = Task[B]

    theTranslatorYouWant: forall f g. (forall b. f b -> g b)
    ```
    which basically means

    Fabio Labella @SystemFw 11:36
    "we know what `F[_]` and `G[_]` are when we pass `translator` to `foldMap` (`Instr[_]` and `Task[_]` respectively), so we can specialise them, but we want to still be polymorphic in `B`, because only the body of `foldMap` knows how to specialise `B`"
    does this make any sense? (btw, very impressive that you came up with "Hmmm, my guess is we don't have one yet. We want it to work for all possible Bs, now and in the future.", this is a deep concept that normally takes time to sink in)
    so it should be clear I hope that just a normal function can't work as an argument to `foldMap`, because we want it to work for all possible `B`, now and in the future

    Balaji Sivaraman @balajisivaraman 11:40
    Thank you. Yes, because when we call foldMap, we won't have a specialized B. That will only come in higher up the chain when someone calls us. So when we write it, we want it to work for anything that could be passed in. Hopefully that is right.

    Fabio Labella @SystemFw 11:41
    yes, it's roughly right
    the ability to pass polymorphic functions around, without losing their polymorphism
    is called _higher-rank polymorphism_
    scala does not have such a feature
    however, we can work our way around it
    let's create a trait
    ```scala
    trait Translator[F[_], G[_]] {
    def apply[B](in: F[B]): G[B]
    }
    ```
    now we can write
    ```scala
    def translator: Translator[Instr, Task] = new Translator[Instr, Task] {
    def apply[B](in: Instr[B]): Task[B] = in match {
    case Put(k, v) => Task.delay (DB.put(k, v))
    case Get(k) => Task.delay(DB.get(k))
    }
    ```
    we can then say `ourFree.foldMap(translator)`
    notice that the type of translator doesn't mention `B`, but only `Instr` and `Task`
    the apply method is still polymorphic in every `B`, so the body of `foldMap` can call it, and it'll work
    does this make sense?

    Balaji Sivaraman @balajisivaraman 11:50
    Yes. I'm with you so far. Just to clarify, within the body of foldMap, we have an A, which is basically the A of the Free. And this is the A that is applied when we call Translator.apply. Is that right?

    Fabio Labella @SystemFw 11:52
    not quite
    within the body of `foldMap`, we pattern match on `Free`
    which is a program containing instructions
    so apply is called on each of the instructions, so `Get` is translated to `Task[Option[String]]`, `Put` is translated to `Task[Unit]`, and so on
    after doing this translation (this is the `map`, in `foldMap`)
    we combine them in the same way they were combined in the original program

    Balaji Sivaraman @balajisivaraman 11:55
    Okay. That makes a whole lot of sense. Thanks a lot. And the translator in our case is the Natural Transformation.

    Fabio Labella @SystemFw 11:55
    exactly, `A` is the return type of the whole program
    `B` is the return type of each individual instructions, that's why we need the polymorphism
    for Category Theory reasons that are (as I hope I've proved) not necessary to understand how `Free` works to an usable extent, `Translator` is the natural transformation:
    ```scala
    trait ~>[F[_], G[_]] {
    def apply[A](f: F[A]): F[B]
    }
    ```
    what is there left that confuses you in your original question?

    Balaji Sivaraman @balajisivaraman 12:00
    Nothing. I got it. (I think.) Thanks a lot. And the interpreter for Doobie is the one in transactor: ConnectionOp ~> Kleisli[M, Connection, ?]. This will translate any program in ConnectionIO to a Kleisli program. In my case, it will be a Kleisli[Task, Connection, Unit]. And when I run that, I will get a Task[Unit], which is the final output type.

    Fabio Labella @SystemFw 12:01
    yes
    you need the type lambda because `G[_]` is of higher kind in `~>`: you still need to be polymorphic in `B`

    Balaji Sivaraman @balajisivaraman 12:02
    Ok. So we need that to mean Kleisli[M, Connection, _], substitute whatever type you want for the underscore. I assume this is also because of a limitation of Scala.

    Fabio Labella @SystemFw 12:03
    so `Kleisli[M, Connection, Unit]` is wrong, you need type `Target[A] = Kleisli[M, Connection, A]` and `ConnectionOp ~> Target` (note `Target`, not `Target[Unit]`). The type lambda is a shorthand for that
    well, it's more like we put an `?`, instead of an `_`
    so it's inconsistent (`_` means several different things in the scala type system, which is unfortunate)
    but we can do it
    `Kleisli[M, Connection, _]` is written `Kleisli[M, Connection, ?]`
    and there's your type lambda

    Balaji Sivaraman @balajisivaraman 12:04
    Okay. I got it. Just to clarify, based on my reading, that would be the same astype SomeType[A] = Kleisli[M, Connection, A], which falls neatly into the "shape" G[_].

    Fabio Labella @SystemFw 12:04
    yes, exactly

    Balaji Sivaraman @balajisivaraman 12:10
    Actually, your entire explanation from my question has made a whole lot of sense. Thank you for taking the time to do it. :grinning: I now feel I'm in a position to dig deeper into not only the fuseMap function, but also the surface-level of Doobie.

    Fabio Labella @SystemFw 12:10
    yes, `translate` is another variation of this pattern
    when you want to go from `Free[Lang1, A]` to `Free[Lang2, A]`
    so basically just change the instruction set
    `ConnectionIO` is `Free`
    fs2 `Stream` has (a lot of) extra machinery, but the basic idea is the same
    we parameterise over the effect `F`, and then in the end interpret to an `F[A]`

    Balaji Sivaraman @balajisivaraman 12:15
    Okay. I got it. Thank you so much.

    Fabio Labella @SystemFw 12:15
    no worries

    Balaji Sivaraman @balajisivaraman 12:16
    I will revisit both fuseMap and also poke around Doobie and Scalaz-Stream.

    Fabio Labella @SystemFw 12:18
    Yes, the important thing is to grasp the key concepts:
    - A Free monad is always translated to another monad, which does the actual work
    - The process of interpretation takes a translation between instructions, and gives a translation between programs
    - You need higher-rank polymorphism (the trait trick)
    - everything follows by having things fit into the right shape

    Zizheng Tai @ZizhengTai 12:20
    Fabio you are a great teacher.

    Balaji Sivaraman @balajisivaraman 12:20
    Okay. :thumbsup:
    @ZizhengTai Indeed.

    Fabio Labella @SystemFw 12:21
    @ZizhengTai Thank you! :-)
    I will put this in a gist for future consultation, I think conversations are a great way to learn