The debatably Free monad

# The debatably Free monad

[Nicolas Rinaudo] • [@NicolasRinaudo@functional.cafe]

---

# A simple Console DSL

---

## The dawn of AI

```text
What is your name?
>
```

---

## The dawn of AI

```
What is your name?
> Nicolas
```

---

## The dawn of AI

```
What is your name?
> Nicolas
Hello, Nicolas!
```

---

## ADT encoding

```scala
enum Console:
```

---

## ADT encoding

---

## ADT encoding

---

## Basic interpreter

```scala
def eval(console: Console) = ???
```

---

## Basic interpreter

```scala
def eval(console: `Console`) = ???
```

---

## Basic interpreter

---

## Basic interpreter

.diff-add[
```scala
*def eval(console: Console) = `console match`
* `case Print(msg) => ???`
* `case Read       => ???`
```
]

---

## Basic interpreter

.diff-rm[
```scala
def eval(console: Console) = console match
* case Print(msg) => `???`
  case Read       => ???
```
]

---

## Basic interpreter

.diff-add[
```scala
def eval(console: Console) = console match
  case Print(msg) =>
*   `println(msg)`
*
  case Read       => ???
```
]

---

## Basic interpreter

* case Read       => `???`
```
]

---

## Basic interpreter

case Read       =>
*   `scala.io.StdIn.readLine()`
```
]

---

## Basic interpreter

.diff-add[
```scala
*def eval(console: Console)`: ???` = console match
  case Print(msg) =>
    println(msg)

case Read       =>
    scala.io.StdIn.readLine()
```
]

---

## Basic interpreter

```scala
def eval(console: Console): ??? = console match
  case Print(msg) =>
    `println(msg)`

case Read       =>
    scala.io.StdIn.readLine()
```

---

## Basic interpreter

```scala
def eval(console: Console): ??? = console match
  case Print(msg) =>
    println(msg)

case Read       =>
    `scala.io.StdIn.readLine()`
```

---

## Basic interpreter

.diff-rm[
```scala
*def eval(console: Console): `???` = console match
  case Print(msg) =>
    println(msg)

case Read       =>
    scala.io.StdIn.readLine()
```
]

---

## Basic interpreter

.diff-add[
```scala
*def eval(console: Console): `Any` = console match
  case Print(msg) =>
    println(msg)

case Read       =>
    scala.io.StdIn.readLine()
```
]

---

## GADT encoding

---

## GADT encoding

.diff-add[
```scala
enum Console[A]:
* case Print(msg: String)` extends Console[Unit]`
  case Read
```
]

---

## GADT encoding

.diff-add[
```scala
enum Console[A]:
  case Print(msg: String) extends Console[Unit]
* case Read` extends Console[String]`
```
]

---

## GADT encoding

```scala
def eval(console: Console): Any = console match
  case Print(msg) =>
    println(msg)

case Read       =>
    scala.io.StdIn.readLine()
```

---

## GADT encoding

.diff-add[
```scala
*def eval[`A`](console: Console`[A]`): Any = console match
  case Print(msg) =>
    println(msg)

case Read       =>
    scala.io.StdIn.readLine()
```
]

---

## GADT encoding

.diff-rm[
```scala
*def eval[A](console: Console[A]): `Any` = console match
  case Print(msg) =>
    println(msg)

case Read       =>
    scala.io.StdIn.readLine()
```
]

---

## GADT encoding

.diff-add[
```scala
*def eval[A](console: Console[A]): `A` = console match
  case Print(msg) =>
    println(msg)

case Read       =>
    scala.io.StdIn.readLine()
```
]

---

## Key takeaways

* Console statements are encoded as a GADT.

* We know how to evaluate _a single statement_ as a pattern match.

* We haven't solved our problem, though...

---

# Chaining statements

---

## Naive implementation

```scala
val program = ???
```

---

## Naive implementation

---

## Naive implementation

---

## Naive implementation

.diff-add[
```scala
val program =
  Print("What is your name?") ::
* `Read                        ::`
```
]

---

## Naive implementation

.diff-add[
```scala
val program =
  Print("What is your name?") ::
  Read                        ::
* `Print("Hello!")             ::`
```
]

---

## Naive implementation

.diff-add[
```scala
val program =
  Print("What is your name?") ::
  Read                        ::
  Print("Hello!")             ::
* `Nil`
```
]

---

## Naive implementation

```scala
val program =
  Print("What is your name?") ::
  Read                        ::
  `Print("Hello!")`             ::
  Nil
```

---

## Naive implementation

```scala
val program =
  Print("What is your name?") ::
  `Read`                        ::
  `Print("Hello!")`             ::
  Nil
```

---

## Naive implementation

```scala
val program =
  Print("What is your name?") ::
  Read                        `::`
  Print("Hello!")             `::`
  Nil
```

---

## Linked statements

```scala
enum Console[A]:
  case Print(msg: String) extends Console[Unit]
  case Read extends Console[String]
```

---

## Linked statements

.diff-add[
```scala
enum Console[A]:
  case Print(msg: String) extends Console[Unit]
* case Read`(next: Console[A])` extends Console[String]
```
]

---

## Linked statements

.diff-rm[
```scala
enum Console[A]:
  case Print(msg: String) extends Console[Unit]
* case Read(next: Console[A]) extends Console[`String`]
```
]

---

## Linked statements

.diff-add[
```scala
enum Console[A]:
  case Print(msg: String) extends Console[Unit]
* case Read(next: Console[A]) extends Console[`A`]
```
]

---

## Linked statements

.diff-add[
```scala
enum Console[A]:
  case Print(msg: String) extends Console[Unit]
  case Read(next: Console[A]) extends Console[A]
```
]

---

## Linked statements

.diff-add[
```scala
enum Console[A]:
  case Print(msg: String) extends Console[Unit]
  case Read(next: Console[A]) extends Console[A]
```
]

---

## Linked statements

.diff-add[
```scala
enum Console[A]:
* case Print(msg: String`, next: Console[A]`) extends Console[Unit]
  case Read(next: Console[A]) extends Console[A]
```
]

---

## Linked statements

.diff-rm[
```scala
enum Console[A]:
* case Print(msg: String, next: Console[A]) extends Console[`Unit`]
  case Read(next: Console[A]) extends Console[A]
```
]

---

## Linked statements

.diff-add[
```scala
enum Console[A]:
* case Print(msg: String, next: Console[A]) extends Console[`A`]
  case Read(next: Console[A]) extends Console[A]
```
]

---

## Linked statements

```scala
enum Console[A]:
  case Print(msg: String, next: Console[A]) extends Console[A]
  case Read(next: Console[A]) extends Console[A]
```

---

## Linked statements

.diff-add[
```scala
enum Console[A]:
  case Print(msg: String, next: Console[A]) extends Console[A]
  case Read(next: Console[A]) extends Console[A]
* `case Stop extends Console[Unit]`
```
]

---

## Linked statements

```scala
enum Console[A]:
  case Print(msg: String, next: Console[A]) extends Console[A]
  case Read(next: Console[A]) extends Console[A]
  case Stop extends Console[Unit]

```

---

## Linked statements

