def compose3[X, Y, Z](r: Rel3[X, Y], s: Rel3[Y, Z],
                      middleValues: List[Y]): Rel3[X, Z] = {
  val witnesses = middleValues.distinct
  new Rel3[X, Z] {
    def related(x: X, z: Z): Boolean =
      witnesses.exists(y => r.related(x, y) && s.related(y, z))
  }
}

def compose2[X, Y, Z](r: Rel2[X, Y], s: Rel2[Y, Z]): Rel2[X, Z] =
  new Rel2[X, Z] {
    def relatives(x: X): List[Z] =
      r.relatives(x).flatMap(y => s.relatives(y)).distinct
  }

def compose1[X, Y, Z](r: Rel1[X, Y], s: Rel1[Y, Z]): Rel1[X, Z] = {
  val joined = (for {
    (x, y) <- r.pairs
    (middle, z) <- s.pairs
    if y == middle
  } yield (x, z)).distinct
  new Rel1[X, Z] {
    val pairs: List[(X, Z)] = joined
  }
}

trait Rel1[+X, +Y] { val pairs: List[(X, Y)] }
trait Rel2[-X, +Y] { def relatives(x: X): List[Y] }
trait Rel3[-X, -Y] { def related(x: X, y: Y): Boolean }

val strings: Rel2[String, Int] = new Rel2[String, Int] {
  def relatives(x: String): List[Int] = List(x.length)
}
// Unsafe if Rel2 were incorrectly covariant in X:
// val arbitrary: Rel2[Any, Int] = strings
// arbitrary.relatives(7)

final class NoChannels(val name: String) extends Customer {
  def spread(msg: String): Unit = ()
  def cost: Double = 0.0
}

abstract class CustomerDecorator(protected val inner: Customer)
    extends Customer {
  final val name: String = inner.name
  def spread(msg: String): Unit = inner.spread(msg)
  def cost: Double = inner.cost
}

final class OnDiscord(c: Customer, out: Comms)
    extends CustomerDecorator(c) {
  override def spread(msg: String): Unit = {
    super.spread(msg)
    out.sendD(name, msg)
  }
  override def cost: Double = super.cost + 0.01
}

final class OnFacebook(c: Customer, out: Comms)
    extends CustomerDecorator(c) {
  override def spread(msg: String): Unit = {
    super.spread(msg)
    out.sendF(name, msg)
  }
  override def cost: Double = super.cost + 0.05
}

final class OnWhatsApp(c: Customer, out: Comms)
    extends CustomerDecorator(c) {
  override def spread(msg: String): Unit = {
    super.spread(msg)
    out.sendW(name, msg)
  }
  override def cost: Double = super.cost + 0.03
}

def customer(name: String, discord: Boolean, facebook: Boolean,
             whatsapp: Boolean, out: Comms): Customer = {
  var c: Customer = new NoChannels(name)
  if (discord) c = new OnDiscord(c, out)
  if (facebook) c = new OnFacebook(c, out)
  if (whatsapp) c = new OnWhatsApp(c, out)
  c
}

final class Editor {
  private var text = ""
  final class Snapshot private[Editor] (
    private[Editor] val saved: String
  )
  def current: String = text
  def edit(next: String): Unit = { text = next }
  def save(): Snapshot = new Snapshot(text)
  def restore(s: Snapshot): Unit = { text = s.saved }
}

val editor = new Editor
editor.edit("first version")
val saved: editor.Snapshot = editor.save()
editor.edit("later version")
editor.restore(saved)
assert(editor.current == "first version")

trait Named {
  def name: String
}
trait Greeting extends Named {
  def greeting: String = "Welcome, " + name
}
class Account(val name: String)
class WelcomedAccount(name: String) extends Account(name) with Greeting

val example = new WelcomedAccount("reader")
assert(example.greeting == "Welcome, reader")

def makeSet(x: Int): Unit = {
  require(isInMap(x) == -1, "element already present")
  require(used < capacity, "capacity exhausted")
  elements(used) = x
  representatives(used) = x
  used += 1
}

def find(x: Int): Int = {
  val i = isInMap(x)
  require(i >= 0, "unknown element")
  representatives(i)
}

def union(x: Int, y: Int): Unit = {
  val keep = find(x)
  val replace = find(y)
  if (keep != replace) {
    var i = 0
    while (i < used) {
      if (representatives(i) == replace) representatives(i) = keep
      i += 1
    }
  }
}

private def isInMap(x: Int): Int = {
  var i = 0
  while (i < used && elements(i) != x) i += 1
  if (i < used) i else -1
}