## Where communities thrive

• Join over 1.5M+ people
• Join over 100K+ communities
• Free without limits
##### Activity
Fabio Labella
@SystemFw
then I'd only focus on Coyoneda, and in particular around foldMap
by favourite explanation of free structure is in terms of abstract algebra, not category theory, in particular about the universal property, which is exactly what foldMap is
e.g. look at foldMap on List, Coyoneda, Free and FreeApplicative
if you look at List/Coyoneda/Free/FreeApplicative as programs of a specific shape, which are parameterised by their instructions, then foldMap says: "give me a translation between instructions, and I'll give you a translation between programs "
Fabio Labella
@SystemFw
(free in this context means that the property above holds for all target programs, e.g. you can always recover any other monoid from List, if you can translate individual elements of that List to the target monoid)
I'm probably being overly cryptic, ask further questions either here or in PM :)
but basically my pov (unless you're interested in CT) is that the free property is worth knowing, at which point "Coyoneda is the free functor" is an adequate explanation for programming
Arnau Abella
foldMap for list folds a list of monoids but for free, it folds a list of monads, right ?
Fabio Labella
@SystemFw
no, it folds a Free monad
I'd recommend writing the type down for foldMap on List, Free, FreeApplicative and Coyoneda
I'll write them out for you
Arnau Abella
- List
def foldMap[A, B](fa: List[A])(f: A => B)(implicit B: Monoid[B]): B

- Free
final def foldMap[M[_]](f: S ~> M)(implicit M: Monad[M]): M[A]

- ApplicativeFree
final def foldMap[G[_]](f: F ~> G)(implicit G: Applicative[G]): G[A]

- Coyoneda
final def foldMap[G[_]](trans: F ~> G)(implicit G: Functor[G]): G[A]
Fabio Labella
@SystemFw
right, easier to see if you add the fa to all cases
Arnau Abella
All of them are traversing a structure, mapping each element to something "combinable" and then combine the elements
Let me re-read everything you have written so far ...

"give me a translation between instructions, and I'll give you a translation between programs "

I am familiar to using Free monads as interpreters of grammars written as GADTs

Fabio Labella
@SystemFw
I actually think it's easier to grasp the idea of "freeness" with free monoids
cause you don't have to worry about GADTs and natural transformations, and emulating higher ranks in scala and so on
so let me ask you this question
imagine a language with only one operation: put, which represents the concept of outputting a String
how would you represent this language?
by language I mean a DSL you're writing in Scala
Arnau Abella
case class Put[A](value: A)
Fabio Labella
@SystemFw
case class Put(value: String)
Arnau Abella
Yep, sorry
Fabio Labella
@SystemFw
cool, that's the instruction set of your language
now, how would you represent a program written in that language?
Arnau Abella
val program: List[Put] = ...
Fabio Labella
@SystemFw
ok
now, are you vaguely familiar with final tagless? (if you're not I'll go down another path, but I think there is an interesting connection to be made)
Arnau Abella
I know the concept and how to work with it in Scala (I don't use it on daily bases)
Fabio Labella
@SystemFw
cool
so look at this alternative version of Put
trait Put[A] {
def put(s: String): A
}
can you tell me how to represent a Put program in the tagless representation above?
Arnau Abella
def program[F[_]: Foldable, A]: F[Put[A]]
Fabio Labella
@SystemFw
nope
that's not tagless, with tagless you always need to return the type parameter
(if you've seen the "common version", you'll see def foo[F[_]: Monad: Db]: F[Int], take F[_], return F, so in this case you need to return A)
does that make sense?
little hint
Arnau Abella
So the return type must be F[A] ?
Fabio Labella
@SystemFw
in this case it must be A
Arnau Abella
it's F[_] if your algebra takes F[_], which is what most people think about when they think "final tagless"
but our algebra takes A
def program[A: Monoid]: A
you need [A: Put: Monoid]: A