course-2002-02.scala

JAVA 语言的函数式编程扩展

//############################################################################
// Programmation IV - 2002 - Week 02
//############################################################################
// $Id: Course-2002-02.scala 11911 2007-06-05 15:57:59Z odersky $

object M0 {
  def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
  def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)

  Console.println(gcd(14,21))
  Console.println(factorial(5))
  Console.println
}

//############################################################################

object M1 {
  def cube(x: Int): Double = x * x * x

  def sumInts(a: Int, b: Int): Double = if (a > b) 0
    else a + sumInts(a + 1, b);

  def sumCubes(a: Int, b: Int): Double = if (a > b) 0
    else cube(a) + sumCubes(a + 1, b);

  def sumReciprocals(a: Int, b: Int): Double = if (a > b) 0
    else 1.0/a + sumReciprocals(a + 1, b);

  def sumPi(n: Int): Double = {
    def element(x: Int): Double = 4.0/(4*x+1) - 4.0/(4*x-1);
    def sumElements(a: Int, b: Int): Double =
      if (a > b) 0
      else element(a) + sumElements(a + 1, b);
    4 + sumElements(1,n)
  }

  Console.println(sumInts(1,4))
  Console.println(sumCubes(1,4))
  Console.println(sumReciprocals(1,4))
  Console.println(sumCubes(1, 10) + sumReciprocals(10, 20))
  Console.println("pi = " + sumPi(20))
  Console.println
}

//############################################################################

object M2 {
  def id(x: Int): Double = x;
  def cube(x: Int): Double = x * x * x;
  def reciprocal(x: Int): Double = 1.0/x;

  def sum(f: Int => Double, a: Int, b: Int): Double =
    if (a > b) 0
    else f(a) + sum(f, a + 1, b);

  def sumInts(a: Int, b: Int): Double = sum(id, a, b);
  def sumCubes(a: Int, b: Int): Double = sum(cube, a, b);
  def sumReciprocals(a: Int, b: Int): Double = sum(reciprocal, a, b);
  def sumPi(n: Int): Double = {
    def element(x: Int): Double = 4.0/(4*x+1) - 4.0/(4*x-1);
    4 + sum(element, 1, n)
  }

  Console.println(sumInts(1,4))
  Console.println(sumCubes(1,4))
  Console.println(sumReciprocals(1,4))
  Console.println(sumCubes(1, 10) + sumReciprocals(10, 20))
  Console.println("pi = " + sumPi(20))
  Console.println
}

//############################################################################

object M3 {
  def sum(f: Int => Double, a: Int, b: Int): Double =
    if (a > b) 0
    else f(a) + sum(f, a + 1, b);

  def sumInts(a: Int, b: Int): Double = sum((xXXXXX => xXXXXX), a, b);
  def sumCubes(a: Int, b: Int): Double = sum((x => x * x * x), a, b);
  def sumReciprocals(a: Int, b: Int): Double = sum((x => 1.0/x), a, b);
  def sumPi(n: Int): Double = 4 + sum((x => 4.0/(4*x+1) - 4.0/(4*x-1)), 1, n);

  Console.println(sumInts(1,4))
  Console.println(sumCubes(1,4))
  Console.println(sumReciprocals(1,4))
  Console.println(sumCubes(1, 10) + sumReciprocals(10, 20))
  Console.println("pi = " + sumPi(20))
  Console.println
}

//############################################################################

object M4 {
  def sum(f: Int => Double): (Int, Int) => Double = {
    def sumF(a: Int, b: Int): Double =
      if (a > b) 0
      else f(a) + sumF(a + 1, b);
    sumF
  }

  def sumInts = sum(x => x)
  def sumCubes = sum(x => x * x * x)
  def sumReciprocals = sum(1.0/_)  
  def sumPi = { n: Int => 4 + sum(x => 4.0/(4*x+1) - 4.0/(4*x-1))(1, n) }

  Console.println(sumInts(1,4))
  Console.println(sumCubes(1,4))
  Console.println(sumReciprocals(1,4))
  Console.println(sumCubes(1, 10) + sumReciprocals(10, 20))
  Console.println("pi = " + sumPi(20))
  Console.println
}

//############################################################################

object M5 {
  def sum(f: Int => Double): (Int, Int) => Double = { (a, b) =>
    if (a > b) 0
    else f(a) + sum(f)(a + 1, b)
  }

  def sumInts = sum(x => x)
  def sumCubes = sum(x => x * x * x)
  def sumReciprocals = sum(x => 1.0/x)
  def sumPi = { n: Int => 4 + sum(x => 4.0/(4*x+1) - 4.0/(4*x-1))(1, n) }

  Console.println(sumInts(1,4))
  Console.println(sumCubes(1,4))
  Console.println(sumReciprocals(1,4))
  Console.println(sumCubes(1, 10) + sumReciprocals(10, 20))
  Console.println("pi = " + sumPi(20))
  Console.println
}

//############################################################################

