A fork for a friend's Gist to demonstrate some things

church-numerals.scala

/*
  SP: currying this gives the type: (T => T) => T => T
  That looks an awful lot like Haskell's application ($) operator. :)
  There is a higher order abstraction here, sniff it out.
*/
type ChurchNumeral[T] = (T => T, T) => T

def cn0[T](f:T=>T, x:T):T = x
def cn1[T](f:T=>T, x:T):T = f(x)
def cn2[T](f:T=>T, x:T):T = f(f(x))
def cn3[T](f:T=>T, x:T):T = f(f(f(x)))

/*
  SP: I would argue it would be clearer to define a type and then definition would be more comprehensible.
  Scala infers: ChurchNumeral[T] => ((T => T, T) => T)
  
  Wouldn't it be nicer to show: ChurchNumeral[T] => ChurchNumeral[T] ? :)
  
  That would be more expressive in code and convey more of your intent and meaning IMO.
  
  See my definition of successor2[T]. Only a couple more extra characters of code but to me communicates much more,
  and much more clearly. 
*/
def successor[T] = (n:ChurchNumeral[T]) => (f:T=>T, x:T) => f(n(f, x))
def successor2[T]: ChurchNumeral[T] => ChurchNumeral[T] = n => (f, x) => f(n(f, x))

// SP: Similarly with plus2[T] below
def plus[T] = (n:ChurchNumeral[T], m:ChurchNumeral[T]) => (f:T=>T, x:T) => m(f, n(f, x))
def plus2[T]: (ChurchNumeral[T], ChurchNumeral[T]) => ChurchNumeral[T] = 
  (m, n) => (f, x) => m(f, n(f, x))

// SP: why are we hardcoding the increment function?
def convertToInt[T](churchNumeral: ChurchNumeral[Int]):Int = {
  val increment = (i:Int) => i + 1
  churchNumeral(increment, 0)
}

// SP: Fixed it here to how I think it should be. I removed the unused type parameter for this definition.
// SP: Bad Susan, I shouldn't have hardcoded the zero value here. It should be passed in a an argument.
// SP: See convertToInt3 for what it should have been.
def convertToInt2(f: Int => Int, n: ChurchNumeral[Int]): Int = n(f, 0)
def convertToInt3(f: Int => Int, zero: Int, ChurchNumeral[Int]): Int = n(f, zero)

// SP: Added helper, identity
def identity[T](x: T) = x

// SP: Added helper, increment (non generalized because time is short)
def increment(y: Int)(x: Int) = y + x

convertToInt(cn0)
convertToInt(cn1)
convertToInt(cn2)

// SP: This is how I would call my function assuming I want my number system to increment by one
convertToInt2(increment, cn0)
convertToInt2(increment, cn1)
convertToInt2(increment, cn2)

// SP: This is how I would call my function assuming I want my number system to increment by two
convertToInt2(increment(2), cn0)
convertToInt2(increment(2), cn1)
convertToInt2(increment(2), cn2)

convertToInt(successor(cn1))
// SP: Using convertToInt2 (obviously you would dress this up to not be so repetitive in something more special purpose
// since most of the time you will want the `convertToInt2(increment(1), _)` wrapper
convertToInt2(increment(1), successor(cn1))

convertToInt(cn3)
// SP: Similarly
convertToInt2(increment(2), cn3)

//This won't compile:
//val cn3Computed = successor(cn2)
//convertToInt(cn3Computed)
//This will:
convertToInt(successor(cn2))
//This won't compile either:
//val cn6 = plus(cn3, cn2)
//convertToInt(cn6)
//This will:
convertToInt(plus(cn3, cn2))

/*
  SP: Let's see how we can compute the intermediate result before converting
*/
val cn3Computed: ChurchNumeral[Int] = successor(cn2)
convertToInt2(increment(1), cn3Computed)

// SP: Similarly
val cn5: ChurchNumeral[Int] = plus(cn3, cn2)
convertToInt(cn5)

// SP: It's just that vals and vars can't have type parameters. They must be concrete types. 
// I think that is the primary thing that is missing.
val cn6: ChurchNumeral[Int] = plus(cn3, cn3)
convertToInt(cn6)

//In both cases, compiler thinks cn6 is (Nothing => Nothing, Nothing) => Nothing
//So it doesn't conform to the expected type ChurchNumeral[Int]?

// SP: The `def` below will compile. The type that you notice without specifying
// types is a result of the type inference algorithm in Scala: (Nothing => Nothing, Nothing) => Nothing
def cn3Computed[T]: ChurchNumeral[T] = successor(cn2)
convertToInt2(increment(1), cn3Computed)