implement numbers with lambda calculus

numbers.scala

package fpinscala

object Test {
  sealed trait Number


  sealed trait Positive extends Number
  case object Zero extends Positive with Negative
  case class Succ[P <: Positive](prev: P) extends Positive


  sealed trait Negative extends Number
  case class Prev(prev: Negative) extends Negative


  val one = Succ(Zero)
  val two = Succ(one)
  val three = Succ(two)
//  val four = add(two, two)
//  val sixteen = {val x = add(four, four); add(x, x)}

  def decrement(n: Number) =
    n match {
      case Succ(prev) => prev
      case neg: Negative => Prev(neg)

    }
  val minusOne = Prev(Zero)
  val minusTwo = Prev(minusOne)

  decrement(one)
  decrement(two)

  decrement(Zero)

  val nine = Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Zero)))))))))
  val ten = Succ(nine)

  def increment(n: Number) =
    n match {
      case Prev(next) => next
      case pos: Positive => Succ(pos)

    }

  def incrementPos[N <: Positive](n: N) =
      Succ(n)

  trait AddStep[X <: Positive, Y <: Positive, Z <: Positive] {
    def get(x: X, y: Y): Z
  }
  implicit def zas[X <: Positive] = new AddStep[Zero.type, X, X] {
    override def get(a: Zero.type, x: X): X = x
  }
  implicit def sas[P <: Positive, Y <: Positive, Z <: Positive](implicit nextStep: AddStep[P, Succ[Y], Z]) = new AddStep[Succ[P], Y, Z] {
    override def get(x: Succ[P], y: Y): Z = add(x.prev, Succ(y)) // prev is unwrap Succ from x
  }
  def add[X <: Positive,Y <: Positive,Z <: Positive](x: X, y: Y)(implicit step: AddStep[X, Y, Z]): Z =
    step.get(x, y)

//  add(two, two)

  def addNeg(x: Negative, y: Negative): Negative =
    x match {
      case Zero => y
      case Prev(prev) => addNeg(prev, Prev(y))
    }

  addNeg(minusOne, minusOne)

  def addNum(x: Number, y: Number): Number =
    x match {
      case Zero => y
      case Succ(prev) => addNum(prev, increment(y))
      case Prev(prev) => addNum(prev, decrement(y))
    }

  val fourR = addNum(two, two)
  val oneR = addNum(two, minusOne)
  val oneRR = addNum(minusOne, two)
  val miOneR = addNum(minusTwo, one)
  val miFourR = addNum(minusTwo, minusTwo)

  def subtract(x: Number, y: Number): Number =
    (x, y) match {
      case (a, Zero) => a
      case (a, Succ(prevY)) => subtract(decrement(a), prevY)
      case (a, Prev(nextY)) => subtract(increment(a), nextY)
    }

  subtract(one, one)
  subtract(one, Zero)
  subtract(Zero, one)

  def toBase2(x: Positive): List[Positive] = // the List is of Zero or Succ(Zero) really
  {
    def base2Succ(soFar: List[Positive]): List[Positive] =
      soFar match {
        case Nil => Succ(Zero) :: Nil
        case Succ(Zero)/*recurse*/ :: rest => Zero :: base2Succ(rest)
        case digit :: rest => Succ(digit) :: rest
      }
    def f(remaining: Positive, soFar: List[Positive]): List[Positive] =
      remaining match {
        case Zero => soFar
        case Succ(prev) => f(prev, base2Succ(soFar))
      }
    f(x, List(Zero))
  }

  toBase2(Zero)
  toBase2(one)
  toBase2(two)
  toBase2(nine)

  def baseNSucc[X <: Positive](soFar: List[Positive], base: Succ[X]): List[Positive] = {
    val zeroInOurRepresentation = base.prev
    zeroInOurRepresentation match {
      case Succ(oneInOurRepresentation) =>
        soFar match {
          case Nil => // this digit doesn't exist i.e. zero
            oneInOurRepresentation :: Nil
          case Zero :: rest => //zero is the max in our representation
            // this digit is at max (eg 9) and will be zero
            // then increment the higher digit
            zeroInOurRepresentation :: baseNSucc(rest, base)
          case Succ(digit) :: rest =>
            digit :: rest
        }
    }
  }

  val oneB = baseNSucc(Nil, two)
  val twoB = baseNSucc(oneB, two)
  val threeB = baseNSucc(twoB, two)
  val fourB = baseNSucc(threeB, two)

  def toBaseN[X <: Positive](x: Positive, base: Succ[X]/*should be SuccSucc*/): List[Positive] =
  {
    def f(leftToAdd: Positive, soFar: List[Positive]): List[Positive] =
      leftToAdd match {
        case Zero => soFar
        case Succ(prev) => f(prev, baseNSucc(soFar, base))
      }
    f(x, List())
  }

  toBaseN(Zero, two)
  toBaseN(one, two)
  toBaseN(two, two)
  toBaseN(nine, two)

  def print(c: Positive) = {
    val digits = "0123456789".toList
    def f(p: Positive, ds: List[Char]): Option[Char] =
      (p, ds) match {
        case (Zero, d :: _) => Some(d)
        case (Succ(prev), _ :: rest) => f(prev, rest)
        case (_, Nil) => None
      }
    f(c, digits)
  }
  print(Zero)
  print(one)
  print(two)
  print(nine)
  print(ten)

  def printBaseN[X <: Positive](x: Positive, base: Succ[X]) =
    toBaseN(x, base).map(
      subtract(base.prev, _)
    ).map{
      case p: Positive => print(p)
    }.reverse
      .map{
        case None => 'x'
        case Some(c) => c
      }.mkString("")

  val base = ten
  printBaseN(Zero, base)
  printBaseN(one, base)
  printBaseN(two, base)
  printBaseN(nine, base)
  printBaseN(ten, base)

//  printBaseN(add(ten, ten), base)

}
object worksheet {
  import _root_.fpinscala.Test._

val zero = add(Zero, Zero)
val test = add(one, Zero)(
  sas[Zero.type, Zero.type, Succ[Zero.type]](
    zas[Succ[Zero.type]]
  )
)
val oneRe = add(two, Zero)(
  sas[Succ[Zero.type], Zero.type, Succ[Succ[Zero.type]]](
    sas[Zero.type, Succ[Zero.type], Succ[Succ[Zero.type]]](
      zas[Succ[Succ[Zero.type]]]
    )
  )
)

val oneRe2 = add(two, Zero)

val another = add(two, two)


trait SubtractStep[X <: Positive, Y <: Positive, Z <: Positive] {
  def get(x: X, y: Y): Z
}
implicit def zss[X <: Positive] = new SubtractStep[X, Zero.type, X] {
  override def get(x: X, a: Zero.type): X = x
}
implicit def sss[P <: Positive, Y <: Positive, Z <: Positive](implicit nextStep: SubtractStep[P, Y, Z]) =
  new SubtractStep[Succ[P], Succ[Y], Z] {
    override def get(x: Succ[P], y: Succ[Y]): Z = nextStep.get(x.prev, y.prev)
  }
def subtract[X <: Positive,Y <: Positive,Z <: Positive](x: X, y: Y)(implicit step: SubtractStep[X, Y, Z]): Z =
  step.get(x, y)

subtract(two, two)


ten

// multiply
// print negative
// type system for all numbers
// parse human readable

print(Zero)
print(one)
print(two)
print(nine)
print(ten)


val base = ten
printBaseN(Zero, base)
printBaseN(one, base)
printBaseN(two, base)
printBaseN(nine, base)
printBaseN(ten, base)
}