Today we cover some of the more advanced functional programming concepts in Scala.
We did tease you in previous courses on various topics. Now we cover them in depth.

You can find today's contents here.

We'll practice a simple implementation of an infinite sequence.
Define a trait Stream[+A] (although we did explain what the + does, you don't need to worry about it now).

1. For now, define these methods in the trait:

   def head: A
   def tail: Stream[A]
   def isEmpty: Boolean

2. Define a companion object for Stream. Implement two methods in the companion: cons and empty. The object should look something like this:

   object Stream {
     def cons[A](h: A, t: => Stream[A]): Stream[A] = new Stream[A] {
       // your implementation here
       def head = ...
     }
    
     def empty: Stream[Nothing] = new Stream[Nothing] {
       // your implementation here
     }
   }

   Notice how your code now stays inside an anonymous instance - the anonymous instantiation and on-the-spot method overriding works exactly as in Java.
   If you'd like, you can alternatively define two subclasses, much like the Cons-based list you implemented a few labs ago.
   Notice the call-by-name scheme at the cons method. This is fundamentally important. Why?

3. Implement the missing methods in the empty and non-empty streams; they should all be one-liners.
   For the empty stream, any access which doesn't make sense (e.g. head) will throw a NoSuchElementException
4. How would you test that the tail of a non-empty Stream is not evaluated until needed?
5. Let's make the Stream actually useful.
   Make it a monad, that is, define the map, flatMap and filter methods in the trait and implement them in the subclasses.
   First things first - how does the signature of each of these methods look like?
6. What would be the benefit of replacing def tail with a lazy val? If there is a benefit, do it.
7. Enhance the Stream trait and object with some functional primitives.
   Depending on the time you have (either at the lab or at home), implement, at will:
   • take(k) which takes an int and returns a stream of the first k elements
   • drop(k) which returns a stream that starts from the k+1'th element
   • Stream.flatten[A](s: Stream[Stream[A]]) which returns a single stream with all the elements in the nested streams, in order
   • zipWith[B](s: Stream[B], f: (A, B) ⇒ C): Stream[C] which takes another stream and a function, and returns a zipped stream with the application of the function on the corresponding elements, in order; test it
   • toList which converts a finite stream to a list
   • fromList(l: List[A]) which converts a list to a stream
   • fromRange(a, b) which receives two integers and returns a stream of numbers from a to b, in increasing order; this should not belong to the Stream object or trait
   • streamOfPrimes(n) which returns a stream of the first n prime numbers; this should not belong to the Stream object or trait