Learning Scala in small bites

#!/bin/bash
scala $0 $@
exit
!#


/*
 Scala has a rich set of value types, and a rich literal syntax to
 support them.
 */


// Integers:
val anInt = 3


// Floating point:
val aDouble = 4.0 


// Charaters:
val aCharacter = 'c' 


// Strings:
val aString = "Google"


// Symbols:
val aSymbol = 'foo


// XML:
val anXMLElement = <a href="http://www.google.com/">{aString}</a>


// Tuples:
val aPair = (aString,aDouble)


// Lists:
val aList = List(1,2,3,4)


// Ranges:
val aRange = 1 to 5


// Maps:
val aMap = Map(3 -> "foo", 4 -> "bar")


// Sets:
val aSet = Set(8,9,10)


// Arrays:
val anArray = Array(1,2,3,5)


// Unit:
val unit = ()


// Null:
val nullValue = null


// Functions:
def incImplicit(x : Int ) = x + 1

val incAnonymous = ((x : Int) => x + 1)

#!/bin/bash
scala $0 $@
exit
!#

/*
 There are many ways to create and use function-like values
 in Scala.
 */


// Implicit function:
def id(x : Int) : Int = x

// Anonymous function:
val anonId = (x : Int) => x


// class with apply method:
class Identity {
  def apply(x : Int) = x
}
val myId = new Identity

// f(x) => f.apply(x)

// object with apply method:
object Id {
  def apply(x : Int) = x
}


// anonymous class with apply method:
val myOtherId = new {
  def apply(x : Int) = x
}

// case blocks also act as functions:
val myCaseID : Int => Int = {
  case x => x
}


println(id(3))
// Prints:
// 3

println(anonId(3))
// Prints:
// 3

println(Id.apply(3))
// Prints:
// 3

println(myId.apply(3))
// Prints:
// 3

println(Id(3))
// Prints:
// 3

println(myId(3))
// Prints:
// 3

println(myOtherId(3))
// Prints:
// 3

println(myCaseID(3))
// Prints:
// 3


// Multi-argument functions:
def h(x : Int, y : Int) : Int = x + y

// A Curried multi-argument function:
def hC (x : Int) (y : Int) : Int = x + y

// Wrong: hC 3 4
// Right: hC (3) (4)

// Wrong: hC (3)
// Right: hC (3) _

// Wrong: hC _ (4)
// Right: hC (_:Int) (4)

val plus3 = hC (_:Int) (3) 
val plus_3 = hC (3) _

println(plus3(10)) 
// Prints:
// 13


// A procedure:
def proc(a : Int) { // Implicitly : Unit
  println("I'm a procedure.")
}

proc(10)
// Prints:
// I'm a procedure.


// An argument-less function:
def argless : Unit = println("argless got called!")

argless
argless
// Prints:
// argless got called
// argless got called


// Lazy fields are argless functions that cache their result:
class LazyClass {
  lazy val x = { println("Evaluating x") ; 3 }
}

val lc = new LazyClass
println(lc.x)
println(lc.x)
println(lc.x)
// Prints:
// Evaluating x
// 3
// 3
// 3

// Parameters can be evaluated lazily by-name:
def lazyId(x : => Int) : Int = {
  x
  x
  x
  return x ;
}

println(lazyId { println("used!") ; 3 })
// Prints:
// used!
// used!
// used!
// used!
// 3

#!/bin/bash
scala $0 $@
exit
!#

/*
 Classes in Scala are similar to classes in Java, with
 several convenient shorthands.
 */


// Create an empty class A:
class A


// Create a subclass of A, B:
class B extends A


// A class with an immutable field:
class C {
  val field = 3
}


// Classes take parameters:
class D(x : Int) {
  val field = x
}


// Parameters can also be fields:
class E(val field : Int) 


// Parameters can be mutable fields:
class F(var field : Int)
val f = new F(3)
f.field = 20


// Parameters and fields can also be private:
class G(private val initialX : Int) {
  private var myPrivateX = initialX
}