```scala
enum Console[A]:
  case Print(msg: String, next: Console[A]) extends `Console[A]`
  case Read(next: Console[A]) extends `Console[A]`
  case Stop extends Console[Unit]
```

---

## Linked statements

```scala
enum `Console[A]`:
  case Print(msg: String, next: Console[A]) extends Console[A]
  case Read(next: Console[A]) extends Console[A]
  case Stop extends Console[Unit]
```

---

## Linked statements

.diff-rm[
```scala
enum Console[A]:
* case Print(msg: String, next: Console[A]) `extends Console[A]`
* case Read(next: Console[A]) `extends Console[A]`
  case Stop extends Console[Unit]
```
]

---

## Linked statements

```scala
enum Console[A]:
  case Print(msg: String, next: Console[A])
  case Read(next: Console[A])
  case Stop extends Console[Unit]

```

---

## Linked statements

```scala
val program =
  Print("What is your name?") ::
  Read                        ::
  Print("Hello!")             ::
  Nil
```

---

## Linked statements

.diff-rm[
```scala
val program =
  Print("What is your name?") ::
  Read                        ::
  Print("Hello!")             ::
* `Nil`
```
]

---

## Linked statements

.diff-add[
```scala
val program =
  Print("What is your name?") ::
  Read                        ::
  Print("Hello!")             ::
* `Stop`
```
]

---

## Linked statements

.diff-rm[
```scala
val program =
* Print("What is your name?"`) ::`
  Read                        ::
  Print("Hello!")             ::
  Stop
```
]

---

## Linked statements

.diff-add[
```scala
val program =
* Print("What is your name?"`,`
*   Read                      ::
*   Print("Hello!")           ::
*   Stop`)`
```
]

---

## Linked statements

.diff-rm[
```scala
val program =
  Print("What is your name?",
*   Read                      `::`
    Print("Hello!")           ::
    Stop)
```
]

---

## Linked statements

.diff-add[
```scala
val program =
  Print("What is your name?",
*   Read`(`
*     Print("Hello!")           ::
*     Stop)`)`
```
]

---

## Linked statements

.diff-rm[
```scala
val program =
  Print("What is your name?",
    Read(
*     Print("Hello!"`)           ::`
      Stop))
```
]

---

## Linked statements

.diff-add[
```scala
val program =
  Print("What is your name?",
    Read(
*     Print("Hello!"`,`
*       Stop))`)`
```
]

---

## Continuations

```scala
val program =
  Print("What is your name?",
    Read(
      Print("Hello!",
        Stop)))

```

---

## Continuations

```scala
val program =
  Print("What is your name?",
    Read(
      `Print("Hello!",`
        Stop)))
```

---

## Continuations

```scala
val program =
  Print("What is your name?",
    `Read`(
      Print("Hello!",
        Stop)))
```

---

## Continuations

.diff-rm[
```scala
enum Console[A]:
  case Print(msg: String, next: Console[A])
* case Read(`next: Console[A]`)
  case Stop extends Console[Unit]
```
]

---

## Continuations

.diff-add[
```scala
enum Console[A]:
  case Print(msg: String, next: Console[A])
* case Read(`next: String => Console[A]`)
  case Stop extends Console[Unit]
```
]

---

## Continuations

.diff-rm[
```scala
enum Console[A]:
* case Print(msg: String, `next: Console[A]`)
  case Read(next: String => Console[A])
  case Stop extends Console[Unit]
```
]

---

## Continuations

.diff-add[
```scala
enum Console[A]:
* case Print(msg: String, `next: () => Console[A]`)
  case Read(next: String => Console[A])
  case Stop extends Console[Unit]
```
]

---

## Continuations

```scala
val program =
  Print("What is your name?",
    Read(
      Print("Hello!",
        Stop)))
```

---

## Continuations

.diff-add[
```scala
val program =
* Print("What is your name?", `() =>`
    Read(
      Print("Hello!",
        Stop)))
```
]

---

## Continuations

.diff-add[
```scala
val program =
  Print("What is your name?", () =>
*   Read(`name =>`
      Print("Hello!",
        Stop)))
```
]

---

## Continuations

.diff-add[
```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
*     Print(`s`"Hello`, $name`!",
        Stop)))
```
]

---

## Continuations

.diff-add[
```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
*     Print(s"Hello, $name!", `() =>`
        Stop)))
```
]

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg) =>
    println(msg)

case Read       =>
    scala.io.StdIn.readLine()
```

---

## Evaluation

.diff-add[
```scala
def eval[A](console: Console[A]): A = console match
* case Print(msg`, next`) =>
    println(msg)

* case Read(`next`)       =>
    scala.io.StdIn.readLine()
```
]

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    `println`(msg)

case Read(next)       =>
    scala.io.StdIn.readLine()
```

---

## Evaluation

```scala
def eval[A](console: Console[A]): `A` = console match
  case Print(msg, next) =>
    println(msg)

case Read(next)       =>
    scala.io.StdIn.readLine()
```

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, `next`) =>
    println(msg)

case Read(next)       =>
    scala.io.StdIn.readLine()
```

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)

case Read(next)       =>
    scala.io.StdIn.readLine()
```

---

## Evaluation

```scala
def `eval`[A](console: `Console[A]`): `A` = console match
  case Print(msg, next) =>
    println(msg)

case Read(next)       =>
    scala.io.StdIn.readLine()
```

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)

case Read(next)       =>
    scala.io.StdIn.readLine()
```

---

## Evaluation

.diff-add[
```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
*   `eval(next())`

case Read(next)       =>
    scala.io.StdIn.readLine()
```
]

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    eval(next())

case Read(next)       =>
    scala.io.StdIn.`readLine`()
```

---

## Evaluation

```scala
def eval[A](console: Console[A]): `A` = console match
  case Print(msg, next) =>
    println(msg)
    eval(next())

case Read(next)       =>
    scala.io.StdIn.readLine()
```

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    eval(next())

case Read(`next`)       =>
    scala.io.StdIn.readLine()
