Where communities thrive

  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
Repo info
Raphael M├Ąder
Yes, from the Specs2 library. I'll read about type erasure, maybe I can find something. Thanks for the hint.
Harrison Houghton
Also, what is PageRepository?
If you're writing code that's parameterized over an arbitrary effect type, often you can make testing easier by replacing the effect with a less general one.
Alexandru Nedelcu
Hi folks, I need the Cats logo. Where can I find it?
Ian Macalinao
Can .map still be used on something with a Functor typeclass instance? Or do I need special imports for that syntax to work?
I'm no longer able to .map over something but if I do functor.map(thing)(fn) it compiles
Rob Norris
What is the type of thing and what cats imports do you have?
Normally you want cats.implicits._ and you want to compile with -Ypartial-unification
To get all the syntax
Fabio Labella
crucially, if you have cats.implicits._, you don't want to have any other implicit imports like syntax or instances @macalinao
Anatolii Kmetiuk

Hi all!

Can anyone explain me how Cats' Free Monad compares to Haskell's one?

Both in Scala and Haskell we seem to have Free programs as ASTs structures stored in memory during the runtime and executed by a separate instruction, usually involving an interpreter.

In Haskell, taking examples here, in order to run the free program, we appear to pass it to an interpreter function directly: one (interpreter is runGame), two (runWeb interpreter). In Scala, we need usually execute by calling a pre-defined interpret with the program and the interpreter, framework style.

In Haskell, the interpreters match on reifications of monad's methods: one, two (I am not very familiar with Haskell, but Return and :>>= look very much like their Pure and FlatMapped counterparts from Scala, correct me if I am wrong here). In Scala, it is in principle impossible to write an interpreter aware of these reifications, since they are private in Cats' implementation.

The Haskell versions make a lot of sense: you are able to define the semantics of the execution of the sequence of monadic method calls. In Cats, this semantics is pre-defined and final, and the emphasis is made on the semantics of individual statements. However, in the official tutorial, you can have the def program: KVStore[Option[Int]] = ... with the flexibility in put, update etc without free monads:

def program[F[_]: Monad](implicit ops: KvOps[F]) =
  for {
    _ <- ops.put("wild-cats", 2)
    _ <- ops.update[Int]("wild-cats", (_ + 12))

Where ops contains the same info as the interpreter, namely the implementation of the domain-specific methods. By switching F and the implicit parameter, you can execute the same program against many backends, with the same type safety as we had with free monads.

E.g. def impureCompiler: KVStoreA ~> Id = ... becomes:

implicit object IdOps extends KvOps[Id] {

  val kvs = mutable.Map.empty[String, Any]

  def put(k, v) = ...

Much less hassle, same effect (inspired by frees.io patterns).

My question is the following: is not the main power of a Free structure in that you are able to treat the sequence of monadic ops as a structure, and hence have perfect control on how to execute the structure? Is this not how Haskell does this (again, not very familiar with it, so I can be wrong here)? If so, why is the execution logic in Cats final, and the reification classes - private?

Fabio Labella
@anatoliykmetyuk You are looking at operational in Haskell, which is actually closer to Scala's version of Free than to the basic Haskell version
the reason I'm mentioning this is that in operational you are not actually pattern matching on the structure (which is private there as well)
but on a "view" over it
and you can do the same with cats Free, using fold
Fabio Labella
however, in both cases, most of the time your interpretation pattern is the one defined in cats foldMap or compile, hence why most of the examples are expressed using those
in the second part of your example, you are using final tagless style, which is also a great choice (and my preferred approach)
Anatolii Kmetiuk
Is it possible to use fold outside the free package though? Seen that the free classes are private.
Fabio Labella
yes, because fold takes as input the two functions representing the bodies of your two cases pattern matches
notice I said two cases, but the actual classes are more than two
this is a common technique: "morally", free has only two cases (Pure and Roll), but the implementation has more for implementation reasons (stack safety)
btw, with operational is the same: the pattern matches you see there are actually pattern synonyms, the actual data structure is different (and law breaking), so we expose a safe "view" over it
Anatolii Kmetiuk
Roll? I can't see it defined here.
Fabio Labella
so the very basic definition of Free is this data Free f a = Pure a | Roll (f (Free f a))
there are two cases, either the computation is terminating with a pure value, or there is another monadic layer
Anatolii Kmetiuk
Can FlatMapped be expressed in terms of these two only?
Fabio Labella
yes, but the usage of this version is less nice
in particular, you need a Functor instance for your data type
it all comes down to the fact that we can express the monad typeclass in two ways (I'm ignoring applicative for a second)
class Monad m where
    pure :: a -> m a
     (>>=) :: m a -> (a -> m b) -> m b
trait Monad[M[_]] {
   def pure[A](a: A): M[A]
   def flatMap[A, B](ma: M[A])(k: A => M[B]): M[B]
class (Functor m) => Monad m where
   pure :: a -> m a
   join :: m (m a) -> m a
trait Monad[M[_] extends Functor[M] {
    def pure[A](a: A): M[A]
    def flatten[A](mma: M[M[A]]):  M[A]
these two are perfectly equivalent
Fabio Labella
the original, simpler free is derived from this latter version, whereas operational (and cats Free) are from the first version
the advantage is that you don't need a Functor instance for your ADT, and that you don't need an extra parameter for your data types representing the next step in the computation
in more technical terms, operational and cats Free are said to be Free over Coyoneda
Anatolii Kmetiuk
So the trick here is that we can pass an A => F[B] to map and then flatten? Ok, let's ignore the uglier Free for a moment, seen that operational and Free are similar. I can't see how Scala version exposes the views of its program, yet it seems crucial to implement TicTacToe turn sequence: https://github.com/HeinrichApfelmus/operational/blob/master/doc/examples/TicTacToe.hs#L51
How would you interpret two free programs in an orderly interleaving fashion without the access to the FlatMapped etc or their views (btw how these are different?)
As far as I can see, the key statement here is this: https://github.com/HeinrichApfelmus/operational/blob/master/doc/examples/TicTacToe.hs#L67 - notice how in all cases p1 (player 1) is passed prior to p2, except for this line
I suspect that's how they interleave these two programs
Fabio Labella

btw how these are different?

in operational, they are different because the raw data structure can be used to break the monad laws, but the view (ProgramViewT) cannot.
In cats, they are different because the machinery for stack safety (Suspend and FlatMapped) is hidden from the user

the example you posted with TicTacToe is complicated by the fact that it's actually not just Free, but a Free monad tranformer over IO
in cats, that would be FreeT
anyway you can use fold (on cats Free), and resume(on FreeT) to have the equivalent of pattern matching
Anatolii Kmetiuk

because the machinery for stack safety

So the main point of Free in Cats is stack safety when doing many flatMaps?

anyway you can use fold (on cats Free), and resume(on FreeT) to have the equivalent of pattern matching

How would you do that? You can't match on FlatMapped, yet this is what they do in operational (I assume :>>= contains the same info as FlatMapped, right?)

Fabio Labella
i.e. some code that takes blocks corresponding to the two Free monad cases (in operational these are Return and :>>=) and applies the right one
you use fold instead of matching