0
# Free Structures
1

2
Free structures provide composable, purely functional DSLs and interpreters, allowing separation of description from interpretation in functional programs.
3

4
## Capabilities
5

6
### Free Monads
7

8
#### Free
9

10
Free monad that turns any functor into a monad, enabling pure functional DSLs.
11

12
```scala { .api }
13
sealed abstract class Free[S[_], A] {
14
  /** Map over the result value */
15
  def map[B](f: A => B): Free[S, B]
16
  
17
  /** Monadic bind operation */
18
  def flatMap[B](f: A => Free[S, B]): Free[S, B]
19
  
20
  /** Fold the free monad using a natural transformation */
21
  def foldMap[M[_]](f: S ~> M)(implicit M: Monad[M]): M[A]
22
  
23
  /** Run using Id (for pure functors) */
24
  def run(implicit S: Functor[S]): A
25
  
26
  /** Run a single step */
27
  def resume(implicit S: Functor[S]): S[Free[S, A]] \/ A
28
  
29
  /** Convert to FreeT */
30
  def toFreeT[M[_]](implicit M: Applicative[M]): FreeT[S, M, A]
31
  
32
  /** Hoist to another functor */
33
  def hoist[T[_]](f: S ~> T): Free[T, A]
34
  
35
  /** Inject into a coproduct */
36
  def inject[T[_]](implicit I: Inject[S, T]): Free[T, A]
37
}
38

39
/** Pure value in Free monad */
40
case class Return[S[_], A](a: A) extends Free[S, A]
41

42
/** Suspended computation in Free monad */
43
case class Suspend[S[_], A](sa: S[Free[S, A]]) extends Free[S, A]
44

45
object Free {
46
  /** Lift a pure value into Free */
47
  def pure[S[_], A](a: A): Free[S, A] = Return(a)
48
  
49
  /** Lift a functor value into Free */
50
  def liftF[S[_], A](sa: S[A])(implicit S: Functor[S]): Free[S, A] = 
51
    Suspend(S.map(sa)(Return(_)))
52
    
53
  /** Roll a suspended computation */
54
  def roll[S[_], A](sa: S[Free[S, A]]): Free[S, A] = Suspend(sa)
55
  
56
  /** Create from function */
57
  def unfold[S[_], A, B](a: A)(f: A => S[A] \/ B)(implicit S: Functor[S]): Free[S, B]
58
  
59
  /** Trampoline - Free monad over Function0 for stack safety */
60
  type Trampoline[A] = Free[Function0, A]
61
  
62
  /** Source - Free monad over (A, ?) for generating sequences */
63
  type Source[A, B] = Free[({ type f[x] = (A, x) })#f, B]
64
  
65
  /** Sink - Free monad over (=> A) for consuming sequences */  
66
  type Sink[A, B] = Free[({ type f[x] = (=> A) => x })#f, B]
67
}
68
```
69

70
**Usage Examples:**
71

72
```scala
73
import scalaz._
74
import scalaz.Free._
75

76
// Define DSL operations
77
sealed trait ConsoleOp[A]
78
case class PrintLine(msg: String) extends ConsoleOp[Unit]
79
case class ReadLine() extends ConsoleOp[String]
80

81
// Smart constructors
82
def printLine(msg: String): Free[ConsoleOp, Unit] = 
83
  liftF(PrintLine(msg))
84
def readLine: Free[ConsoleOp, String] = 
85
  liftF(ReadLine())
86

87
// Program using the DSL
88
val program = for {
89
  _    <- printLine("What's your name?")
90
  name <- readLine
91
  _    <- printLine(s"Hello, $name!")
92
} yield name
93

94
// Interpreter
95
val consoleInterpreter = new (ConsoleOp ~> Id) {
96
  def apply[A](op: ConsoleOp[A]): A = op match {
97
    case PrintLine(msg) => println(msg)
98
    case ReadLine()     => scala.io.StdIn.readLine()
99
  }
100
}
101

102
// Run the program
103
val result = program.foldMap(consoleInterpreter)
104
```
105

