Every single freshman CS question in ˜80 lines of Scala

recstream.scala

import Stream._

object Curryfication {
  def curry [A,B,C](f:Pair[A,B] ⇒ C) = (x:A) ⇒ (y:B) ⇒ f (x,y)
  def uncurry [A,B,C](f: A ⇒ B ⇒ C) = (x:Pair[A,B]) ⇒ f (x._1) (x._2)
}

trait Curried[S,R] {
  type Fun
  def curry : (S ⇒ R) ⇒ Fun
}

class CurriedDefault {
  implicit def ZeroC[S,R] = new Curried[S,R]{
    type Fun = S ⇒ R
    def curry = f ⇒ f
  }
}

object Curried extends CurriedDefault{
  def apply[S,R] (f:S ⇒ R) (implicit c:Curried[S,R]) : c.Fun =
    c.curry(f)

  implicit def SuccC[T,S,R] (implicit c:Curried[S,R]) =
    new Curried[Pair[T,S],R] {
      type Fun = T ⇒ c.Fun
      def curry = f ⇒ x ⇒ c.curry(y ⇒ f(x,y))
    }
}

trait Uncurried [S] {
  type Tuple
  type Return
  def uncurry : S ⇒ Tuple ⇒ Return
}


class UncurriedDefault {
  implicit def ZeroUC[S] = new Uncurried[S ⇒ S]{
    type Tuple = S
    type Return = S
    def uncurry = f ⇒ f
  }
}

object Uncurried extends UncurriedDefault{
  def apply[S] (f:S) (implicit uc:Uncurried[S]) : uc.Tuple ⇒ uc.Return =
    uc.uncurry(f)

  implicit def SuccUC[S,R] (implicit uc:Uncurried[R]) =
    new Uncurried[S ⇒ R]{
      type Tuple = Pair[S,uc.Tuple]
      type Return = uc.Return
      def uncurry = f ⇒ x ⇒ uc.uncurry(f (x._1)) (x._2)
    }
}

trait RecStream [S,Base] {
  def prod : (S ⇒ Base) ⇒ S ⇒ Pair[Base, S]
  def rstream : (S ⇒ Base) ⇒ S ⇒ Stream[Base]
}

class RecStreamDefault {
  implicit def ZeroRS[S] = new RecStream[S,S] {
    def prod = xs ⇒ ss ⇒ (ss, xs (ss))
    def rstream = xs ⇒ ss ⇒ ss #:: rstream (xs) (xs(ss))
  }

}

object RecStream extends RecStreamDefault {
  def apply[S,B](f:S ⇒ B) (implicit rs:RecStream[S,B]): S ⇒ Stream[B] =
    rs.rstream(f)

  implicit def SuccRS[R,B] (implicit rs:RecStream[R,B]) =
    new RecStream[Pair[B,R],B] {
      def prod = f ⇒ a ⇒ (a._1, rs.prod (y ⇒ f (a._1,y)) (a._2))
      def rstream = f ⇒ a ⇒
      a._1 #:: rstream (f) (rs.prod (y ⇒ f (a._1,y)) (a._2))
    }

}

object Test{
  def increaser : Int ⇒ Stream[Int] =
    RecStream((x:Int) ⇒ x + 1)

  def fibonacci : Pair[Int,Int] ⇒ Stream [Int] =
    RecStream(x ⇒ x._1 + x._2)

  def sumthree (x:Int)(y:Int)(z:Int) = x+y+z

  // def sumthreestream = RecStream(sumthree)

  def uncst = Uncurried(sumthree _)
  def sumthreestream = RecStream(uncst)

  def curriedsumthreestream = Curried(sumthreestream)

  def main(args:Array[String]) = {
    fibonacci(0,1).take(10).print
    print ("\n")
    increaser(0).take(10).print
    print ("\n")
    increaser(1).take(10).print
    print ("\n")
    sumthreestream(0,(0,1)).take(10).print
    print("\n")
    curriedsumthreestream(0)(0)(1).take(10).print
    print("\n")
  }
}