// Fields may be artificial:
class H {
  private var realX = 0 ;

  def x = realX

  // called for "this.x = <value>":
  def x_=(newX : Int) {
    this.realX = newX
  }
}

val h = new H

h.x = 3
println(h.x) // prints 3


// Fields can be lazy:
class I {
  lazy val x = { println("called x") ; 3 }
}

val i = new I
println(i.x) // prints "called x"; "3"
println(i.x) // prints 3


// Case classes allow pattern matching:
class JK

case class J(x : Int) extends JK 
case class K(s : String) extends JK 

val jk : JK = J(3) // Note the lack of new

jk match {
  case K("foo") => println("foo") 
  case J(0)     => println("0")
  case J(n)     => println(n+1)
}

// Prints:
// 4


// Classes can extend multiple traits:
trait L {
  def f() { println("foo") }
}
trait M {
  def g() { println("bar") }
}

class N extends L with M

val n = new N
n.f()
n.g()
// Prints:
// foo
// bar


// Companion objects take the place of static fields:
class O(val value : String) 

object O {
  def from(value : String) : O = new O(value)
}


// Objects can have a type too:
class P {
  def f() {
    println("foo") 
  }
}

object myObject extends P   
myObject.f()
// Prints:
// foo


// Case objects work in pattern matching:
class Bool

case object TRUE extends Bool
case object FALSE extends Bool

val b : Bool = TRUE

b match {
  case FALSE => println("It was false!")
  case TRUE  => println("It was true!")
}
// Prints:
// It was true!

#!/bin/bash
scala $0 $@
exit
!#

/*
 You can learn a lot just by seeing how many ways there are to write
 factorial in Scala.
 */



// Iteratively:
def fact0(n : Int) : Int = {
  var i = n ;
  var a = 1 ;
  while (i > 0) {
    a = a*i ;
    i -= 1 ;
  }
  return a ;
}

println("fact0(5) = " + fact0(5)) ;
// Prints:
// fact0(5) = 120

println("fact0(33) = " + fact0(33)) ;
// Prints:
// fact0(33) = -2147483648

println("fact0(34) = " + fact0(34)) ;
// Prints:
// fact0(34) = 0 


// Using BigInt:
def fact1(n : BigInt) : BigInt = {
  var i = n ;
  var a : BigInt = 1 ;
  while (i > 0) {
    a = a * i ;
    i -= 1 ;
  }
  return a ;
}

println("fact1(34) = " + fact1(34)) ;
// Prints:
// fact1(34) = 295232799039604140847618609643520000000 


// Recursively:
def fact2(n : Int) : Int = {
  if (n <= 0) {
    return 1 ;
  }
  else {
    return n * fact2(n - 1) ;
  }
}

// Tail-recursively:
def fact2tail(i: BigInt): BigInt = {
  def f(i : BigInt, accumulator : BigInt) : BigInt = {
    if (i == 0) {
       return accumulator ;
    } else {
       return f(i - 1, i * accumulator) ;
    }
  }
  return f(i,1) ;
}

println("fact2tail(34) = " + fact2tail(34)) ;
// Prints:
// fact2tail(34) = 295232799039604140847618609643520000000 


// Without returns:
def fact3(n : Int) : Int = {
  if (n <= 0) {
    1
  }
  else {
    n * fact3(n - 1) 
  }
}


// Without blocks:
def fact4(n : Int) : Int = 
  if (n <= 0) 
    1
  else 
    n * fact4(n - 1) 


// Using pattern-matching:
def fact5(n : Int) : Int = n match {
  case 0 => 1 
  case n => n * fact5(n - 1)
}


// Using fold:
def fact6(n : Int) : Int =
 (1 to n).foldRight (1) ((a : Int, b : Int) => a * b)


// With an inferred return type:
def fact7(n : Int) =
 (1 to n).foldRight (1) ((a : Int, b : Int) => a * b)


// With the anonymous function type inferred.
def fact8(n : Int) =
 (1 to n).foldRight (1) ((a,b) => a * b)


