//############################################################################// Programmation IV - 2002 - Week 05//############################################################################// $Id: Course-2002-05.scala 7937 2006-06-21 10:36:06Z odersky $object M0 {  def partition[a](xs: List[a], pred: a => boolean): Pair[List[a], List[a]] = {    if (xs.isEmpty)      Pair(List(),List())    else {      val tailPartition = partition(xs.tail, pred);      if (pred(xs.head))        Pair(xs.head :: tailPartition._1, tailPartition._2)      else        Pair(tailPartition._1, xs.head :: tailPartition._2)    }  }  def quicksort[a] (less : (a,a) => boolean) (xs : List[a]) : List[a] = {    if (xs.isEmpty)      xs    else {      val pivot = xs.head;      val sub = partition(xs.tail, { elem : a => less(elem, pivot) });      quicksort(less)(sub._1) ::: List(pivot) ::: quicksort(less)(sub._2)    }  }  def test = {    Console.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 0)));    Console.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 5)));    Console.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 9)));    Console.println;    Console.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 0)));    Console.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 5)));    Console.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 9)));    Console.println;    Console.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 0)));    Console.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 5)));    Console.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 9)));    Console.println;    Console.println(quicksort[int]((x,y) => x < y)(List(7,2,1,5,4,3,8,6)));    Console.println;  }}//############################################################################object M1 {  def partition[a](xs: List[a], pred: a => boolean): Pair[List[a], List[a]] = {    xs.foldRight[Pair[List[a], List[a]]](Pair(List(), List())) {      (x, p) => if (pred (x)) Pair(x :: p._1, p._2) else Pair(p._1, x :: p._2)    }  }  def quicksort[a] (less : (a,a) => boolean) (xs : List[a]) : List[a] = {    if (xs.isEmpty)      xs    else {      val pivot = xs.head;      val sub = partition(xs.tail, (elem : a) => less(elem, pivot));      quicksort(less)(sub._1) ::: List(pivot) ::: quicksort(less)(sub._2)    }  }  def test = {    Console.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 0)));    Console.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 5)));    Console.println(partition[int](List(1,2,3,4,5,6,7,8), (x => x < 9)));    Console.println;    Console.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 0)));    Console.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 5)));    Console.println(partition[int](List(8,7,6,5,4,3,2,1), (x => x < 9)));    Console.println;    Console.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 0)));    Console.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 5)));    Console.println(partition[int](List(7,2,1,5,4,3,8,6), (x => x < 9)));    Console.println;    Console.println(quicksort[int]((x,y) => x < y)(List(7,2,1,5,4,3,8,6)));    Console.println;  }}//############################################################################object M2 {  def powerset[a] (s : List[a]) : List[List[a]] = {    if (s.isEmpty)      List(List())    else {      val x = s.head;      val withoutX = powerset(s.tail);      withoutX ::: withoutX.map { s1 : List[a] => x::s1 }    }  }  def test = {    Console.println(powerset(List()));    Console.println(powerset(List(1)));    Console.println(powerset(List(1,2)));    Console.println(powerset(List(1,2,3)));    Console.println(powerset(List(1,2,3,4)));    Console.println;  }}//############################################################################object M3 {  def abs(x: int) = if (x < 0) 0 - x else x;  def range(lo: Int, hi: Int): List[Int] =    if (lo > hi) List()    else lo :: range(lo + 1, hi);  type Placement = List[Pair[int,int]];  def queens(n: int): List[Placement] = {    def placeQueens(row: int): List[Placement] = {      if (row == 0)        List(List())      else {        def isSafe(column: int, placement: Placement): boolean =          placement forall {            pos => (pos._2 != column &&               abs(pos._2 - column) != row - pos._1)          }        def adjoinRow(placement: Placement): List[Placement] =          range(1, n)            .filter (column => isSafe(column, placement))            .map (column => Pair(row, column) :: placement);        placeQueens(row - 1) flatMap adjoinRow      }    }    placeQueens(n)  }  def test = {    Console.println("queens(1) = " + queens(1));    Console.println("queens(2) = " + queens(2));    Console.println("queens(3) = " + queens(3));    Console.println("queens(4) = " + queens(4));    Console.println;  }}//############################################################################object M4 {  def abs(x: int) = if (x < 0) 0 - x else x;  def range(lo: Int, hi: Int): List[Int] =    if (lo > hi) List()    else lo :: range(lo + 1, hi);  type Placement = List[Int];  def queens(n: Int): List[Placement] = {    val columns = range(1, n);    def placeQueens(row: Int): List[Placement] = {      if (row == 0)        List(List())      else {        def isSafe(col: Int, p: Placement, delta: Int): Boolean =          (p.isEmpty ||           (col != p.head &&            abs(col - p.head) != delta &&            isSafe(col, p.tail, delta + 1)));        for (          val placement <- placeQueens(row - 1);          val col <- columns;          isSafe(col, placement, 1)        ) yield {          col :: placement        }      }    }    placeQueens(n);  }  def test = {    Console.println("queens(1) = " + queens(1));    Console.println("queens(2) = " + queens(2));    Console.println("queens(3) = " + queens(3));    Console.println("queens(4) = " + queens(4));    Console.println;  }}//############################################################################object Test {  def main(args: Array[String]): unit = {    M0.test;    M1.test;    M2.test;    M3.test;    M4.test;    ()  }}//############################################################################