```

---

## Evaluation

```scala
def `eval`[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    eval(next())

case Read(next)       =>
    scala.io.StdIn.readLine()
```

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    eval(next())

case Read(next)       =>
    scala.io.StdIn.readLine()
```
---

## Evaluation

.diff-add[
```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    eval(next())

case Read(next)       =>
*   `eval(next(`scala.io.StdIn.readLine()`))`
```
]

---

## Evaluation

.diff-add[
```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    eval(next())

case Read(next)       =>
    eval(next(scala.io.StdIn.readLine()))
*
* `case Stop             =>`
*   `()`
```
]

---

## Key takeaways

* Chaining console statements is done by continuations.

* Evaluating a chain of statements is a recursive pattern match.

* This is not very reusable, though...

---

# Decomposing programs

---

## Decomposing program

```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
      Print(s"Hello, $name!", () =>
        Stop)))
```

---

## Decomposing program

```scala
val program =
  `Print("What is your name?", () =>`
    `Read(name =>`
      Print(s"Hello, $name!", () =>
        Stop)))
```

---

## Decomposing program

.diff-add[
```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
      Print(s"Hello, $name!", () =>
        Stop)))
*
*`val ask =`
* `Print("What is your name?", () =>`
*   `Read(name =>`
```
]

---

## Decomposing program

.diff-add[
```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
      Print(s"Hello, $name!", () =>
        Stop)))

val ask =
  Print("What is your name?", () =>
    Read(name => `name))`
```
]

---

## Decomposing program

```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
      Print(s"Hello, $name!", () =>
        Stop)))

val ask =
  `Print`("What is your name?", () =>
    Read(name => name))
```

---

## Decomposing program

```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
      Print(s"Hello, $name!", () =>
        Stop)))

val ask =
  Print("What is your name?", () =>
    Read(name => `name`))
```

---

## Decomposing program

.diff-add[
```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
      Print(s"Hello, $name!", () =>
        Stop)))

*val ask`: Console[String]` =
  Print("What is your name?", () =>
    Read(name => name))
```
]

---

## Decomposing program

```scala
val program =
  Print("What is your name?", () =>
    Read(`name =>`
      `Print(s"Hello, $name!", () =>`
        `Stop)`))

val ask: Console[String] =
  Print("What is your name?", () =>
    Read(name => name))
```

---

## Decomposing program

.diff-add[
```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
      Print(s"Hello, $name!", () =>
        Stop)))

val ask: Console[String] =
  Print("What is your name?", () =>
    Read(name => name))
*
*`val greet =`
* `name =>`
*   `Print(s"Hello, $name!", () =>`
*     `Stop)`
```
]

---

## Decomposing program

```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
      Print(s"Hello, $name!", () =>
        Stop)))

val ask: Console[String] =
  Print("What is your name?", () =>
    Read(name => name))

val greet =
  `name` =>
    Print(s"Hello, $name!", () =>
      Stop)
```

---

## Decomposing program

```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
      Print(s"Hello, $name!", () =>
        Stop)))

val ask: Console[String] =
  Print("What is your name?", () =>
    Read(name => name))

val greet =
  name =>
    `Print`(s"Hello, $name!", () =>
      Stop)
```

---

## Decomposing program

```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
      Print(s"Hello, $name!", () =>
        Stop)))

val ask: Console[String] =
  Print("What is your name?", () =>
    Read(name => name))

val greet =
  name =>
    Print(s"Hello, $name!", () =>
      `Stop`)
```

---

## Decomposing program

.diff-add[
```scala
val program =
  Print("What is your name?", () =>
    Read(name =>
      Print(s"Hello, $name!", () =>
        Stop)))

val ask: Console[String] =
  Print("What is your name?", () =>
    Read(name => name))

*val greet`: String => Console[Unit]` =
  name =>
    Print(s"Hello, $name!", () =>
      Stop)
```
]

---

## Decomposing program

.diff-rm[
```scala
*`val program =`
* `Print("What is your name?", () =>`
*   `Read(name =>`
*     `Print(s"Hello, $name!", () =>`
*       `Stop)))`
*
val ask: Console[String] =
  Print("What is your name?", () =>
    Read(name => name))

val greet: String => Console[Unit] =
  name =>
    Print(s"Hello, $name!", () =>
      Stop)
```
]

---

## Decomposing program

```scala
val ask: Console[String] =
  Print("What is your name?", () =>
    Read(name => name))

val greet: String => Console[Unit] =
 name =>
   Print(s"Hello, $name!", () =>
     Stop)
```

---

## Decomposing program

```scala
val ask: Console[String] =
  Print("What is your name?", () =>
    Read(name => `name`))

val greet: String => Console[Unit] =
 name =>
   Print(s"Hello, $name!", () =>
     Stop)
```

---

## Decomposing program

```scala
val ask: Console[String] =
  Print("What is your name?", () =>
    Read(name => `name`))

val greet: String => Console[Unit] =
 name =>
   Print(s"Hello, $name!", () =>
     Stop)
// ⛔ Found:    (name : String)
//   Required: Console[A]
```
---

## Unconstraining next

.diff-rm[
```scala
enum Console[A]:
* case Print(msg: String, next: () => `Console[A]`)
* case Read(next: String => `Console[A]`)
  case Stop extends Console[Unit]
```
]

---

## Unconstraining next

.diff-add[
```scala
enum Console[A]:
* case Print(msg: String, next: () => `A`)
* case Read(next: String => `A`)
  case Stop extends Console[Unit]
```
]

---

## Unconstraining next

```scala
val ask: Console[String] =
  Print("What is your name?", () =>
    Read(name => name))

val greet: String => Console[Unit] =
 name =>
   Print(s"Hello, $name!", () =>
     Stop)
```

---

## Unconstraining next

```scala
val ask: Console[String] =
  `Print`("What is your name?", () =>
    Read(name => name))

val greet: String => Console[Unit] =
 name =>
   Print(s"Hello, $name!", () =>
     Stop)
```

---

## Unconstraining next

```scala
val ask: Console[String] =
  Print("What is your name?", () =>
    `Read`(name => name))

val greet: String => Console[Unit] =
 name =>
   Print(s"Hello, $name!", () =>
     Stop)
```

---

## Unconstraining next

```scala
val ask: Console[String] =
  Print("What is your name?", () =>
    Read(name => `name`))

val greet: String => Console[Unit] =
 name =>
   Print(s"Hello, $name!", () =>
     Stop)
```

---

## Unconstraining next

.diff-rm[
```scala
*val ask: `Console[String]` =
  Print("What is your name?", () =>
    Read(name => name))

val greet: String => Console[Unit] =
 name =>
   Print(s"Hello, $name!", () =>
     Stop)
```
]

---

## Unconstraining next

.diff-add[
```scala
*val ask: `Console[Console[String]]` =
  Print("What is your name?", () =>
    Read(name => name))

val greet: String => Console[Unit] =
 name =>
   Print(s"Hello, $name!", () =>
     Stop)
```
]

---

## Unconstraining next

.diff-rm[
```scala
val ask: Console[Console[String]] =
  Print("What is your name?", () =>
    Read(name => name))

val greet: String => Console[Unit] =
 name =>
   Print(s"Hello, $name!", () =>
*    `Stop`)
```
]

---

## Unconstraining next

.diff-add[
```scala
val ask: Console[Console[String]] =
  Print("What is your name?", () =>
    Read(name => name))

val greet: String => Console[Unit] =
 name =>
   Print(s"Hello, $name!", () =>
*    `()`)
```
]

---

## Simplifying Console

.diff-rm[
```scala
enum Console[A]:
  case Print(msg: String, next: () => A)
  case Read(next: String => A)
* `case Stop extends Console[Unit]`
```
]

---

## Simplifying Console

```scala
enum Console[A]:
  case Print(msg: String, next: () => A)
  case Read(next: String => A)

```

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    eval(next())

case Read(next) =>
    val in = scala.io.StdIn.readLine()
    eval(next(in))

case Stop => ()
```

---

## Evaluation

.diff-rm[
```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    eval(next())

case Read(next) =>
    val in = scala.io.StdIn.readLine()
    eval(next(in))
*
* `case Stop => ()`
```
]

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    eval(next())

case Read(next) =>
    val in = scala.io.StdIn.readLine()
    eval(next(in))
```

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    `eval`(next())

case Read(next) =>
    val in = scala.io.StdIn.readLine()
    `eval`(next(in))
```

---

## Evaluation

```scala
def eval[A](console: `Console[A]`): A = console match
  case Print(msg, next) =>
    println(msg)
    eval(next())

case Read(next) =>
    val in = scala.io.StdIn.readLine()
    eval(next(in))
```

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    eval(`next()`)

case Read(next) =>
    val in = scala.io.StdIn.readLine()
    eval(`next(in)`)
```

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    eval(`next()`)

case Read(next) =>
    val in = scala.io.StdIn.readLine()
    eval(`next(in)`)
// ⛔ Found:    A
//   Required: Console[A]
```

---

## Evaluation

```scala
def eval[A](console: Console[A]): `A` = console match
  case Print(msg, next) =>
    println(msg)
    eval(next())

case Read(next) =>
    val in = scala.io.StdIn.readLine()
    eval(next(in))
```

---

## Evaluation

.diff-rm[
```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
*   `eval(`next()`)`

case Read(next) =>
    val in = scala.io.StdIn.readLine()
*   `eval(`next(in)`)`
```
]

---

## Evaluation

```scala
def eval[A](console: Console[A]): A = console match
  case Print(msg, next) =>
    println(msg)
    next()

case Read(next) =>
    val in = scala.io.StdIn.readLine()
    next(in)

```

---

## Chained evaluation

```scala
val ask: Console[Console[String]] =
  Print("What is your name?", () =>
    Read(name => name))

val greet: String => Console[Unit] =
  name =>
    Print(s"Hello, $name!", () =>
      ())

```

---

## Chained evaluation

```scala
val ask: Console[`Console[String]`] =
  Print("What is your name?", () =>
    Read(name => name))

val greet: String => Console[`Unit`] =
  name =>
    Print(s"Hello, $name!", () =>
      ())
```

---

## Chained evaluation

```scala
enum Chain:
```

---

## Chained evaluation

---

## Chained evaluation

---

## Chained evaluation

---

## Chained evaluation

---

## Chained evaluation

```scala
def evalChain[A](chain: Chain[A]): A = ???
```

---

## Chained evaluation

```scala
def evalChain[A](chain: `Chain[A]`): A = ???
```

---

## Chained evaluation

---

## Chained evaluation

.diff-add[
```scala
*def evalChain[A](chain: Chain[A]): A = `chain match`
* `case Done(a)       => ???`
* `case Next(console) => ???`
```
]

---

## Chained evaluation

```scala
def evalChain[A](chain: Chain[A]): A = chain match
  case Done(`a`)       => ???
  case Next(console) => ???
```

---

## Chained evaluation

```scala
def evalChain[A](chain: Chain[A]): `A` = chain match
  case Done(a)       => ???
  case Next(console) => ???
```

---

## Chained evaluation

.diff-rm[
```scala
def evalChain[A](chain: Chain[A]): A = chain match
* case Done(a)       => `???`
  case Next(console) => ???
```
]

---

## Chained evaluation

.diff-add[
```scala
def evalChain[A](chain: Chain[A]): A = chain match
* case Done(a)       => `a`
  case Next(console) => ???
```
]

---

## Chained evaluation

```scala
def evalChain[A](chain: Chain[A]): A = chain match
  case Done(a)       => a
  case Next(`console`) => ???
```

---

## Chained evaluation

```scala
def evalChain[A](chain: Chain[A]): `A` = chain match
  case Done(a)       => a
  case Next(console) => ???
```

---

## Chained evaluation

```scala
def `evalChain`[A](chain: Chain[A]): A = chain match
  case Done(a)       => a
  case Next(console) => ???
```

---

## Chained evaluation

```scala
def evalChain[A](chain: Chain[A]): A = chain match
  case Done(a)       => a
  case Next(console) => ???
```

---

## Chained evaluation

```scala
def evalChain[A](chain: Chain[A]): A = chain match
  case Done(a)       => a
  case Next(console) => ???
```

---

## Chained evaluation

.diff-rm[
```scala
def evalChain[A](chain: Chain[A]): A = chain match
  case Done(a)       => a
* case Next(console) => `???`
```
]

---

## Chained evaluation

.diff-add[
```scala
def evalChain[A](chain: Chain[A]): A = chain match
  case Done(a)       => a
* case Next(console) => `evalChain(eval(console))`
```
]

---

## Decomposed program

```scala
val ask: Console[Console[String]] =
  Print("What is your name?", () =>
    Read(name => name))

val greet: String => Console[Unit] =
  name =>
    Print(s"Hello, $name!", () =>
      ())
```

---

## Decomposed program

.diff-rm[
```scala
*val ask: `Console[Console[String]]` =
  Print("What is your name?", () =>
    Read(name => name))

*val greet: String => `Console[Unit]` =
  name =>
    Print(s"Hello, $name!", () =>
      ())
```
]

---

## Decomposed program

.diff-add[
```scala
*val ask: `Chain[String]` =
  Print("What is your name?", () =>
    Read(name => name))

*val greet: String => `Chain[Unit]` =
  name =>
    Print(s"Hello, $name!", () =>
      ())
```
]

---

## Decomposed program

.diff-rm[
```scala
val ask: Chain[String] =
  Print("What is your name?", () =>
*   Read(name => `name`))

val greet: String => Chain[Unit] =
  name =>
    Print(s"Hello, $name!", () =>
*     `()`)
```
]

---

## Decomposed program

.diff-add[
```scala
val ask: Chain[String] =
  Print("What is your name?", () =>
*   Read(name => `Done(name)`))

val greet: String => Chain[Unit] =
  name =>
    Print(s"Hello, $name!", () =>
*     `Done(())`)
```
]

---

## Decomposed program

.diff-rm[
```scala
val ask: Chain[String] =
  `Print`("What is your name?", () =>
    `Read`(name => Done(name)))

val greet: String => Chain[Unit] =
  name =>
    `Print`(s"Hello, $name!", () =>
      Done(()))
```
]

---

## Decomposed program

.diff-add[
```scala
val ask: Chain[String] =
  `Next(Print`("What is your name?", () =>
    `Next(Read`(name => Done(name)))`))`

val greet: String => Chain[Unit] =
  name =>
    `Next(Print`(s"Hello, $name!", () =>
      Done(()))`)`
```
]

---

## Key takeaways

* We now have a specific type for chained console statements.

* We know how to evaluate both single and chained statements.

* We have decomposed our initial program in simpler, composable chunks.

---

# Composing programs

---

## Composing program

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
    Next(Print(s"Hello, $name!", () =>
      Done(())))
```

---

## Composing program

.diff-add[
```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
    Next(Print(s"Hello, $name!", () =>
      Done(())))

*`val program: Chain[Unit] =`
* `???`
```
]

---

## Composing statements

```scala
val ask: `Chain[String]` =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
    Next(Print(s"Hello, $name!", () =>
      Done(())))

val program: Chain[Unit] =
  ???
```

---

## Composing statements

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
    Next(Print(s"Hello, $name!", () =>
      Done(())))

val program: `Chain[Unit]` =
  ???
```

---

## Composing statements

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: `String => Chain[Unit]` =
  name =>
    Next(Print(s"Hello, $name!", () =>
      Done(())))

val program: Chain[Unit] =
  ???
```

---

## Composing statements

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
    Next(Print(s"Hello, $name!", () =>
      Done(())))

val program: Chain[Unit] =
  ???
```

---

## Composing statements

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
    Next(Print(s"Hello, $name!", () =>
      Done(())))

val program: Chain[Unit] =
  ???
```

---

## Composing statements

.diff-rm[
```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
    Next(Print(s"Hello, $name!", () =>
      Done(())))

val program: Chain[Unit] =
* `???`
```
]

---

## Composing statements

.diff-add[
```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
    Next(Print(s"Hello, $name!", () =>
      Done(())))

val program: Chain[Unit] =
* `ask.flatMap(greet)`
```
]

---

## Chain as a Monad

```scala
given `Monad[Chain]` with
  extension [A](cchain: Chain[Chain[A]])
    def flatten: Chain[A] = ???

extension [A](chain: Chain[A])
    def map[B](f: A => B): Chain[B] = ???

extension [A](a: A)
    def pure: Chain[A] = ???
```

---

## Chain as a Monad

```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
    def `flatten`: Chain[A] = ???

extension [A](chain: Chain[A])
    def map[B](f: A => B): Chain[B] = ???

extension [A](a: A)
    def `pure`: Chain[A] = ???
```

---

## Chain as a Monad

```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
    def flatten: Chain[A] = ???

extension [A](chain: Chain[A])
    def `map`[B](f: A => B): Chain[B] = ???

extension [A](a: A)
    def pure: Chain[A] = ???
```

---

## Chain as a Monad

```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
    def flatten: Chain[A] = ???

extension [A](chain: Chain[A])
    def map[B](f: A => B): Chain[B] = ???

* extension [A](a: A)
*   def pure: Chain[A] = ???
```

---

## Chain.pure

```scala
extension [A](a: A)
  def pure: Chain[A] = ???
```

---

## Chain.pure

```scala
extension [A](a: `A`)
  def pure: Chain[A] = ???
```

---

## Chain.pure

```scala
extension [A](a: A)
  def pure: `Chain[A]` = ???
```

---

## Chain.pure

---

## Chain.pure

---

## Chain.pure

.diff-rm[
```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
    def flatten: Chain[A] = ???

extension [A](chain: Chain[A])
    def map[B](f: A => B): Chain[B] = ???

extension [A](a: A)
*   def pure: Chain[A] = `???`
```
]

---

## Chain.pure

.diff-add[
```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
    def flatten: Chain[A] = ???

extension [A](chain: Chain[A])
    def map[B](f: A => B): Chain[B] = ???

extension [A](a: A)
*   def pure: Chain[A] = `Done(a)`
```
]

---

## Chain.map

```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
    def flatten: Chain[A] = ???

* extension [A](chain: Chain[A])
*   def map[B](f: A => B): Chain[B] = ???

extension [A](a: A)
    def pure: Chain[A] = Done(a)
```

---

## Chain.map

```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): Chain[B] = ???
```

---

## Chain.map

```scala
extension [A](chain: `Chain[A]`)
  def map[B](f: A => B): Chain[B] = ???
```

---

## Chain.map

---

## Chain.map

.diff-add[
```scala
extension [A](chain: Chain[A])
* def map[B](f: A => B): Chain[B] = `chain match`
*   `case Done(a)  => ???`
*   `case Next(ca) => ???`
```
]

---

## Chain.map (Done)

```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): Chain[B] = chain match
    case Done(`a`)  => ???
    case Next(ca) => ???
```

---

## Chain.map (Done)

```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): `Chain[B]` = chain match
    case Done(a)  => ???
    case Next(ca) => ???
```

---

## Chain.map (Done)

```scala
extension [A](chain: Chain[A])
  def map[B](`f: A => B`): Chain[B] = chain match
    case Done(a)  => ???
    case Next(ca) => ???
```

---

## Chain.map (Done)

```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): Chain[B] = chain match
    case Done(a)  => ???
    case Next(ca) => ???
```

---

## Chain.map (Done)

```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): Chain[B] = chain match
    case Done(a)  => ???
    case Next(ca) => ???
```

---

## Chain.map (Done)

.diff-rm[
```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): Chain[B] = chain match
*   case Done(a)  => `???`
    case Next(ca) => ???
```
]

---

## Chain.map (Done)

.diff-add[
```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): Chain[B] = chain match
*   case Done(a)  => `Done(f(a))`
    case Next(ca) => ???
```
]

---

## Chain.map (Next)

```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): Chain[B] = chain match
    case Done(a)  => Done(f(a))
    case Next(`ca`) => ???
```

---

## Chain.map (Next)

```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): `Chain[B]` = chain match
    case Done(a)  => Done(f(a))
    case Next(ca) => ???
```

---

## Chain.map (Next)

```scala
extension [A](chain: Chain[A])
  def map[B](`f: A => B`): Chain[B] = chain match
    case Done(a)  => Done(f(a))
    case Next(ca) => ???
```

---

## Chain.map (Next)

```scala
extension [A](chain: Chain[A])
  def `map`[B](f: A => B): Chain[B] = chain match
    case Done(a)  => Done(f(a))
    case Next(ca) => ???
```

---

## Chain.map (Next)

```scala
extension [A](chain: Chain[A])
  def map[B](f: `A => B`): Chain[B] = chain match
    case Done(a)  => Done(f(a))
    case Next(ca) => ???
```
---

## Chain.map (Next)

```scala
extension [A](chain: `Chain[A]`)
  def map[B](f: A => B): `Chain[B]` = chain match
    case Done(a)  => Done(f(a))
    case Next(ca) => ???
```

---

## Chain.map (Next)

```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): Chain[B] = chain match
    case Done(a)  => Done(f(a))
    case Next(ca) => ???
```

---

## Chain.map (Next)

```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): Chain[B] = chain match
    case Done(a)  => Done(f(a))
    case Next(ca) => ???
```

---

## Chain.map (Next)

```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): Chain[B] = chain match
    case Done(a)  => Done(f(a))
    case Next(ca) => ???
```

---

## Chain.map (Next)

.diff-rm[
```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): Chain[B] = chain match
    case Done(a)  => Done(f(a))
*   case Next(ca) => `???`
```
]

---

## Chain.map (Next)

.diff-add[
```scala
extension [A](chain: Chain[A])
  def map[B](f: A => B): Chain[B] = chain match
    case Done(a)  => Done(f(a))
*   case Next(ca) => `Next(ca.map(_.map(f)))`
```
]

---

## Chain.map

.diff-rm[
```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
    def flatten: Chain[A] = ???

extension [A](chain: Chain[A])
*   def map[B](f: A => B): Chain[B] = `???`

extension [A](a: A)
    def pure: Chain[A] = Done(a)
```
]

---

## Chain.map

.diff-add[
```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
    def flatten: Chain[A] = ???

extension [A](chain: Chain[A])
*   def map[B](f: A => B): Chain[B] = `chain match`
*     `case Done(a)  => Done(f(a))`
*     `case Next(ca) => Next(ca.map(_.map(f)))`

extension [A](a: A)
    def pure: Chain[A] = Done(a)
```
]

---

## Chain.flatten

```scala
given Monad[Chain] with
* extension [A](cchain: Chain[Chain[A]])
*   def flatten: Chain[A] = ???

extension [A](chain: Chain[A])
    def map[B](f: A => B): Chain[B] = chain match
      case Done(a)  => Done(f(a))
      case Next(ca) => Next(ca.map(_.map(f)))

extension [A](a: A)
    def pure: Chain[A] = Done(a)
```

---

## Chain.flatten

```scala
extension [A](cchain: Chain[Chain[A]])
  def flatten: Chain[A] = ???
```

---

## Chain.flatten

```scala
extension [A](cchain: `Chain[Chain[A]]`)
  def flatten: Chain[A] = ???
```

---

## Chain.flatten

---

## Chain.flatten

.diff-add[
```scala
extension [A](cchain: Chain[Chain[A]])
* def flatten: Chain[A] = `cchain match`
*   `case Done(ca)  => ???`
*   `case Next(cca) => ???`
```
]

---

## Chain.flatten (Done)

```scala
extension [A](cchain: Chain[Chain[A]])
  def flatten: Chain[A] = cchain match
    case Done(`ca`)  => ???
    case Next(cca) => ???
```

---

## Chain.flatten (Done)

```scala
extension [A](cchain: Chain[Chain[A]])
  def flatten: `Chain[A]` = cchain match
    case Done(ca)  => ???
    case Next(cca) => ???
```

---

## Chain.flatten (Done)

.diff-rm[
```scala
extension [A](cchain: Chain[Chain[A]])
  def flatten: Chain[A] = cchain match
*   case Done(ca)  => `???`
    case Next(cca) => ???
```
]

---

## Chain.flatten (Done)

.diff-add[
```scala
extension [A](cchain: Chain[Chain[A]])
  def flatten: Chain[A] = cchain match
*   case Done(ca)  => `ca`
    case Next(cca) => ???
```
]

---

## Chain.flatten (Next)

```scala
extension [A](cchain: Chain[Chain[A]])
  def flatten: Chain[A] = cchain match
    case Done(ca)  => ca
    case Next(`cca`) => ???
```

---

## Chain.flatten (Next)

```scala
extension [A](cchain: Chain[Chain[A]])
  def flatten: `Chain[A]` = cchain match
    case Done(ca)  => ca
    case Next(cca) => ???
```

---

## Chain.flatten (Next)

```scala
extension [A](cchain: Chain[Chain[A]])
  def `flatten`: Chain[A] = cchain match
    case Done(ca)  => ca
    case Next(cca) => ???
```

---

## Chain.flatten (Next)

```scala
extension [A](cchain: `Chain[Chain[A]]`)
  def flatten: `Chain[A]` = cchain match
    case Done(ca)  => ca
    case Next(cca) => ???
```

---

## Chain.flatten (Next)

```scala
extension [A](cchain: Chain[Chain[A]])
  def flatten: Chain[A] = cchain match
    case Done(ca)  => ca
    case Next(cca) => ???
```

---

## Chain.flatten (Next)

```scala
extension [A](cchain: Chain[Chain[A]])
  def flatten: Chain[A] = cchain match
    case Done(ca)  => ca
    case Next(cca) => ???
```

---

## Chain.flatten (Next)

```scala
extension [A](cchain: Chain[Chain[A]])
  def flatten: Chain[A] = cchain match
    case Done(ca)  => ca
    case Next(cca) => ???
```

---

## Chain.flatten (Next)

.diff-rm[
```scala
extension [A](cchain: Chain[Chain[A]])
  def flatten: Chain[A] = cchain match
    case Done(ca)  => ca
*   case Next(cca) => `???`
```
]

---

## Chain.flatten (Next)

.diff-add[
```scala
extension [A](cchain: Chain[Chain[A]])
  def flatten: Chain[A] = cchain match
    case Done(ca)  => ca
*   case Next(cca) => `Next(cca.map(_.flatten))`
```
]

---

## Chain.flatten

.diff-rm[
```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
*   def flatten: Chain[A] = `???`

extension [A](chain: Chain[A])
    def map[B](f: A => B): Chain[B] = chain match
      case Done(a)  => Done(f(a))
      case Next(ca) => Next(ca.map(_.map(f)))

extension [A](a: A)
    def pure: Chain[A] = Done(a)
```
]

---

## Chain.flatten

.diff-add[
```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
*   def flatten: Chain[A] = `cchain match`
*     `case Done(ca)  => ca`
*     `case Next(cca) => Next(cca.map(_.flatten))`

extension [A](chain: Chain[A])
    def map[B](f: A => B): Chain[B] = chain match
      case Done(a)  => Done(f(a))
      case Next(ca) => Next(ca.map(_.map(f)))

extension [A](a: A)
    def pure: Chain[A] = Done(a)
```
]

---

## Console as a Functor

```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
    def flatten: Chain[A] = cchain match
      case Done(ca)  => ca
      case Next(cca) => Next(cca.`map`(_.flatten))

extension [A](chain: Chain[A])
    def map[B](f: A => B): Chain[B] = chain match
      case Done(a)  => Done(f(a))
      case Next(ca) => Next(ca.`map`(_.map(f)))

extension [A](a: A)
    def pure: Chain[A] = Done(a)
```

---

## Console as a Functor

```scala
given Functor[Console] with
  extension [A](console: Console[A])
    def `map`[B](f: A => B): Console[B] = ???
```

---

## Console as a Functor

```scala
given Functor[Console] with
  extension [A](console: `Console[A]`)
    def map[B](f: A => B): Console[B] = ???
```

---

## Console as a Functor

.diff-rm[
```scala
given Functor[Console] with
  extension [A](console: Console[A])
*   def map[B](f: A => B): Console[B] = `???`
```
]

---

## Console as a Functor

.diff-add[
```scala
given Functor[Console] with
  extension [A](console: Console[A])
*   def map[B](f: A => B): Console[B] = `console match`
*     `case Print(msg, next) => ???`
*     `case Read(next)       => ???`
```
]

---

## Console as a Functor

```scala
given Functor[Console] with
  extension [A](console: Console[A])
    def map[B](f: A => B): Console[B] = console match
      case Print(msg, `next`) => ???
      case Read(`next`)       => ???
```

---

## Console as a Functor

```scala
given Functor[Console] with
  extension [A](console: Console[A])
    def map[B](f: `A => B`): Console[B] = console match
      case Print(msg, next) => ???
      case Read(next)       => ???
```

---

## Console as a Functor

.diff-rm[
```scala
given Functor[Console] with
  extension [A](console: Console[A])
    def map[B](f: A => B): Console[B] = console match
*     case Print(msg, next) => `???`
*     case Read(next)       => `???`
```
]

---

## Console as a Functor

.diff-add[
```scala
given Functor[Console] with
  extension [A](console: Console[A])
    def map[B](f: A => B): Console[B] = console match
*     case Print(msg, next) => `Print(msg, next andThen f)`
*     case Read(next)       => `Read(next andThen f)`
```
]

---

## Composing programs

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
    Next(Print(s"Hello, $name!", () =>
      Done(())))

val program: Chain[Unit] =
  `ask.flatMap(greet)`
```

---

## Key takeaways

* `Chain` is now a `Monad`.

* `Console` is now a `Functor`.

* Our code is very verbose...

---

# Extracting atomic statements

---

## Atomic statements

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
    Next(Print(s"Hello, $name!", () =>
      Done(())))

val program: Chain[Unit] =
  ask.flatMap(greet)
```

---

## Atomic statements

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    `Next(Read(name => Done(name)))`))

val greet: String => Chain[Unit] =
  name =>
    Next(Print(s"Hello, $name!", () =>
      Done(())))

val program: Chain[Unit] =
  ask.flatMap(greet)
```

---

## Atomic statements

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
    `Next(Print(s"Hello, $name!", () =>`
      `Done(())))`

val program: Chain[Unit] =
  ask.flatMap(greet)
```

---

## Atomic print

```scala
def print(msg: String): Chain[Unit] =
  Next(Print(msg, () => Done(())))
```

---

## Atomic print

```scala
def print(`msg: String`): Chain[Unit] =
  Next(Print(msg, () => Done(())))
```

---

## Atomic print

```scala
def print(msg: String): Chain[Unit] =
  `Next(Print(msg, () => Done(())))`
```

---

## Atomic print

.diff-rm[
```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
*   `Next(Print(s"Hello, $name!", () =>`
*     `Done(())))`

val program: Chain[Unit] =
  ask.flatMap(greet)
```
]

---

## Atomic print

.diff-add[
```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    Next(Read(name => Done(name)))))

val greet: String => Chain[Unit] =
  name =>
*   `print(s"Hello, $name")`

val program: Chain[Unit] =
  ask.flatMap(greet)
```
]

---

## Atomic read

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    `Next(Read(name => Done(name)))`))