// With a parameterless anonymous function:
def fact9(n : Int) =
 (1 to n).foldRight (1) (_ * _)


// With reduce:
def fact10(n : Int) =
 (1 to n) reduceRight (_ * _)


// With the synonym for foldRight:
def fact11(n : Int) =
 ((1 to n) :\ 1) (_ * _)

#!/bin/bash
scala $0 $@
exit
!#

/*
 There are many ways to print the elements of an array in Scala.
 */

// A traditional while loop:
var i = 0 ;
while (i < args.length) {
    println(args(i)) ;
    i += 1 ;
}


// A traditional for loop:
for (i <- 0 until args.length)
 println(args(i)) 


// An iterator-based for loop:
for (arg <- args) 
 println(arg) 


// A functional approach:
args.foreach((arg : String) => println(arg))


// With the argument type inferred:
args.foreach(arg => println(arg))


// With a parameterless anonymous function:
args.foreach(println(_))


// With a Curried function:
args.foreach(println _)


// With a function as argument:
args.foreach(println)


// With infix method call invocation:
args foreach println

// Duplicate the arguments array.
val myArgs = new Array[String](args.length) ;

// Copy method 1:
for (i <- 0 until args.length) 
  myArgs.update(i,args(i))

// Syntactic sugar:
// e1(e2) = e3
//    ==>
// e1.update(e2,e3)

// Copy method 2:
for (i <- 0 until args.length) 
  myArgs(i) = args(i)

// Copy method 3:
(0 until args.length).foreach(i => myArgs(i) = args(i))

// Copy method 4:
(0 until args.length) foreach (i => myArgs(i) = args(i))


// o.m(a) == o m a
val a = 3
val b = 4
val n = a.+(b)
println(n)
// Prints:
// 7


// Create new array of chars:
val alphabet = Array("a","b","c")

val alphabetChars : Array[String] = Array[String]("a","b","c")


// Create a list:
val numbers = List(42,1701,13)
numbers foreach println
// Prints:
// 42
// 1701
// 13

// Create a new list:
val moreNumbers = 1981 :: numbers

numbers
// Prints:
// 42
// 1701
// 13

moreNumbers foreach println
// Prints:
// 1981
// 42
// 1701
// 13

def myMap[A,B] (f : A => B) (list : List[A]) : List[B] = 
  if (list.isEmpty) 
    { Nil }
  else
    { f(list.head) :: myMap (f) (list.tail) }


(myMap ((n:Int) => n + 1) (moreNumbers)) foreach println
// Prints:
// 1982
// 43
// 1702
// 14    


moreNumbers.map(n => n + 1) foreach println
// Prints:
// 1982
// 43
// 1702
// 14


moreNumbers map (_ + 1) foreach println
// Prints:
// 1982
// 43
// 1702
// 14


class Ship(val x : Int, val y : Int) extends Iterable[(String,Int)] {

  def elements = new Iterator[(String,Int)] {
    private var nextVar = 'x
    
    def next : (String,Int) = nextVar match {
      case 'x => { nextVar = 'y ; ("x",x) }
      case 'y => { nextVar = 'z ; ("y",y) }
    }

    def hasNext : Boolean = nextVar != 'z
  }

}


val Galactica = new Ship(42,1701)

for ((coord,value) <- Galactica) {
  println(coord + ": " + value)
}
// Prints:
// x: 42
// y: 1701

#!/bin/bash
scala $0 $@
exit
!#

/*
 Pattern-matching frequently replaces conditionals in Scala.
 */

10 match {
  case 10 => println("It's 10.")
}
// Prints:
// It's 10.


"foo" match {
  case "foo" => println("It's foo.") 
}
// Prints:
// It's foo.


val x : Any = 3
x match {
  case "foo" => println("It's foo.")
  case 3 => println("It's 3.")
}
// Prints:
// It's 3.


val y : Any = 10 
y match {
  case _ : String => println("It's a string.")
  case _ : Int => println("It's an integer.")
}
// Prints:
// It's an integer.


