Combining Streams in Scala

Given an interface Stream:

trait Stream[A] {
  def head: A
  def tail: Stream[A]
}

Constant streams

Write the functions zeroes, ones, and twos, which return streams of values 0, 1, and 2:

def zeroes: Stream[Int] = ???
// 0 -> 0 -> 0 -> 0 -> ...

def ones: Stream[Int] = ???
// 1 -> 1 -> 1 -> 1 -> ...

def twos: Stream[Int] = ???
// 2 -> 2 -> 2 -> 2 -> ...

Natural numbers streams

Write the functions evens and odds, which return streams of the even natural numbers (0, 2, 4, ...) and the odd natural numbers (1, 3, 5, ...):

def evens: Stream[Int] = ???
// 0 -> 2 -> 4 -> 6 -> ...

def odds: Stream[Int] = ???
// 1 -> 3 -> 5 -> 7 -> ...

Combined streams

Write the function combine, which interleaves its argument streams in constant time:

def combine[A](ss: Stream[A] *): Stream[A] = ???
// combine(evens, odds) = 0 -> 1 -> 2 -> 3 -> ...

Solution

Here is one possible solution.

Constants streams

object ConstantsStreams {

  class ConstantsStream(value: Int) extends Stream[Int] {
    def head: Int = value
    def tail: Stream[Int] = this
  }

  def zeroes: Stream[Int] =
    new ConstantsStream(0)

  def ones: Stream[Int] =
    new ConstantsStream(1)

  def twos: Stream[Int] =
    new ConstantsStream(2)
}

Natural numbers streams

object NatsStreams {

  class ByTwosStream(value: Int) extends Stream[Int] {
    def head: Int = value
    def tail: Stream[Int] = new ByTwosStream(value + 2)
  }

  def evens: Stream[Int] =
    new ByTwosStream(0)

  def odds: Stream[Int] =
    new ByTwosStream(1)
}

Combined streams

object CombinedStreams {

  class InterleavedStream[A](ss: Stream[A] *) extends Stream[A] {
    def head: A = ss.head.head
    def tail: Stream[A] =
      new InterleavedStream((ss.tail :+ ss.head.tail):_*)
  }

  def combine[A](ss: Stream[A] *): Stream[A] =
    new InterleavedStream[A](ss:_*)
}

Demo

object Streams extends App {

  def peek[A](s: Stream[A]): String =
    s"${s.head} -> ${s.tail.head} -> ${s.tail.tail.head} -> ${s.tail.tail.tail.head} -> ..."

  println()

  print(
    s"""|Constants streams:
        |  zeroes = ${peek(ConstantsStreams.zeroes)}
        |    ones = ${peek(ConstantsStreams.ones)}
        |    twos = ${peek(ConstantsStreams.twos)}
        |""".stripMargin
  )

  println()

  print(
    s"""|Natural numbers streams:
        |  evens = ${peek(NatsStreams.evens)}
        |   odds = ${peek(NatsStreams.odds)}
        |""".stripMargin
  )

  println()

  print(
    s"""|Combined streams:
        |  combine(evens, odds) = ${peek(CombinedStreams.combine(NatsStreams.evens, NatsStreams.odds))}
        |""".stripMargin
  )
}

This file is literate Scala, and can be run using Codedown:

$ curl https://earldouglas.com/posts/exercises/scala-streams.md |
  codedown scala | xargs -0 scala -nc -e

Constants streams:
  zeroes = 0 -> 0 -> 0 -> 0 -> ...
    ones = 1 -> 1 -> 1 -> 1 -> ...
    twos = 2 -> 2 -> 2 -> 2 -> ...

Natural numbers streams:
  evens = 0 -> 2 -> 4 -> 6 -> ...
   odds = 1 -> 3 -> 5 -> 7 -> ...

Combined streams:
  combine(evens, odds) = 0 -> 1 -> 2 -> 3 -> ...