val greet: String => Chain[Unit] =
  name =>
    print(s"Hello, $name")

val program: Chain[Unit] =
  ask.flatMap(greet)
```

---

## Atomic read

.diff-add[
```scala
def print(msg: String): Chain[Unit] =
  Next(Print(msg, () => Done(())))
*
*`def read: Chain[String] =`
* `Next(Read(str => Done(str)))`
```
]

---

## Factoring out common code

```scala
def print(msg: String): Chain[Unit] =
  Next(Print(msg, () => Done(())))

def read: Chain[String] =
  Next(Read(str => Done(str)))
```

---

## Factoring out common code

```scala
def print(msg: String): Chain[Unit] =
  Next(Print(msg, `() => Done(())`))

def read: Chain[String] =
  Next(Read(`str => Done(str)`))
```

---

## Factoring out common code

```scala
def print(msg: String): Chain[Unit] =
  Next(`Print(`msg, () => Done(())`)`)

def read: Chain[String] =
  Next(`Read(`str => Done(str)`)`)
```

---

## Factoring out common code

```scala
def print(msg: String): Chain[Unit] =
  Next(`Print(msg, () => Done(()))`)

def read: Chain[String] =
  Next(`Read(str => Done(str))`)
```

---

## Factoring out common code

```scala
def print(msg: String): Chain[Unit] =
  Next(Print(msg, () => Done(())))