// Case classes are matchable:
case class Pair(val x : Int, val y : String) 

val p = Pair(42,"foo")

p match {
  case Pair(43,"foo") => println("Not me.")
  case Pair(42,s) => println("It's " + s + ".") 
}
// Prints:
// It's foo.


// unapply allows the creation of pseudo-case-classes from Objects:
object StringCons {

  def apply(c : Char, s : String) = c + s

  def unapply(s : String) : Option[(Char,String)] = s match {
    case "" => None
    case _ => Some((s.charAt(0),s.substring(1)))
  }
}

"foo" match {
  case StringCons('x',rest) => println("Not me.")
  case StringCons('f',rest) => println("The rest is " + rest + ".")
}
// Prints:
// The rest is oo.


// Taking advantage of operator sugar enhances readability:
object :+: {
  def apply(c : Char, s : String) = c + s

  def unapply(s : String) : Option[(Char,String)] = s match {
    case "" => None
    case _ => Some((s.charAt(0),s.substring(1)))
  }
}

"foo" match {
  case 'f' :+: "ooo" => println("Not me.")
  case 'f' :+: 'o' :+: rest => println("The rest is " + rest + ".")
}


// unapplySeq allows for multi-arity extractors:
object Factor {

  def factor(n : Int) : List[Int] = n match {
     case 1 => List.empty
     case n => {
       for (i <- 2 to n) 
         if ((n % i) == 0)
           return i :: factor(n / i)
       return List(n,1)
     }
  }

  def unapplySeq(n : Int) : Option[List[Int]] = {
    return Some(factor(n))
  }
}

// 120 = 2 * 2 * 2 * 3 * 5
120 match {
  case Factor(a,b,c) => println("Not me.")
  case Factor(a,b,c,d,e) => println((a,c,e))
}
// Prints:
// (2,2,5)



// Pattern-matchable lists can be created from scratch:
abstract class MyList[+A] {
  def :*: [B >: A] (head : B) = new `:*:`(head,this)
}

case class :*:[A](val head : A, val tail : MyList[A]) extends MyList[A] 

case object MyNil extends MyList[Nothing] 

val l : MyList[Int] = 3 :*: 4 :*: 5 :*: MyNil

l match {
  case hd :*: tl => println(hd)
}

// Prints
// 3

// While loops are syntactic sugar in Scala:
def myWhile (cond : => Boolean) (body : => Unit) : Unit =
 if (cond) { body ; myWhile (cond) (body) } else ()

var i = 0 ;

myWhile (i < 4) { i += 1 ; println (i) }
// Prints:
// 1
// 2
// 3
// 4


// A benchmark construct:
def benchmark (body : => Unit) : Long = {
  val start = java.util.Calendar.getInstance().getTimeInMillis()
  body
  val end = java.util.Calendar.getInstance().getTimeInMillis()
  end - start
}

val myTime = benchmark {
 var i = 0 ;
 myWhile (i < 1000000) {
  i += 1 ;
 } 
}

println("myWhile took: " + myTime)

val time = benchmark {
 var i = 0 ;
 while (i < 1000000) {
  i += 1 ;
 } 
}

println("while took:   " + time)


// A short-circuiting or:
def myOr(left : Boolean, right : => Boolean) : Boolean = 
  if (left) { true } else { right }

println(myOr(true,throw new Exception("Boom!")))
// Prints:
// true

#!/bin/bash
scala $0 $@
exit
!#

/*
 A demonstration of implicits for embedding 
 domain-specific languages in Scala.  In this
 case, the DSL creates an AST for regular expressions.

 Exercise: Implement a matchesString method for RegEx
 */


abstract class RegEx {
  def ~ (right : RegEx) = Sequence(this,right)
  def || (right : RegEx) = Alternation(this,right)
  def * = Repetition(this)

  def matchesString(s : String) : Boolean =
    throw new Exception("An exercise for the reader!")
}

// Charaters:
case class CharEx(val c : Char)
 extends RegEx

