0
# cats-free
1

2
Comprehensive free monads and related constructs for functional programming in Scala.
3

4
## Package Information
5

6
- **Package Name**: cats-free
7
- **Package Type**: Scala library (Maven/sbt dependency)
8
- **Language**: Scala
9
- **Installation**: `libraryDependencies += "org.typelevel" %% "cats-free" % "1.6.1"`
10
- **Minimum Scala**: 2.11
11
- **License**: MIT
12

13
## Core Imports
14

15
```scala
16
import cats.free._
17
import cats.free.Free
18
import cats.arrow.FunctionK
19
import cats.{Functor, Monad, Comonad, Applicative, Eval, InjectK, Defer, Foldable, Traverse}
20
```
21

22
## Basic Usage
23

24
```scala
25
import cats.free._
26
import cats.free.Free
27

28
// Define your algebra
29
sealed trait KVStoreA[A]
30
case class Put[T](key: String, value: T) extends KVStoreA[Unit]
31
case class Get[T](key: String) extends KVStoreA[Option[T]]
32

33
// Create a Free monad
34
type KVStore[A] = Free[KVStoreA, A]
35

36
def put[T](key: String, value: T): KVStore[Unit] = liftF(Put(key, value))
37
def get[T](key: String): KVStore[Option[T]] = liftF(Get(key))
38

39
// Compose operations
40
val program: KVStore[Option[String]] = for {
41
  _      <- put("name", "Alice")
42
  result <- get[String]("name")
43
} yield result
44
```
45

46
## Architecture
47

48
cats-free implements the Free monad pattern, enabling the separation of program description from program interpretation. This allows you to:
49

50
1. **Define algebras** - Abstract syntax trees representing operations
51
2. **Build programs** - Compose operations using monadic syntax
52
3. **Create interpreters** - Transform abstract operations into concrete effects
53
4. **Execute safely** - Run programs with stack-safe evaluation
54

55
The library provides several related constructs including Free monads, Free applicatives, Free monad transformers, Cofree comonads, and optimization utilities via Yoneda and Coyoneda lemmas.
56

57
## Capabilities
58

59
### Free Monads
60

61
Core free monad construction and operations for building composable, interpreter-separated programs with stack-safe evaluation.
62

63
```scala { .api }
64
sealed abstract class Free[S[_], A] extends Product with Serializable
65

66
// Constructors
67
def pure[S[_], A](a: A): Free[S, A]
68
def liftF[F[_], A](value: F[A]): Free[F, A]
69
def defer[F[_], A](value: => Free[F, A]): Free[F, A]
70
def roll[F[_], A](value: F[Free[F, A]]): Free[F, A]
71

72
// Monadic operations
73
def map[B](f: A => B): Free[S, B]  
74
def flatMap[B](f: A => Free[S, B]): Free[S, B]
75

76
// Transformations
77
def mapK[T[_]](f: S ~> T): Free[T, A]
78
def compile[T[_]](f: FunctionK[S, T]): Free[T, A]
79

80
// Execution
81
def foldMap[M[_]](f: FunctionK[S, M])(implicit M: Monad[M]): M[A]
82
def run(implicit S: Comonad[S]): A
83
def runTailRec(implicit S: Monad[S]): S[A]
84
def runM[M[_]](f: S[Free[S, A]] => M[Free[S, A]])(implicit S: Functor[S], M: Monad[M]): M[A]
85

86
// Evaluation helpers
87
def step: Free[S, A]
88
def resume(implicit S: Functor[S]): Either[S[Free[S, A]], A]
89
def go(f: S[Free[S, A]] => Free[S, A])(implicit S: Functor[S]): A
90
def fold[B](r: A => B, s: S[Free[S, A]] => B)(implicit S: Functor[S]): B
91
```
92

93
[Free Monads](./free-monads.md)
94

95
### Free Monad Transformer  
96

97
Monad transformer version of Free that adds another monad layer for enhanced composition with existing monad stacks.
98

99
```scala { .api }
100
sealed abstract class FreeT[S[_], M[_], A] extends Product with Serializable
101

102
// Constructors
103
def pure[S[_], M[_], A](value: A)(implicit M: Applicative[M]): FreeT[S, M, A]
104
def liftF[S[_], M[_], A](value: S[A])(implicit M: Applicative[M]): FreeT[S, M, A]
105
def liftT[S[_], M[_], A](value: M[A])(implicit M: Functor[M]): FreeT[S, M, A]
106
def roll[S[_], M[_], A](value: S[FreeT[S, M, A]])(implicit M: Applicative[M]): FreeT[S, M, A]
107
def defer[S[_], M[_], A](a: M[Either[A, S[FreeT[S, M, A]]]])(implicit M: Applicative[M]): FreeT[S, M, A]
108

109
// Monadic operations
110
def map[B](f: A => B)(implicit M: Applicative[M]): FreeT[S, M, B]
111
def flatMap[B](f: A => FreeT[S, M, B]): FreeT[S, M, B]
112

113
// Transformations
114
def mapK[N[_]](mn: M ~> N): FreeT[S, N, A]
115
def hoist[N[_]](mn: FunctionK[M, N]): FreeT[S, N, A]
116
def compile[T[_]](st: FunctionK[S, T])(implicit M: Functor[M]): FreeT[T, M, A]
117

118
// Execution
119
def foldMap[N[_]](f: FunctionK[S, N])(implicit M: Monad[M], N: Monad[N]): N[A]
120
def runM(implicit S: Functor[S], M: Monad[M]): M[A]
121
```
122

