https://kotlinlang.org logo
Join Slack
Powered by
Can someone give me a minimal example for Free (PU...
# arrow
i
Can someone give me a minimal example for Free (PUN intended)?
j
The overused console example is what I had around to test some stuff with recursion-schemes and Free. I don't have a good example for transform sry 😕 Maybe you can describe what you want to solve with Free and that'll lead to an example.
Copy code
@higherkind
sealed class ConsoleF<A> : ConsoleFOf<A> {
  /**
   * Actions together with a continuation pattern
   */
  data class GetLine<A>(val cont: (String) -> A) : ConsoleF<A>()
  data class PutStrLn<A>(val str: String, val cont: A) : ConsoleF<A>()

  fun <B> map(f: (A) -> B): ConsoleF<B> = when (this) {
    is GetLine -> GetLine(cont andThen f)
    is PutStrLn -> PutStrLn(str, f(cont))
  }

  /**
   * Inherit from FreeMonad to make life easier later
   */
  companion object : FreeMonad<ForConsoleF> {
    /**
     * Normally this would be defined with @extension, but that only works if its not in the same module
     *  as @higherkind for the datatype
     */
    fun functor() = object : Functor<ForConsoleF> {
      override fun <A, B> Kind<ForConsoleF, A>.map(f: (A) -> B): Kind<ForConsoleF, B> = fix().map(f)
    }

    /**
     * Smart constructors to make life easier
     */
    fun getLine() = Free.liftF(GetLine(::identity))
    fun putStrLn(str: String) = Free.liftF(PutStrLn(str, Unit))
  }
}

/**
 * Our program using the inherited features from the companion object to get access to binding
 */
val prog = ConsoleF.binding {
  !putStrLn("What is your name?")
  val (input) = getLine()
  !putStrLn("Hello $input")
}.fix()

fun main() {
  /**
   * This is interpret with recursion-schemes, its in an active pr for recursion-schemes and only here cause I
   *  needed to test if monadic actions were supported properly so you can ignore this for now :)
   */
  prog.interpret(ConsoleF.functor(), { IO.unit }) {
    when (val fa = it.fix()) {
      is ConsoleF.GetLine -> Eval.later {
        IO {
          readLine()!!
        }.flatMap { fa.cont(it).value() }
      }
      is ConsoleF.PutStrLn -> Eval.later {
        IO { println(fa.str) }.flatMap { fa.cont.value() }
      }
    }
  }.unsafeRunSync()

  /**
   * Interpret our progam in IO
   */
  prog.foldMap(
    object : FunctionK<ForConsoleF, ForIO> {
      override fun <A> invoke(fa: Kind<ForConsoleF, A>): Kind<ForIO, A> = when (val fa = fa.fix()) {
        is ConsoleF.GetLine -> IO {
          readLine()!!
        }.map(fa.cont)
        is ConsoleF.PutStrLn -> IO {
          println(fa.str)
          fa.cont
        }
      }
    },
    IO.monad()
  ).fix().unsafeRunSync()
}
👍 1
i
ok, not so minimal at all. So basically I want to see if I can rap a list into a free and get a Monad.
Copy code
kotlin
fun Free<ListK<Int>, Int>.hello() =
    transform(
        { it * 2 },
        fs = // requirs a FunctionK
    )
I actually don’t find anything understandable for FunctionK only this snippet, but I don’t understand it.
Copy code
kotlin
val cofreeOptionToNel: FunctionK<CofreePartialOf<ForOption>, ForNonEmptyList> = object : FunctionK<CofreePartialOf<ForOption>, ForNonEmptyList> {
  override fun <A> invoke(fa: Kind<CofreePartialOf<ForOption>, A>): Kind<ForNonEmptyList, A> =
    fa.fix().let { c ->
      NonEmptyList.fromListUnsafe(listOf(c.head) + c.tailForced().fix().fold({ listOf<A>() }, { invoke(it).fix().all }))
    }
}
j
First of, the first type argument for free needs to be a higherkinded type (e.g 
ForListK
in your case). Second: To get a 
Kind<F, A>
into a free monad use 
Free.liftF
. Lastly a 
FunctionK
is just a natural transformation of a 
Kind<F, A>
to a 
Kind<G, A>
. If you want to keep it as a list just use 
FunctionK.id()
. The below example really states that using this function one can convert all `Cofree<ForOption, A>`'s to `Nel<A>. What do you intend to use 
Free
for? If you just want monadic operations over a list then you can simply use the list monad instead.
i
But what is S exactly for instance i define this
Copy code
kotlin
val intListFree = 4.free<ForListK, Int>().hello()

fun Free<ForListK, Int>.hello() =
    transform(
        { it * 2 },
        fs = FunctionK.id()// requirs a FunctionK
    )
compared to this
Copy code
kotlin
val b = listOf(4).k()
        .free()
Which resolves to a Free<Any?, ListK<Int>>
Or to put it differently how can I use FunctionK to go from a Functor F to G
j
S
is the Functor that Free needs, if you do 
.free
(which I did not even know exists) it's going to do 
Free.just
which makes no assumptions about 
S
. The importance is clear when you want to interpret a 
Free<S, A>
because you will need a natural transformation over 
S
. https://typelevel.org/cats/datatypes/freemonad.html does a good job at explaining what 
Free
can and should be used for, https://medium.com/@olxc/free-monads-explained-pt-1-a5c45fbdac30 is a good read about where free comes from and how it works. Some vocab before: In arrow a natural transformation is simply a FunctionK and another thing: I hate the cats approach to free monads because they require a monad instance when interpreting which is not necessary at all (but the examples and docs are good)
i
What do I need to do If I want to change it for example to a ForOption
j
What is it in this case? Free? In any case if you want to convert something via a 
FunctionK
you need to provide the conversion method. I am a bit confused with what you are trying to do 🙈
r
The arrow tests for Free have some simple ADTs
In Free you go from F to G where F is your ADT and G is your target monad. And the way you go there is via 
foldMap
and 
FunctionK
, that is how Free programs are interepreted
j
@raulraja we should change that when the recursion scheme pr is in. It can eval an adt without a monad instance, is still stacksafe and operates on a simple algebra instead of the unsafe mess that is foldmap. Also the example in arrow test is misleading as free usually requires a functor instance and adder cannot provide one. All in all the free lib could use a small face-lift because it can actually be quite usable (and type safe if your datatype is a functor). I think I'll put some work into it when recursion schemes are done.
i
Let’s also work on a Free Doc for the arrow page. I still don’t get it, but let me sleep over it. I will do the PR on the Free Docs. I need both of you to review it later on 🙂 @raulraja @Jannis
👍 1
r
Can't all GADTs provide a functor instance?
Free bakes in the coyoneda trick in Scala and Kotlin
you don't need Functor explictly to go from the ADT to the target F
The issue with Free in Kotlin in general is that you can't easily mix different GADTs so it's not useful
j
Well partially, you still at some point need a functor, either way with an explicit functor it is much easier as you don't have to typecast stuff to a all the time. (Although I need to look into yoneda and coyoneda more).
r
No Coproduct + Inject like in data types a la carte trick
and Coproduct is extremely slow when you nest algebras
interpreters need to be optimized like we had to do in Freestyle
j
That only affects coproducts for now, which can be done at some point. Inject can be done as well because we can inject every Free<F, A> into a Free<CoproductPartial<F, *>, A>. I think a lot can be done to make the api nicer. And again if you define your adt like a pattern functor you get type-safety back.
r
Coproduct ends up in memory like a linked list with all the noeds hanging in one side so acessing the algebra in the coproduct becomes slower as the number of ADTs increase
j
The coproduct optimizations is something interesting to do but before I think free should be somewhat friendlier
r
totally
don;t get me wrong, I'm all for those improvements
just stating the poor state of affairs with Free
the first thing I'd fix is the kotlin compiler
j
haha
r
there is no reason it can't infer 
A
and forces you to cast it in all FunctionK
j
well I think it's not really needed to model it like that. Given a pattern functor on your adt you get all typesafety back in an instant and its little to no more boilerplate
r
sounds good
are we gonna codegen those automatically?
the idea for recursion schemes is to get some of the features from Droste
Droste autogenerates functor, traverse, algebras and coalgebras for any ADT including the pattern representation
so activating recursion schemes over algebras becomes as easy as optics in arrow
i
Do you have a link to Droste ?
r
you get a full featured API from all those type classes automatically
j
I literally just discovered droste! I want to implement the gather/scatter for generalized folds (which I deleted from the pr because the implementation is based on ed kmetts recursion schemes and they are broken there)
👍🏽 1
r
we maintain droste with Andy in the higherkindness org
many people at 47 are involved
i
I am in, too
r
@andyscott ping!
j
Auto-deriving functors (and other instances) would be a nice quality of life upgrade. But I think what would be even better (for arrow) is auto generating inject typeclass instances to generate smart constructors because we can't use nice stuff like implicits to do so. That is also trivially easy given a type of nested Free<CoproductPartials>
Well not smart constructors but at least an easy way to generate Free<Coproduct> instances regardless of nesting, order and completely invisible from the user, which should be possible
r
It should also be possible with the actual new Coproduct data type in generic instead of the one in extras
If we make a kinded version for it or similar
fold
in that one is efficient unlike the other one which forces you to nest to the right
j
my slack reminder list that I am using as a todo is getting scary long 😄 so many things to read and try. What I think would be ideal is to have a 
binding
in which I can use any 
Free<F, A>
, I predefine a typealias 
= Free<Coproduct...>
and with some annotation magic I get back a 
binding
of some sort that defines bind for all 
Free<F, A>
and just injects to 
Coproduct
and binds with normal bind. I have done that already on one layer (manually) and I think adding layers to it should be possible programmatically
Then integrating more algebras becomes a piece of cake, no need for smart constructors apart from the one lifting to Free<F, A> and no existing programs need a change apart from the interpreter
r
all that is good the issue is that Free is just monad
it can't easily suspend effects or interpret itself recursively
We have a better Free already FreeC that can also do error handling
so in all it's interesting as machinery but as a data type to compose apps it's never gonna beat in performance Tagless encodings
but it's awesome if we improve its current state
j
well the point of free is to reify effects in an adt and then interpret them in some effectful manner if I understood that correctly. Also I'd argue that depending on what you are doing performance should not be the nr1 concern and free offers some nice benefits there. Although I would like to go the opposite direction not in a more powerful monad, but more towards FreeAp and FreeSelective and see where that leads to. But thats a bit off. Also iirc there are some attempts that make Free much faster, but then again I think its probably fast enough for most cases.
r
yeah what I mean is that the JVM is a different monster and to do any effect suspension you need MonadDefer or up and Free on its own can't do any of it so you start packing different things like FreeApplicative etc as data types
at the end they all expose a small piece of IO
but IO is currently the only capable data type that can actually suspend effects
Free only can if you define an additional algebra for it that takes suspend functions
not a limitation what I'm saying is that I learn that Free in practice has a lot of limitations
because the ADT it has traditionally been built around is not too capable
but if we can break it down and make it more ergonomic then awesome
IO internally and Streams are also Free monads
j
Aren't streams usually modeled with cofree? That feels more intuitive for me. Also what effects would a program need to suspend if all its computation is reified as Free?
r
yeah I mean they are modeled with a Free like ADT
@Jannis for example how would you implement 
raiseError
or 
handleErrorWith
with Free monads?
even if expressed there as tagless it's ment to be similar to MonadError
but it can't implement most of its combinators because Free lacks errors in its ADT
similarly there is the question when an algebra in Free needs to take another Free program as argument
j
I either wouldn't (use explicit returns like Either), use FreeT and let the underlying monad handle that or encode that in adts (which is pretty awful)
r
how does that interpretation happen so you can implement functions like 
handleErrorWith
?
not trying to challenge just remembering all the wholes I ended up digging with this stuff
j
I think FreeT is the best choice here for handling errors if you don't want explicit Either's around
Nah thinking about these things is important to see where flaws are and what improvements can be made! 🙂
About taking another Free program as arguments. That is trivial as long as the F in there is injectable to the G that the current program runs in. Idk how much of a constraint that is tho
i
It would be great, if someone creates an issue, with some instructions, how we could potentially improve the existing Free.
j
I'll compile this into a list and put one up over the next few days
👏 2
8 Views
Open in Slack
PreviousNext
Powered by