// Sequences:
case class Sequence (val left : RegEx, val right : RegEx)
 extends RegEx

// Alternation:
case class Alternation (val left : RegEx, val right : RegEx) 
 extends RegEx

// Kleene repetition:
case class Repetition (val exp : RegEx)
 extends RegEx

// Empty:
case object Empty extends RegEx


// Building regex's manually is cumbersome:
val rx1 = Sequence(CharEx('f'),Sequence(CharEx('o'),CharEx('o')))


// Automatically convert strings into regexes:
implicit def stringToRegEx(s : String) : RegEx = {
  var ex : RegEx = Empty
  for (c <- s) {
    ex = Sequence(ex,CharEx(c))
  }
  ex
}

// Implicits + operator overloading makes the syntax terse:
val rx2 = "baz" ~ ("foo" || "bar") * ;
println(rx2)
// Prints:
// Repetition(Sequence(Sequence(Sequence(Sequence(Empty,CharEx(b)),CharEx(a)),CharEx(z)),Alternation(Sequence(Sequence(Sequence(Empty,CharEx(f)),CharEx(o)),CharEx(o)),Sequence(Sequence(Sequence(Empty,CharEx(b)),CharEx(a)),CharEx(r)))))

#!/bin/bash
scala $0 $@
exit
!#


/*
 Traits allow multiple inheritance is Scala.

 The order of inheritance is important!
 */


class Animal {
  def printName () {
  }
}


trait Man extends Animal {
  def height = 6 ;

  override def printName() {
    super.printName() ;
    println("Man") ;
  }
}


trait Bear extends Animal {
  val color = 'brown ;

  override def printName() {
    super.printName() ;
    println("Bear") ;
  }
}


trait Pig extends Animal {
  val shape = 'round ;

  override def printName() {
    super.printName() ;
    println("Pig") ;
  }
}



class ManBearPig extends Man with Bear with Pig 
class BearManPig extends Bear with Man with Pig
class PigBearMan extends Pig with Bear with Man
class PigManBear extends Pig with Man with Bear
class ManPigBear extends Man with Pig with Bear
class BearPigMan extends Bear with Pig with Man

(new ManBearPig).printName ;
// Prints:
// Man
// Bear
// Pig

(new BearPigMan).printName ;
// Prints:
// Bear
// Pig
// Man

(new Animal with Man with Bear).printName ;
// Prints:
// Man
// Bear

#!/bin/bash
scala $0 $@
exit
!#


/*
 Sorted maps require a comparison procedure.  

 Sorted data structures will use an 'implicit' function for converting
 to Ordering if one is in scope.

 If one is not in scope, it must be specified.
*/


import scala.collection.immutable.{SortedMap,TreeMap} ;

/**
 A Person is a social security number and a name.
 */
case class Person(val ssn : Int, val name : String) 


// val db1 : SortedMap[Person,Symbol] = TreeMap[Person,Symbol]()
// ERROR!
// Person is not ordered!


/**
 Implicitly converts a Person to an Ordered[Person], 
 using SSNs to compare.
 */
implicit object OrderingBySSN extends Ordering[Person] {
  def compare (p1 : Person, p2 : Person) : Int = p1.ssn - p2.ssn
}


val db1 : SortedMap[Person,Symbol] = TreeMap[Person,Symbol]()