106
#### FreeT
107

108
Free monad transformer combining Free with another monad.
109

110
```scala { .api }
111
sealed abstract class FreeT[S[_], M[_], A] {
112
  /** Map over the result value */
113
  def map[B](f: A => B)(implicit M: Functor[M]): FreeT[S, M, B]
114
  
115
  /** Monadic bind operation */
116
  def flatMap[B](f: A => FreeT[S, M, B])(implicit M: Monad[M]): FreeT[S, M, B]
117
  
118
  /** Fold using natural transformation */
119
  def foldMap[N[_]](f: S ~> N)(implicit M: Monad[M], N: Monad[N]): M[A]
120
  
121
  /** Interpret into the base monad */
122
  def interpret[N[_]](f: S ~> ({ type λ[α] = FreeT[N, M, α] })#λ)(implicit M: Monad[M]): FreeT[N, M, A]
123
  
124
  /** Run the FreeT */
125
  def runFreeT(implicit M: Monad[M]): M[S[FreeT[S, M, A]] \/ A]
126
  
127
  /** Hoist the base monad */
128
  def hoist[N[_]](mn: M ~> N)(implicit M: Functor[M]): FreeT[S, N, A]
129
  
130
  /** Transform the functor */
131
  def mapSuspension[T[_]](f: S ~> T)(implicit M: Functor[M]): FreeT[T, M, A]
132
}
133

134
object FreeT {
135
  /** Lift a pure value */
136
  def point[S[_], M[_], A](a: A)(implicit M: Applicative[M]): FreeT[S, M, A]
137
  
138
  /** Lift a functor operation */
139
  def liftF[S[_], M[_], A](sa: S[A])(implicit S: Functor[S], M: Applicative[M]): FreeT[S, M, A]
140
  
141
  /** Lift base monad operation */
142
  def liftM[S[_], M[_], A](ma: M[A])(implicit M: Applicative[M]): FreeT[S, M, A]
143
  
144
  /** Roll a suspended computation */
145
  def roll[S[_], M[_], A](smf: S[FreeT[S, M, A]])(implicit M: Applicative[M]): FreeT[S, M, A]
146
}
147
```
148

149
### Free Applicatives
150

151
#### FreeAp
152

153
Free applicative functor for building parallel computations that can be optimized and interpreted.
154

155
```scala { .api }
156
sealed abstract class FreeAp[S[_], A] {
157
  /** Map over the result value */
158
  def map[B](f: A => B): FreeAp[S, B]
159
  
160
  /** Apply a function in FreeAp */
161
  def ap[B](f: FreeAp[S, A => B]): FreeAp[S, B]
162
  
163
  /** Fold using natural transformation */
164
  def foldMap[G[_]](f: S ~> G)(implicit G: Applicative[G]): G[A]
165
  
166
  /** Analyze the structure (for optimization) */
167
  def analyze[M](f: S ~> ({ type λ[α] = Const[M, α] })#λ)(implicit M: Monoid[M]): M
168
  
169
  /** Convert to Free monad */
170
  def toFree: Free[S, A]
171
  
172
  /** Hoist to another functor */
173
  def hoist[T[_]](f: S ~> T): FreeAp[T, A]
174
}
175

176
object FreeAp {
177
  /** Lift a pure value */
178
  def pure[S[_], A](a: A): FreeAp[S, A]
179
  
180
  /** Lift a functor operation */
181
  def liftF[S[_], A](sa: S[A]): FreeAp[S, A]
182
  
183
  /** Natural transformation to Free */
184
  def freeApToFree[S[_]]: FreeAp[S, ?] ~> Free[S, ?]
185
}
186
```
187

188
**Usage Examples:**
189