def read: Chain[String] =
  Next(Read(str => Done(str)))
```

---

## Factoring out common code

```scala
def print(msg: String): Chain[Unit] =
  Next(Print(msg, () => Done(())))

def read: Chain[String] =
  Next(Read(str => Done(str)))
```

---

## Factoring out common code

def read: Chain[String] =
* Next(Read(str => `Done(str)`))
```
]

---

## Factoring out common code

.diff-add[
```scala
def print(msg: String): Chain[Unit] =
* Next(Print(msg, () => `()).map(Done.apply)`)

def read: Chain[String] =
* Next(Read(str => `str).map(Done.apply)`)
```
]

---

## Factoring out common code

```scala
def print(msg: String): Chain[Unit] =
  Next(`Print(msg, () => ())`.map(Done.apply))

def read: Chain[String] =
  Next(`Read(str => str)`.map(Done.apply))
```

---

## Factoring out common code

```scala
def print(msg: String): Chain[Unit] =
  Next(Print(msg, () => ())`.map(Done.apply)`)

def read: Chain[String] =
  Next(Read(str => str)`.map(Done.apply)`)
```

---

## Factoring out common code

```scala
def print(msg: String): Chain[Unit] =
  `Next(`Print(msg, () => ()).map(Done.apply)`)`

def read: Chain[String] =
  `Next(`Read(str => str).map(Done.apply)`)`
```