123
[Free Monad Transformer](./free-transformer.md)
124

125
### Free Applicative
126

127
Free applicative functors for building parallel, analyzable computations that don't require the full power of monadic binding.
128

129
```scala { .api }
130
sealed abstract class FreeApplicative[F[_], A]
131
def pure[F[_], A](a: A): FreeApplicative[F, A]
132
def lift[F[_], A](fa: F[A]): FreeApplicative[F, A]
133
def foldMap[G[_]](f: F ~> G)(implicit G: Applicative[G]): G[A]
134
```
135

136
[Free Applicative](./free-applicative.md)
137

138
### Cofree Comonads
139

140
Dual of Free monads - infinite data structures with context-dependent computation, useful for representing streams and environment-dependent values.
141

142
```scala { .api }
143
final case class Cofree[S[_], A](head: A, tail: Eval[S[Cofree[S, A]]])
144
def unfold[F[_], A](a: A)(f: A => F[A])(implicit F: Functor[F]): Cofree[F, A]
145
def extract: A
146
def coflatMap[B](f: Cofree[S, A] => B)(implicit S: Functor[S]): Cofree[S, B]
147
```
148

149
[Cofree Comonads](./cofree.md)
150

151
### Yoneda and Coyoneda
152

153
Performance optimization constructs that enable map fusion and provide free functors for types that aren't naturally functorial.
154

155
```scala { .api }
156
// Yoneda lemma - cofree functor
157
abstract class Yoneda[F[_], A] extends Serializable {
158
  def apply[B](f: A => B): F[B]
159
  def run: F[A]
160
  def map[B](f: A => B): Yoneda[F, B]
161
  def toCoyoneda: Coyoneda.Aux[F, A, A]
162
}
163

164
// Coyoneda lemma - free functor  
165
sealed abstract class Coyoneda[F[_], A] extends Serializable {
166
  type Pivot
167
  val fi: F[Pivot]
168
  def k: Pivot => A
169
  def run(implicit F: Functor[F]): F[A]
170
  def map[B](f: A => B): Coyoneda[F, B]
171
  def transform[G[_]](f: FunctionK[F, G]): Coyoneda[G, A]
172
}
173

174
object Coyoneda {
175
  type Aux[F[_], A, B] = Coyoneda[F, A] { type Pivot = B }
176
  def lift[F[_], A](fa: F[A]): Coyoneda[F, A]
177
  def apply[F[_], A, B](fa: F[A])(f: A => B): Aux[F, B, A]
178
}
179

180
object Yoneda {
181
  def apply[F[_], A](fa: F[A])(implicit F: Functor[F]): Yoneda[F, A]
182
}
183
```
184

185
[Yoneda and Coyoneda](./yoneda-coyoneda.md)
186

187
### Trampoline
188

189
Stack-safe recursion utility built on Free monads over Function0, providing an easy way to convert recursive algorithms into iterative ones.
190

191
```scala { .api }
192
type Trampoline[A] = Free[Function0, A]
193
def done[A](a: A): Trampoline[A]
194
def defer[A](a: => Trampoline[A]): Trampoline[A]
195
def delay[A](a: => A): Trampoline[A]
196
```
197

198
[Trampoline](./trampoline.md)
199

200
### Interpreters and Natural Transformations
201

202
Utilities for creating interpreters and natural transformations to convert between different effect types and execute Free programs.
203

204
```scala { .api }
205
// Natural transformations
206
trait FunctionK[F[_], G[_]] extends Serializable {
207
  def apply[A](fa: F[A]): G[A]
208
  def compose[E[_]](f: FunctionK[E, F]): FunctionK[E, G]
209
  def andThen[H[_]](f: FunctionK[G, H]): FunctionK[F, H]
210
}
211

212
// Free monad transformation methods (defined on Free instances)
213
def mapK[T[_]](f: S ~> T): Free[T, A]
214
def compile[T[_]](f: FunctionK[S, T]): Free[T, A]
215

216
// InjectK for composable algebras
217
abstract class InjectK[F[_], G[_]] {
218
  def inj: FunctionK[F, G]
219
  def prj: FunctionK[G, λ[α => Option[F[α]]]]
220
  def apply[A](fa: F[A]): G[A]
221
  def unapply[A](ga: G[A]): Option[F[A]]
222
}
223

224
// Free injection helpers
225
def liftInject[G[_]]: FreeLiftInjectKPartiallyApplied[G]
226
def inject[F[_], G[_]]: FreeInjectKPartiallyApplied[F, G]
227
```
228

229
[Interpreters](./interpreters.md)