190
```scala
191
import scalaz._
192
import scalaz.Free._
193

194
// Validation DSL using FreeAp
195
sealed trait ValidateOp[A]
196
case class CheckLength(s: String, min: Int) extends ValidateOp[Boolean]
197
case class CheckEmail(s: String) extends ValidateOp[Boolean]
198

199
def checkLength(s: String, min: Int): FreeAp[ValidateOp, Boolean] = 
200
  FreeAp.liftF(CheckLength(s, min))
201
def checkEmail(s: String): FreeAp[ValidateOp, Boolean] = 
202
  FreeAp.liftF(CheckEmail(s))
203

204
// Parallel validation
205
val validation = (
206
  checkLength("John", 2) |@|
207
  checkEmail("john@example.com")
208
) { (lengthOk, emailOk) => lengthOk && emailOk }
209

210
// Interpreter can optimize parallel operations
211
val validator = new (ValidateOp ~> Id) {
212
  def apply[A](op: ValidateOp[A]): A = op match {
213
    case CheckLength(s, min) => s.length >= min
214
    case CheckEmail(s)       => s.contains("@")
215
  }
216
}
217

218
val result = validation.foldMap(validator)
219
```
220

221
### Cofree Comonads
222

223
#### Cofree
224

225
Cofree comonad that provides infinite streams of values with comonadic operations.
226

227
```scala { .api }
228
sealed abstract class Cofree[S[_], A] {
229
  /** The head value */
230
  def head: A
231
  
232
  /** The tail structure */
233
  def tail: S[Cofree[S, A]]
234
  
235
  /** Map over all values */
236
  def map[B](f: A => B): Cofree[S, B]
237
  
238
  /** Cofree comonad extend operation */
239
  def extend[B](f: Cofree[S, A] => B): Cofree[S, B]
240
  
241
  /** Extract the head value */
242
  def extract: A = head
243
  
244
  /** Unfold from the current position */
245
  def unfold[B](f: Cofree[S, A] => (B, S[Cofree[S, A]])): Cofree[S, B]
246
  
247
  /** Convert to Free monad */
248
  def toFree: Free[S, A]
249
  
250
  /** Hoist to another functor */
251
  def hoist[T[_]](f: S ~> T): Cofree[T, A]
252
  
253
  /** Transform values with access to context */
254
  def cojoin: Cofree[S, Cofree[S, A]]
255
  
256
  /** Apply a natural transformation */
257
  def mapBranching[T[_]](f: S ~> T): Cofree[T, A]
258
}
259

260
case class Cofree[S[_], A](head: A, tail: S[Cofree[S, A]])
261

262
object Cofree {
263
  /** Create Cofree from head and tail */
264
  def apply[S[_], A](head: A, tail: S[Cofree[S, A]]): Cofree[S, A]
265
  
266
  /** Unfold a Cofree structure */
267
  def unfold[S[_], A, B](seed: A)(f: A => (B, S[A]))(implicit S: Functor[S]): Cofree[S, B]
268
  
269
  /** Create from a sequence */
270
  def fromSeq[A](seq: Seq[A]): Cofree[Option, A]
271
  
272
  /** Repeat a value infinitely */
273
  def repeat[A](a: A): Cofree[Function0, A]
274
  
275
  /** Iterate a function */
276
  def iterate[A](start: A)(f: A => A): Cofree[Function0, A]
277
}
278
```
279

280
**Usage Examples:**
281

282
```scala
283
import scalaz._
284

285
// Infinite stream of natural numbers
286
val naturals = Cofree.iterate(0)(_ + 1)
287

288
// Take first 5 values
289
def take[A](n: Int, cf: Cofree[Function0, A]): List[A] = {
290
  if (n <= 0) Nil
291
  else cf.head :: take(n - 1, cf.tail())
292
}
293

294
val first5 = take(5, naturals)  // List(0, 1, 2, 3, 4)
295

296
// Fibonacci sequence
297
def fib: Cofree[Function0, Int] = {
298
  def fibStep(a: Int, b: Int): Cofree[Function0, Int] =
299
    Cofree(a, () => fibStep(b, a + b))
300
  fibStep(0, 1)
301
}
302

303
val fibNumbers = take(10, fib)  // List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
304
```
305