---

## Factoring out common code

```scala
def print(msg: String): Chain[Unit] =
  Next(Print(msg, () => ()).map(Done.apply))

def read: Chain[String] =
  Next(Read(str => str).map(Done.apply))
```

---

## Factoring out common code

.diff-add[
```scala
*`def liftChain[A](console: Console[A]): Chain[A] =`
* `Next(console.map(Done.apply))`
*
def print(msg: String): Chain[Unit] =
  Next(Print(msg, () => ()).map(Done.apply))

def read: Chain[String] =
  Next(Read(str => str).map(Done.apply))
```
]

---

## Factoring out common code

def print(msg: String): Chain[Unit] =
* `Next(`Print(msg, () => ())`.map(Done.apply))`

def read: Chain[String] =
* `Next(`Read(str => str)`.map(Done.apply))`
```
]

---

## Factoring out common code

.diff-add[
```scala
def liftChain[A](console: Console[A]): Chain[A] =
  Next(console.map(Done.apply))

def print(msg: String): Chain[Unit] =
* `liftChain(`Print(msg, () => ())`)`

def read: Chain[String] =
* `liftChain(`Read(str => str)`)`
```
]

---

## Composing atomic statements

.diff-rm[
```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
*   `Next(Read(name => Done(name)))`))

val greet: String => Chain[Unit] =
  name =>
    print(s"Hello, $name")

