Main.scala

/* An attempt at a direct translation of the `$` mechanism.
 *
 * In the book `lazy` can annotate the implementation of a method. The result of a `lazy` method is a
 * suspension of the result type but the type is still the same. In pseudo code
 *
 * trait A { val someMethod: Int }
 * class Impl extends A { def lazy someImplementation: Int }
 *
 * The result type in the interface is `Int` but the implementation's result is a suspension of
 * type `Int`.  I don't see a way to achieve in scala.
 *
 * EDIT: This translation is correct. I had misread the book's definition of the lazy annotaiton.
 */
final class Lazy[+T](susp: => T) {
  lazy val force: T = susp
}

object Lazy {
  def unapply[T](lzy: Lazy[T]): Option[T] = Some(lzy.force)

  given [T]: Conversion[T, Lazy[T]] = Lazy(_)
}

trait Streams {
  type Stream[+T]

  def append[T](s0: Stream[T], s1: Stream[T]): Stream[T]
  def take[T](s: Stream[T], count: Int): Stream[T]
  def drop[T](s: Stream[T], count: Int): Stream[T]
  def toList[T](s: Stream[T]): List[T]
}

object Streams extends Streams {
  sealed trait StreamCell[+T]
  case object SNil extends StreamCell[Nothing]
  case class SCons[T](head: T, rest: Stream[T]) extends StreamCell[T]

  object SCons {
    def apply[T](head: T, rest: => StreamCell[T]): StreamCell[T] = SCons(head, Lazy(rest))
  }

  type Stream[+T] = Lazy[StreamCell[T]]

  /* In the book the pattern match is suspended. In this implementation there is no way I know to
   * hide that suspension. Instead values are forced at different points than in the book.  I don't
   * know if that has an impact on the complexity.
   */
  def append[T](s0: Stream[T], s1: Stream[T]): Stream[T] = Lazy {
    s0 match {
      case Lazy(SNil) => s1.force
      case Lazy(SCons(head, rest)) => SCons(head, append(rest, s1))
    }
  }

  def take[T](s: Stream[T], count: Int): Stream[T] = Lazy {
    count match {
      case 0 => SNil
      case n => s match {
        case Lazy(SNil) => SNil
        case Lazy(SCons(head, rest)) => SCons(head, take(rest, n - 1))
      }
    }
  }

  def drop[T](s: Stream[T], count: Int): Stream[T] = Lazy {
    count match {
      case 0 => s.force
      case n => s match {
        case Lazy(SNil) => SNil
        case Lazy(SCons(_, rest)) => drop(rest, n - 1).force
      }
    }
  }

  def toList[T](s: Stream[T]): List[T] = s match {
    case Lazy(SNil) => Nil
    case Lazy(SCons(head, rest)) => head :: toList(rest)
  }
}

@main
def main: Unit = {
  import Streams._

  val s0: Stream[Int] = SCons(10, SCons(9, SNil))
  val s1: Stream[Int] = SCons(5, SCons(4, SNil))
  val s2: Stream[Int] = SCons(10, SCons(9, SCons(5, SCons(4, SNil))))

  assert(toList(s2) == toList(append(s0, s1)))
}