306
### Coproducts and Injection
307

308
#### Coproduct
309

310
Coproduct (sum) of two functors, enabling composition of DSLs.
311

312
```scala { .api }
313
sealed abstract class Coproduct[F[_], G[_], A] {
314
  /** Fold using natural transformations */
315
  def fold[H[_]](f: F ~> H, g: G ~> H): H[A]
316
  
317
  /** Map over the value */
318
  def map[B](f: A => B): Coproduct[F, G, B]
319
  
320
  /** Check if this is left */
321
  def isLeft: Boolean
322
  
323
  /** Check if this is right */
324
  def isRight: Boolean
325
  
326
  /** Run natural transformation on left */
327
  def leftMap[H[_]](f: F ~> H): Coproduct[H, G, A]
328
  
329
  /** Run natural transformation on right */
330
  def rightMap[H[_]](f: G ~> H): Coproduct[F, H, A]
331
}
332

333
case class Coproduct[F[_], G[_], A](run: F[A] \/ G[A])
334

335
object Coproduct {
336
  /** Create left coproduct */
337
  def leftc[F[_], G[_], A](fa: F[A]): Coproduct[F, G, A]
338
  
339
  /** Create right coproduct */
340
  def rightc[F[_], G[_], A](ga: G[A]): Coproduct[F, G, A]
341
}
342
```
343

344
#### Inject
345

346
Type class for injecting one functor into a coproduct.
347

348
```scala { .api }
349
sealed abstract class Inject[F[_], G[_]] {
350
  /** Inject F into G */
351
  def inj[A](fa: F[A]): G[A]
352
  
353
  /** Try to project G back to F */
354
  def prj[A](ga: G[A]): Option[F[A]]
355
}
356

357
object Inject {
358
  /** Reflexive injection */
359
  implicit def reflexiveInject[F[_]]: Inject[F, F]
360
  
361
  /** Left injection into coproduct */
362
  implicit def leftInject[F[_], G[_]]: Inject[F, Coproduct[F, G, ?]]
363
  
364
  /** Right injection into coproduct */
365
  implicit def rightInject[F[_], G[_], H[_]](implicit I: Inject[F, G]): Inject[F, Coproduct[H, G, ?]]
366
}
367
```
368

369
**Usage Examples:**
370

371
```scala
372
import scalaz._
373
import scalaz.Free._
374

375
// Multiple DSL composition
376
sealed trait FileOp[A]
377
case class ReadFile(name: String) extends FileOp[String]
378
case class WriteFile(name: String, content: String) extends FileOp[Unit]
379

380
sealed trait ConsoleOp[A]  
381
case class PrintLine(msg: String) extends ConsoleOp[Unit]
382
case object ReadLine extends ConsoleOp[String]
383

384
// Combined DSL
385
type App[A] = Coproduct[FileOp, ConsoleOp, A]
386

387
// Smart constructors using injection
388
def readFile(name: String)(implicit I: Inject[FileOp, App]): Free[App, String] =
389
  liftF(I.inj(ReadFile(name)))
390
  
391
def printLine(msg: String)(implicit I: Inject[ConsoleOp, App]): Free[App, Unit] =
392
  liftF(I.inj(PrintLine(msg)))
393

394
// Program using both DSLs
395
val program = for {
396
  content <- readFile("input.txt")
397
  _       <- printLine(s"File content: $content")
398
} yield content
399

400
// Interpreters
401
val fileInterpreter = new (FileOp ~> Id) {
402
  def apply[A](op: FileOp[A]): A = op match {
403
    case ReadFile(name) => s"Contents of $name"
404
    case WriteFile(name, content) => println(s"Writing to $name: $content")
405
  }
406
}
407

408
val consoleInterpreter = new (ConsoleOp ~> Id) {
409
  def apply[A](op: ConsoleOp[A]): A = op match {
410
    case PrintLine(msg) => println(msg)
411
    case ReadLine => scala.io.StdIn.readLine()
412
  }
413
}
414

415
// Combined interpreter
416
val appInterpreter = new (App ~> Id) {
417
  def apply[A](app: App[A]): A = app.fold(fileInterpreter, consoleInterpreter)
418
}
419

420
// Run the program
421
program.foldMap(appInterpreter)
422
```
423

