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)