val program: Chain[Unit] =
  ask.flatMap(greet)
```
]

---

## Composing atomic statements

val greet: String => Chain[Unit] =
  name =>
    print(s"Hello, $name")

val program: Chain[Unit] =
  ask.flatMap(greet)
```
]

---

## Composing atomic statements

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", `() =>`
    `read`))

val greet: String => Chain[Unit] =
  name =>
    print(s"Hello, $name")

val program: Chain[Unit] =
  ask.flatMap(greet)
```

---

## Composing atomic statements

```scala
val ask: Chain[String] =
  `Next(Print(`"What is your name?", () =>
    read`))`

val greet: String => Chain[Unit] =
  name =>
    print(s"Hello, $name")

val program: Chain[Unit] =
  ask.flatMap(greet)
```

---

## Composing atomic statements

```scala
val ask: `Chain[String]` =
  Next(Print("What is your name?", () =>
    read))

val greet: String => Chain[Unit] =
  name =>
    print(s"Hello, $name")

val program: Chain[Unit] =
  ask.flatMap(greet)
```

---

## Composing atomic statements

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    read))

val greet: String => Chain[Unit] =
  name =>
    print(s"Hello, $name")

val program: Chain[Unit] =
  ask.flatMap(greet)
```

---

## Composing atomic statements