424
### Natural Transformations
425

426
#### Natural Transformation (~>)
427

428
Type-level function between functors.
429

430
```scala { .api }
431
trait NaturalTransformation[F[_], G[_]] {
432
  /** Apply the transformation */
433
  def apply[A](fa: F[A]): G[A]
434
  
435
  /** Compose with another natural transformation */
436
  def compose[E[_]](f: E ~> F): E ~> G
437
  
438
  /** AndThen composition */
439
  def andThen[H[_]](f: G ~> H): F ~> H
440
}
441

442
type ~>[F[_], G[_]] = NaturalTransformation[F, G]
443
type <~[F[_], G[_]] = NaturalTransformation[G, F]
444

445
object NaturalTransformation {
446
  /** Identity transformation */
447
  def id[F[_]]: F ~> F = new (F ~> F) {
448
    def apply[A](fa: F[A]): F[A] = fa
449
  }
450
  
451
  /** Constant transformation */
452
  def const[F[_], G[_]](g: G[Unit]): F ~> G
453
}
454
```
455

456
**Usage Examples:**
457

458
```scala
459
import scalaz._
460

461
// Natural transformation from Option to List
462
val optionToList = new (Option ~> List) {
463
  def apply[A](opt: Option[A]): List[A] = opt.toList
464
}
465

466
// Natural transformation from List to Option (taking head)
467
val listToOption = new (List ~> Option) {
468
  def apply[A](list: List[A]): Option[A] = list.headOption
469
}
470

471
// Use in Free monad interpretation
472
val program: Free[Option, Int] = for {
473
  x <- Free.liftF(Some(1))
474
  y <- Free.liftF(Some(2))
475
} yield x + y
476

477
val result = program.foldMap(optionToList)  // List(3)
478
```
479

480
### Trampoline for Stack Safety
481

482
#### Trampoline
483

484
Stack-safe computation using Free monad over Function0.
485

486
```scala { .api }
487
type Trampoline[A] = Free[Function0, A]
488

489
object Trampoline {
490
  /** Suspend a computation */
491
  def suspend[A](a: => Trampoline[A]): Trampoline[A] = 
492
    Free.liftF(() => a).flatMap(identity)
493
    
494
  /** Delay a computation */
495
  def delay[A](a: => A): Trampoline[A] = suspend(Free.pure(a))
496
  
497
  /** Done with result */
498
  def done[A](a: A): Trampoline[A] = Free.pure(a)
499
}
500
```
501

502
**Usage Examples:**
503

504
```scala
505
import scalaz._
506
import scalaz.Free.Trampoline
507

508
// Stack-safe factorial
509
def factorial(n: Int): Trampoline[BigInt] = {
510
  if (n <= 1) Trampoline.done(BigInt(1))
511
  else Trampoline.suspend(factorial(n - 1).map(_ * n))
512
}
513

514
// Stack-safe even/odd
515
def even(n: Int): Trampoline[Boolean] = 
516
  if (n == 0) Trampoline.done(true)
517
  else Trampoline.suspend(odd(n - 1))
518

519
def odd(n: Int): Trampoline[Boolean] =
520
  if (n == 0) Trampoline.done(false) 
521
  else Trampoline.suspend(even(n - 1))
522

523
// Run safely
524
val result1 = factorial(10000).run
525
val result2 = even(10000).run
526
```