object M6 {
  def sum(f: Int => Double)(a: Int, b: Int): Double =
    if (a > b) 0
    else f(a) + sum(f)(a + 1, b);

  def sumInts = sum(x => x)_
  def sumCubes = sum(x => x * x * x)_
  def sumReciprocals = sum(x => 1.0/x)_
  def sumPi = { n: Int => 4 + sum(x => 4.0/(4*x+1) - 4.0/(4*x-1))(1, n) }

  Console.println(sumInts(1,4))
  Console.println(sumCubes(1,4))
  Console.println(sumReciprocals(1,4))
  Console.println(sumCubes(1, 10) + sumReciprocals(10, 20))
  Console.println("pi = " + sumPi(20))
  Console.println
}

//############################################################################

object M7 {
  def sum(f: Int => Double)(a: Int, b: Int): Double = {
    def iter(a: Int, result: Double): Double =
      if (a > b) result
      else iter(a + 1, f(a) + result);
    iter(a, 0)
  }

  def sumInts = sum(x => x)_
  def sumCubes = sum(x => x * x * x)_
  def sumReciprocals = sum(x => 1.0/x)_
  def sumPi = { n: Int => 4 + sum(x => 4.0/(4*x+1) - 4.0/(4*x-1))(1, n) }

  Console.println(sumInts(1,4))
  Console.println(sumCubes(1,4))
  Console.println(sumReciprocals(1,4))
  Console.println(sumCubes(1, 10) + sumReciprocals(10, 20))
  Console.println("pi = " + sumPi(20))
  Console.println
}

//############################################################################

object M8 {
  def product(f: Int => Double)(a: Int, step: Int, b: Int): Double =
    if (a > b) 1
    else f(a) * product(f)(a + step, step, b);

  def productPi = { n: Int => product(x=>4.0*x*x/(2*x-1)/(2*x-1))(1,1,n)/n }

  val pi = 2 * product(x => x * x)(2, 2, 40) / product(x => x * x)(1, 2,40)/40;

  Console.println("pi = " + productPi(20))
  Console.println("pi = " + pi)
  Console.println
}

//############################################################################

object M9 {
  def accumulate[t](combiner: (t, t) => t, nullValue: t, f: Int => t, 
                    next: Int => Int)(a: Int, b: Int): t =
    if (a > b) nullValue
    else combiner(f(a), accumulate(combiner, nullValue, f, next)(next(a), b))

  def inc(x: Int) = x + 1

  def sum(f: Int => Double): (Int, Int) => Double =
    accumulate((x: Double, y: Double) => x + y, 0d, f, inc)

  def product(f: Int => Double): (Int, Int) => Double =
    accumulate((x: Double, y: Double) => x * y, 1d, f, inc)

  def sumInts = sum(x => x)
  def sumCubes = sum(x => x * x * x)
  def sumReciprocals = sum(x => 1.0 / x)
  def sumPi = { n: Int => 4 + sum(x => 4.0/(4*x+1) - 4.0/(4*x-1))(1, n) }

  def productPi = { n: Int => product(x=>4.0*x*x/(2*x-1)/(2*x-1))(1,n)/n }

  val pi = 2*product(x => 2*x*2*x)(1,20)/product(x =>(2*x-1)*(2*x-1))(1,20)/40

  Console.println(sumInts(1, 4))
  Console.println(sumCubes(1, 4))
  Console.println(sumReciprocals(1, 4))
  Console.println(sumCubes(1, 10) + sumReciprocals(10, 20))
  Console.println("pi = " + sumPi(20))
  Console.println("pi = " + productPi(20))
  Console.println("pi = " + pi)
  Console.println
}

//############################################################################

object MA {
  val tolerance = 0.0001
  def abs(x: Double) = if (x < 0) -x else x
  def isCloseEnough(x: Double, y: Double) = abs((x - y) / x) < tolerance
  def fixedPoint(f: Double => Double)(firstGuess: Double) = {
    def iterate(guess: Double): Double = {
      val next = f(guess);
      Console.println(next);
      if (isCloseEnough(guess, next)) next
      else iterate(next)
    }
    iterate(firstGuess)
  }
  def sqrt(x: Double) = fixedPoint(y => (y + x / y) / 2)(1.0)

  Console.println("sqrt(2) = " + sqrt(2))
  Console.println
}

//############################################################################

object MB {
  val tolerance = 0.0001;
  def abs(x: Double) = if (x < 0) -x else x;
  def isCloseEnough(x: Double, y: Double) = abs((x - y) / x) < tolerance;
  def fixedPoint(f: Double => Double)(firstGuess: Double) = {
    def iterate(guess: Double): Double = {
      val next = f(guess);
      Console.println(next);
      if (isCloseEnough(guess, next)) next
      else iterate(next)
    }
    iterate(firstGuess)
  }
  def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2;
  def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0);

  Console.println("sqrt(2) = " + sqrt(2))
  Console.println
}

//############################################################################

object MC {
  def sum(f: Int => Double)(a: Int, b: Int): Double = {
    def iter(a: Int, result: Double): Double = {