```scala
val ask: Chain[String] =
  Next(Print("What is your name?", () =>
    read))

val greet: String => Chain[Unit] =
  name =>
    print(s"Hello, $name")

val program: Chain[Unit] =
  ask.flatMap(greet)
```

---

## Composing atomic statements

.diff-add[
```scala
val ask: Chain[String] =
* Next(Print("What is your name?", `() => ())`
*   `.flatMap(_ => `read))

val greet: String => Chain[Unit] =
  name =>
    print(s"Hello, $name")

val program: Chain[Unit] =
  ask.flatMap(greet)
```
]

---

## Composing atomic statements

.diff-rm[
```scala
val ask: Chain[String] =
* `Next(Print("What is your name?", () => ())`
    .flatMap(_ => read))

val greet: String => Chain[Unit] =
  name =>
    print(s"Hello, $name")

val program: Chain[Unit] =
  ask.flatMap(greet)
```
]

---

## Composing atomic statements

.diff-add[
```scala
val ask: Chain[String] =
* `print("What is your name?")`
    .flatMap(_ => read))

val greet: String => Chain[Unit] =
  name =>
    print(s"Hello, $name")

val program: Chain[Unit] =
  ask.flatMap(greet)
```
]

---

## Composing atomic statements

```scala
val program: Chain[Unit] = for
  _    <- print("What is your name?")
  name <- read
  _    <- print(s"Hello, $name!")
yield ()

```

---

## Key takeaways

* We can now write atomic console statements into a `Chain`.

* These compose comfortably using standard for-comprehensions.

* It feels like `Chain` might not be specific to `Console`...

---

# Generalising Chain

---

## Actual requirements

```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
    def flatten: Chain[A] = cchain match
      case Done(ca)  => ca
      case Next(cca) => Next(cca.`map`(_.flatten))

extension [A](chain: Chain[A])
    def map[B](f: A => B): Chain[B] = chain match
      case Done(a)  => Done(f(a))
      case Next(ca) => Next(ca.`map`(_.map(f)))

extension [A](a: A)
    def pure: Chain[A] = Done(a)
```

---

## Actual requirements

```scala
def liftChain[A](console: Console[A]): Chain[A] =
  Next(console.`map`(Done.apply))

def print(msg: String): Chain[Unit] =
  liftChain(Print(msg, () => ()))

def read: Chain[String] =
  liftChain(Read(str => str))
```

---

## Generalising Chain

---

## Generalising Chain

.diff-add[
```scala
*enum Chain[`F[_], `A]:
* case Next(value: `F`[Chain[A]])
  case Done(a: A)
```
]

---

## Generalising Chain

```scala
given Monad[Chain] with
  extension [A](cchain: Chain[Chain[A]])
    def flatten: Chain[A] = cchain match
      case Done(ca)  => ca
      case Next(cca) => Next(cca.map(_.flatten))

extension [A](chain: Chain[A])
    def map[B](f: A => B): Chain[B] = chain match
      case Done(a)  => Done(f(a))
      case Next(ca) => Next(ca.map(_.map(f)))

extension [A](a: A)
    def pure: Chain[A] = Done(a)
```

---

## Generalising Chain

.diff-add[
```scala
*given `[F[_]]: `Monad[Chain`[F, _]`] with
* extension [A](cchain: Chain[`F, `Chain[`F, `A]])
*   def flatten: Chain[`F, `A] = cchain match
      case Done(ca)  => ca
      case Next(cca) => Next(cca.map(_.flatten))

* extension [A](chain: Chain[`F, `A])
*   def map[B](f: A => B): Chain[`F, `B] = chain match
      case Done(a)  => Done(f(a))
      case Next(ca) => Next(ca.map(_.map(f)))

extension [A](a: A)
*   def pure: Chain[`F, `A] = Done(a)
```
]

---

## Generalising Chain

```scala
given [F[_]]: Monad[Chain[F, _]] with
  extension [A](cchain: Chain[F, Chain[F, A]])
    def flatten: Chain[F, A] = cchain match
      case Done(ca)  => ca
      case Next(cca) => Next(cca.`map`(_.flatten))

extension [A](chain: Chain[F, A])
    def map[B](f: A => B): Chain[F, B] = chain match
      case Done(a)  => Done(f(a))
      case Next(ca) => Next(ca.`map`(_.map(f)))

extension [A](a: A)
    def pure: Chain[F, A] = Done(a)
```

---

## Generalising Chain

.diff-add[
```scala
*given [F[_]`: Functor`]: Monad[Chain[F, _]] with
  extension [A](cchain: Chain[F, Chain[F, A]])
    def flatten: Chain[F, A] = cchain match
      case Done(ca)  => ca
      case Next(cca) => Next(cca.map(_.flatten))

extension [A](chain: Chain[F, A])
    def map[B](f: A => B): Chain[F, B] = chain match
      case Done(a)  => Done(f(a))
      case Next(ca) => Next(ca.map(_.map(f)))

extension [A](a: A)
    def pure: Chain[F, A] = Done(a)
```
]

---

## Generalising Chain

.diff-rm[
```scala
*def liftChain[A](console: `Console`[A]): Chain[A] =
  Next(console.map(Done.apply))

def print(msg: String): Chain[Unit] =
  liftChain(Print(msg, () => ()))

def read: Chain[String] =
  liftChain(Read(str => str))
```
]

---

## Generalising Chain

.diff-add[
```scala
*def liftChain[`F[_], `A](console: F[A]): Chain[`F, `A] =
  Next(console.map(Done.apply))

def print(msg: String): Chain[Unit] =
  liftChain(Print(msg, () => ()))

def read: Chain[String] =
  liftChain(Read(str => str))
```
]

---

## Generalising Chain

.diff-rm[
```scala
*def liftChain[F[_], A](`console`: F[A]): Chain[F, A] =
* Next(`console`.map(Done.apply))

def print(msg: String): Chain[Unit] =
  liftChain(Print(msg, () => ()))

def read: Chain[String] =
  liftChain(Read(str => str))
```
]

---

## Generalising Chain

def print(msg: String): Chain[Unit] =
  liftChain(Print(msg, () => ()))

def read: Chain[String] =
  liftChain(Read(str => str))
```
]

---

## Generalising Chain

*def print(msg: String): Chain[`Console, `Unit] =
  liftChain(Print(msg, () => ()))

*def read: Chain[`Console, `String] =
  liftChain(Read(str => str))
```
]

---

## Generalising Chain

```scala
def liftChain[F[_], A](fa: F[A]): Chain[F, A] =
  Next(`fa.map`(Done.apply))

def print(msg: String): Chain[Console, Unit] =
  liftChain(Print(msg, () => ()))

def read: Chain[Console, String] =
  liftChain(Read(str => str))
```

---

## Generalising Chain

.diff-add[
```scala
*def liftChain[F[_]`: Functor`, A](fa: F[A]): Chain[F, A] =
  Next(fa.map(Done.apply))

def print(msg: String): Chain[Console, Unit] =
  liftChain(Print(msg, () => ()))

def read: Chain[Console, String] =
  liftChain(Read(str => str))
```
]

---