I set myself the following additional goal (devised by me):

I chose to learn Scala for this course because of its expressive type system and functional features. As such, I decided to write a program which uses Scala's type system to consistently type the Y Combinator and then uses the result to implement a function that calculates Pascal's triangle without recursion but using several of Scala's functional features. I have placed the type-level logic in a comment.

// Here begins file main.scala

object Combinator {
  /*
  The overall type of the Y Combinator below is ((A -> B) -> (A -> B)) -> (A -> B). The challenge is to consistently type its subexpressions.

  λf.(λx.f(x x))(λx.f(x x))

  By looking at the definition, we can deduce the following about the types of some of the elements:

  f: (A -> B) -> (A -> B)

  x: X
  &&
  x: X -> (A -> B)

  In some type systems, we can define a type Rec s.t. Rec == Rec -> (A -> B), a recursive type. In Scala, we can approximate this using the following:

  case class Rec(r: Rec => (A => B)) {
    def apply(x: Rec) = r(x)
  }

  The constructor converts Rec -> (A -> B) to just Rec but said Rec can still act like Rec -> (A -> B) via the apply method.

  The resulting types of the subexpressions are then as follows:

  x: Rec
  x x: A -> B
  f(x x): A -> B
  (λx.f(x x)): Rec -> (A -> B)
  Rec((λx.f(x x))): Rec
  (λx.f(x x))Rec((λx.f(x x))): A -> B
  λf.(λx.f(x x))(λx.f(x x)): ((A -> B) -> (A -> B)) -> (A -> B)

  This gives the result we wanted.
  */

  def Y[A,B](f: (A => B) => (A => B)) = {
    case class Rec(r: Rec => (A => B)) {
      def apply(x: Rec) = r(x)
    }

    ((x: Rec) => f(x(x))(_))(Rec(x => f(x(x))(_)))
  }
}

object Main extends App {

  def pascal = Combinator.Y {
    f: (Int => Array[Int]) =>
      n: Int =>
        if(n == 1) Array(1)
        else {
          val prev = f(n-1)
          1 +: (prev zip prev.drop(1)).map{ case(a,b) => a + b } :+ 1
        }
  }

  val depth = 15
  val spacing = 6

  for(y <- 1 to depth) {
    print(" "*(spacing*(depth - y)/2))
    for(x <- pascal(y)) print(x + " "*(spacing - x.toString().length))
    println()
  }
}