val db2 = db1 + ((Person(1,"Matt")) -> 'Chicken)
val db3 = db2 + ((Person(2,"Matt")) -> 'Mouse)

println(db3)
// Prints:
// Map(Person(1,Matt) -> 'Chicken, Person(2,Matt) -> 'Mouse)




/**
 Explicitly converts a Person to an Ordering[Person],
 using names to compare.
 */
object OrderingByName extends Ordering[Person] {
  def compare (p1 : Person, p2 : Person) : Int = p1.name compare p2.name
}


val dbX : SortedMap[Person,Symbol] = 
 TreeMap[Person,Symbol]()(OrderingByName)

val dbY = dbX + ((Person(1,"Matt")) -> 'Chicken)
val dbZ = dbY + ((Person(2,"Matt")) -> 'Mouse)

println(dbZ)
// Prints:
// Map(Person(2,Matt) -> 'Mouse)

#!/bin/bash
scala $0 $@
exit
!#


/*
 Note the difference between how the update behaves for immutable and
 mutable data structures. 
 */


val mutHashMap = new scala.collection.mutable.HashMap[String,Int]
val immHashMap = new scala.collection.immutable.HashMap[String,Int]

mutHashMap("Foo") = 1
immHashMap("Foo") = 1

println(mutHashMap)
// Prints:
// Map(Foo -> 1)

println(immHashMap)
// Prints:
// Map()

println(immHashMap("Foo") = 1)
// Prints
// Map(Foo -> 1)

/* If an object extends Application, then the body of the object is
   effectively a script. */

object DemoApplication extends Application {

  /*
   Warning (courtesy of Dean Wampler): 

   Extending Application runs the entire program in the constructor
   for the object, which prevents the JVM from performing JIT
   optimizations.

   For large applications, use a main() method instead of extending
   Application.
  */

  println("Hello, World!")
}

/* An object with a main method is a program. */

object DemoApplication2 {
  def main (args : Array[String]) {
    println("Hello, World!") 
  }
}

/*
 Demo:   A lightweight unit-testing framework.
 Author: Matthew Might
 Site:   http://matt.might.net/
         http://www.ucombinator.org/

 A home-grown unit-testing library, demonstrating the utility of
 by-name parameters.
 */


/**
 Thrown when checkThat fails.
 */
case class CheckException extends RuntimeException

/**
 Thrown when a check fails and there is information as to why.
 */
case class ReasonedCheckException(reason : String) extends CheckException



/**
 The Check object contains methods for testing.
 */
object Check {

  /**
   Determines whether checks happen at runtime.
   */
  var checksEnabled = true
  
  /**
   The === equality throws an exception on false.
   */
  abstract class CheckEquality[A] {
    def === (a : A) : Boolean
  }

  /**
   Implicitly adds === to every object in Scala.
   */
  implicit def checkEqualable[A] (a : A) : CheckEquality[A] = 
    new CheckEquality[A] {
      def === (b : A) : Boolean = {
        if (a != b) {
          throw new ReasonedCheckException(a + " != " + b) 
        }
        return true
      }
    }


  /**
   Throws an execption if its argument doesn't evaluate to true.
   */
  def checkThat (action : => Boolean) {
    if (checksEnabled) {
      if (!action)
        throw new CheckException
    }
  }
}



import Check._


/**
 Unit test suites should inherit from TestSuite.
 */
trait TestSuite {

  /**
   The test method defines new tests.
   */
  def test[A] (description : String) (action : => A) {

    try {
      action
      println ("test passed: " + description) 
      return ()
    }
    catch {
      case (e : Exception) => {
        println("test failed: " + description)
        println("exception thrown: " + e)
      }
    }
  }


}



class ArithmeticTests extends TestSuite {

  test ("2 equals 2") {
    checkThat (2 === 2)
  }

  test ("2 plus 2 equals 4") {
    checkThat (2 + 2 === 4)
  }

  test ("2 equals 3") {
    checkThat (2 === 3)
  }

}





object DemoTesting extends Application {
  (new ArithmeticTests)
}

/*
 Author: Matthew Might
 Site:   http://matt.might.net/
         http://www.ucombinator.org/

 This is a companion file for DemoScalaPet.scala
 */


public class Pet {
    private String name ;
    
    public Pet(String name) {
        this.name = name ;
    }

    public String getName() {
        return name ;
    }
}

/*
 Demo:     Interacting with Java classes, and creating Scala classes.
 Author:   Matthew Might
 Site:     http://matt.might.net/
           http://www.ucombinator.org/

 See also: Pet.java
 */


// Interacting with a Java class:
object DemoScalaPet extends Application {

  val javaPet = new Pet("Steve")

  println(javaPet.getName())
  // Prints:
  // Steve
}


// With a Java-like accessor:
class ScalaPet(petName : String) {
  private val name = petName
  def getName() = name
}


// Without the superfluous private field:
class ScalaPet1(petName : String) {
  def getName() = petName
}


// Without the () on the accessor:
class ScalaPet2(petName : String) {
  def getName = petName
}


// Using val to generate the accessor:
class ScalaPet3(val name : String)


// Using var to generate the mutator:
class ScalaPet4(var name : String)


// Enumeration via pattern-matchable objects:
abstract class Breed 
case object Chihuahua extends Breed
case object Collie extends Breed
case class Pinscher(isMiniature : Boolean) extends Breed

// A pattern-matchable Dog class:
case class Dog(override val name : String, breed : Breed)
 extends ScalaPet3(name)


// Playing with Dogs:
object DogMatcher extends Application {

  val d1 = Dog("Penny", Pinscher(true))

  val d2 = Dog("Chico", Chihuahua) 

  val d2name = d2 match {
    case Dog(name,_) => name
  }

  println(d2name)
  // Prints:
  // Chico

  def isMinPin (d : Dog) = d match {
    case Dog(_,Pinscher(true)) => true
    case _ => false
  }

  println(isMinPin(d1))
  // Prints:
  // true
  
  println(isMinPin(d2))
  // Prints:
  // false
}

/*
 Demo:   Solving algebraic equations with custom patterns.
 Author: Matthew Might
 Site:   http://matt.might.net/
         http://www.ucombinator.org/
 */


/* 
 Scala allows programmers to define custom case constructors and
 deconstructors using the apply and unapply methods.

 Deconstructors are invoked to take a value apart during pattern
 matching with 'match' and 'case'.

 If the method apply has type X -> Y, then the method unapply should
 have the type Y -> Option[X].

 The intended contract for these methods is 

  (1) unapply(apply(x)) == Some(x), and

  (2) if unapply(y) = Some(x), then apply(x) == y.

 One use of this mechanism is to prevent grep/replace-programming when
 the definition of a case class's constructor changes.

 Custom patterns can also be used to match on the semantics of a
 value, rather than just its structure.
 */



object Succ {
  def apply (x  : Double) : Double = 
    x + 1.0

  // matches: _ + 1.0
  def unapply (x : Double) : Option[Double] = 
    Some(x - 1.0)
}


object Pred {
  def apply (x  : Double) : Double = 
    x - 1.0

  // matches: _ - 1.0
  def unapply (x : Double) : Option[Double] =
    Some(x + 1.0)  
}


object Square {
  def apply(x : Double) : Double = x * x

  // matches: _ ^ 2
  def unapply (x : Double) : Option[Double] = 
    Some(Math.sqrt(x))
}


object By2 {
  def apply(x : Double) : Double = x * 2.0

  // matches: _ * 2.0
  def unapply (x : Double) : Option[Double] = 
    Some(x / 2.0)
}


object Over2 {
  def apply(x : Double) : Double = x / 2.0

  // matches: _ / 2.0
  def unapply (x : Double) : Option[Double] = 
    Some(x * 2.0)
}



object DemoAlgebra extends Application {

  // Solve for x: 
  // 145 = x^2 + 1

  145.0 match {
    case Succ(Square(x)) => println(x)
  }
  // Prints:
  // 12.0


  // A pattern-generator:
  def NSucc(n : Double) = new Object {
    def unapply (x : Double) = Some(x - n)
  }

  val NSucc30 = NSucc(30)

  100.0 match {
    case NSucc30(x) => println(x)
  }
  // Prints:
  // 70.0

}

/*
 Author: Matthew Might
 Site:   http://matt.might.net/
         http://www.ucombinator.org/


 This file demonstrates a domain-specific language (DSL) embedded in
 Scala.

 The function Exp.free demonstrates functional, pattern-matching-based
 tree-walking, whle Exp.reduced demonstrates object-oriented
 tree-walking.

*/


/**
 An Exp object can be either a variable reference, a lambda term or an
 application.
 */
abstract class Exp {

  /**
   Creates an application term when one term is applied to another.
   Serves as syntactic sugar for the DSL.
   */
  def apply(arg : Exp) : Exp = App(this,arg)

  /**
   Produces a term with subst._1 replaced with subst._2
   */
  def apply(subst : (Symbol,Exp)) : Exp ;

  /**
   Returns this term as fully call-by-value reduced as possible.
   */
  def reduced : Exp ;
}


/**
 A Lam term has a parameter variable and a body expression.
 */
case class Lam (v : Symbol, body : Exp) extends Exp {

  def apply(subst : (Symbol,Exp)) = 
    if (v == subst._1)
      this
    else if (Exp.free(body) contains v)
      throw new Exception("Variable capture while substituting " + 
                          subst._2 + " for " + subst._1 +
                          " in " +  body)
    else
      Lam(v,body(subst))
  
  def reduced = this

  override def toString = "(lambda ("+v.name+") "+body+")"
}


/**
 A Ref term evaluates to the value of the variable.
 */
case class Ref(v : Symbol) extends Exp {
  
  def apply(subst  : (Symbol,Exp)) = 
    if (subst._1 == v)
      subst._2 
    else
      this

  def reduced = this

  override def toString = v.name
}


/**
 An App term encodes a function call.
 */
case class App(f : Exp, e : Exp) extends Exp {
  
  def apply(subst : (Symbol,Exp)) =
    App(f(subst), e(subst))

  def reduced = f.reduced match {
    case Lam(v,body) => body (v -> e.reduced)
    case _ => this
  }

  override def toString = "("+f+" "+e+")"
}


/**
 Exp is a companion object for class Exp that contains helper methods.
 */
object Exp {

  /**
   Returns the free variables inside a term.
   */
  def free (e : Exp) : Set[Symbol] = e match {
    case Ref(v) => Set(v)
    case Lam(v,body) => free(body) - v
    case App(f,e) => free(f) ++ free(e)
  }

  /**
   Sugar for lambda.
   */
  def λ (v : Symbol) (body : Exp) : Exp = 
    Lam(v,body)


  /**
   More sugar for lambda.
   */
  implicit def λ (f : Ref => Exp) : Exp = {
    genSymCounter = genSymCounter + 1
    val s = Symbol("$v" + genSymCounter)
    Lam(s,f(Ref(s)))
  }


  /**
   A counter for generated symbols.
   */
  private var genSymCounter = 0


  /**
   Abstractable objects become lambda terms when coupled with an expression.
   */
  abstract class Abstractable {
    def :-> (body : Exp) : Lam ;
  }

  /**
   Provides a Scala-like way of writing anonymous functions.
   */
  implicit def symbolToAbstractable (s : Symbol) : Abstractable = 
    new Abstractable {
      def :-> (body : Exp) : Lam = 
        Lam(s,body)
    }

  /**
   Sugar for references.
   */
  implicit def symbolToRef(s : Symbol) : Exp = 
    Ref(s)

  
}



object DemoLambda extends Application {

  import Exp._

  // Identity function:
  val id = λ ('x) ('x)

  // U combinator:
  val U = λ (f => f(f)) 

  val U2 = λ {h => h(h)}

  val U3 : Exp = (f : Ref) => f(f)

  val U4 = 'f :-> 'f('f)


  // Identity applied to identity:
  val idid = U(id)

  // Identity applied to z:
  val appz = id('z)

  // f applied to x:
  val appfx = 'f('x)
  

  println(id)
  // Prints:
  // (lambda (x) x)

  println(idid)
  // Prints:
  // ((lambda ($v1) ($v1 $v1)) (lambda (x) x))

  println(appz)
  // Prints:
  // ((lambda (x) x) z)  
  
  println(appfx)
  // Prints:
  // (f x)
  
  println(free(appz))
  // Prints:
  // Set('z)

  println(idid.reduced)
  // Prints:
  // (lambda (x) x)
  
  println(appz.reduced)
  // z
}