scala exercises

exers.scala

 
//private[this]
class T{private val name = "jack";private[this] val age = 28; def say = {val t = new T; t.age+t.name}}
class Test[-T,+U] { private[this] var s:U=_; private[this]var t:T=_;def say(a:T):U={ def info(b:T):T = t;  s}}

 
//lazy
def say(a: =>Int) = {a;lazy val b= {println(2);a};b;b}
say({println(3);1})

//throw
@throws(classOf[Exception])
def say(a:Int)={
val  = try{2/0}catch{case _=>3}finally{2}
}

//reflect.BeanProperty
@BeanProperty
val name = "jack" //(产生 getName 方法）
var age = 25 //(产生setSex 和getSex方法）

//内部内
trait A{ class B}
val s:A#B = null


//子类转换
def up[T<:A](a:T):A = a
类似
def up[T](a:T)(implicit ev T<:<A):A = a

//implicit 
//finding order 1. context
//2. class A and object A
//3. class B and object B
object D{ implicit def conv2(a:B):A = new A}
class A
class B
object A{ implicit def conv(a:A):B = new B}
object C extends D{ def ss(a:B)(implicit c:B=>A):A = a; def say(a:A)(implicit c:A=>B):B = a}


//协变和逆变
trait B[-T1,+T2] extends Function1[T1,T2]{def apply(a:T1):T2 }
class T extends B[Int,String]{ def apply(a:Int) = a+"2"}

//模拟filter chain
 def say1(a:Int) = a+1
 def say2(a:Int) = a+2
 (say1 _ andThen say2)(3) 

 //类似===>
  trait A[T]{ def say(a:T):T}
  
  object T1 extends A[String]{ def say(a:String):String = a.replace(">","")}
 
  object T2 extends A[String]{ def say(a:String):String = a.replace("<","")}
 object Te{
  val ss = List(T1,T2)
  (">M<"/:ss)((x,y)=> y say x)
 }


//中缀类型
type of[M[_],T] = M[T]
//>>(a,b) -> a >> b 中缀操作符的magic
object >>{ def unapply(a:String):Option[(Int,Int)] = Some(s.length,3)}
val s >> t = "hello"

//预初始化
trait A{val a:Int;require(a!=0)}
class B { val a = 3}
class C(val a:Int)
new { val a = 2} with A
object B extends { val a = 2} with A //此处相当于构造参数初始化。
new B with A 
new C with A

//trait线性化
trait A{ val a = println(1)}
trait B{ val b = println(2)}
trait C{ val c = println(3)}
class D extends A with B with C
//初始化A->B->C->D,切 push stack
 Stack.push(A)->push(B)->push(C)->push(D)
//so when super call,  D->C->B->A
D.say ->super ->C.say-> super-> B.say->super-> A.say

-----------------------
//why 逆变
[-T](http://stackoverflow.com/questions/5351899/example-of-contravariance)
//协变是为了类型不可变，如List[+T], Array是可变
class A[+T]{def say[U>:T](a:U) = a} //确保A是不可变的。
class List[+T,U<:T]{def say(a:U):T = a} //确保可以返回合适的值,def ss(a:List[B,B],b:B):List[A,B] = b :: a //( [A,B]=[B,B])

class A[-T,U>:T]{def say(a:T):U = a}

-----------------------
//why 如果不带[],会根据目标引用类型来推断类型
class A[T] {} // compiler: class A[T>:Any <:Nothing]
scala> val s:A[Any] = new A
// 自动根据s构建了对象A[Any]类型
scala> new A
res0: A[Nothing] = A@f49e8f
val a1 = Array(3) //调用  def apply(x: Int, xs: Int*): Array[Int] = {
val a2:Array[Any] = Array(3)//调用 def apply[T: ClassManifest](xs: T*): Array[T] = {

-----------------------

//collection
Map extends PartialFunction //为了apply的参数是在集合中存在的值。 偏函数是过滤某些参数的函数，是函数的子类。
Seq extends PartialFunction//为了apply的参数只能是在区间[0,length]中。
Set extends (A=>Boolean) //Set('a')('a') = true

List(1,2) == Vector(1,2) //GenSeqLike.equals = (that canEqual this) && (this sameElements that)

(1 to 10 zipWithIndex) foreach{case (x,y)=>x+y} //operator by index
List(2):+1 
1+:List(3)
//Ordered 的AnyVal类型implicit来自于Ordering
xs flatMap f = (xs map f) flatten

//Map defaultValue set
Map(2->3) withDefaultValue 2
val (x,y) = (2->3) // (x,y)* toMap
1 to 20 map Map(1->2,2->3) // Map(1->2) _  : function0 , 1 to 20 map{ x=>Map(1->2,2->3)(x)}

//Stream(水流，水龙头，当需要的时候打开）range and streamRange dist
range（1，2） filter 是先产生集合，然后过滤
streamRange（1，3） filter 是边过滤，边产生
def from(a:Int):Stream[Int] = a#:: from(a+1)
//sieve筛子
def sieve(s:Stream[Int]):Stream[Int]  = s.head #:: sieve(s.tail filter (_ % s.head !=0))
val primes = sieve(from(2))//所有的质数
//sqrt root
def sqrtStream(x:Double):Stream[Double] = {
   def improve(guess:Double) = (guess+x/guess)/2
   val guesses:Stream[Double] = 1#::(guesses map improve)

msort.scala

//proof 归纳
//f: Nil ++Xs = Xs
//s: (x::xs) ++ys = x::(xs++ys) 

//只能AnyVal
def msort[T<%Ordered[T]](xs: List[T]): List[T] = { 
  @tailrec
  def merge(xs: List[T], ys: List[T], acc: List[T]): List[T] = 
    (xs, ys) match { 
      case (Nil, _) => ys.reverse ::: acc 
      case (_, Nil) => xs.reverse ::: acc
      case (x :: xs1, y :: ys1) => 
        if (x<y) merge(xs1, ys, x :: acc) 
        else merge(xs, ys1, y :: acc) 
    } 
  val n = xs.length / 2 
  if (n == 0) xs 
  else { 
    val (ys, zs) = xs splitAt n 
    merge(msort(ys), msort(zs), Nil).reverse
  } 
} 
//Using non-strictness involves either passing parameters by-name, or using non-strict collections such as Stream. The following code uses Stream just to prevent stack overflow, and List elsewhere:

def msort[T](xs: List[T])(implicit ord:Ordering[T]): List[T] = { 
   
  def merge(left: List[T], right: List[T]): Stream[T] = (left, right) match {
    case (x :: xs, y :: ys) => 
        if(ord.lt(x,y))  Stream.cons(x, merge(xs, right))
        else Stream.cons(y, merge(left, ys))
    case _ => if (left.isEmpty) right.toStream else left.toStream
  }
  val n = xs.length / 2 
  if (n == 0) xs 
  else { 
    val (ys, zs) = xs splitAt n 
    merge(msort(ys), msort(zs)).toList
  } 
}

queen.scala

def queen(n:Int):Set[List[Int]] = {
  
   def place(k:Int):Set[List[Int]] ={
    if(k==0) Set(List())
    else 
       for{
           que<-place(k-1) // que=List(1) 是 (row ,col) = (0,1)
           col<-0 until n
           if isSafe(col,que)
        } yield col :: que

      }
   
    def isSafe(col:Int,dots:List[Int]):Boolean = {
         val row = dots.length
         val dotsWithPairs = ((row -1 ) to 0 by -1) zip dots
          dotsWithPairs forall {
            case (r,c) => c!=col && math.abs(c-col) != row-r
          } 
     
   }
  
   place(n)
}

 def show(s:List[Int]) = {
    val lines = for(col <- s) yield Vector.fill(s.length)("* ") .updated(col,"x ").mkString
    "\n" + (lines mkString "\n")
 }

           

translate-phonenumber.scala

def translate(phone:String):Set[String] =  //TODO

val phoneKey:Map[Char,String] = Map('2'->"ABC",'3'->"DEF",'4'->"GHI",5->"JKL",6->"MNO",7->"PQRS",8->"TUV",9->"WXYZ")

val numberPairChar:Map[Char,Char] =  for((number,str) <-phoneKey ; letter<- str) yield number->letter

//word  to  number ; eg: "hello"-> xxxx
def wordToNumber(s:String):String = s.toUpperCase map numberPairChar mkString

def numberPairString(ls:List[String]):Map[String,List[String]] = 
         ls groupBy wordToNumber withDefaultVale List()

//"2789" 中 2 => List( List("jack wom hask"),)  ; 27 => List(List(...),List(...)) 一串号码数能打出库里面的什么单词
def encode(phone:String):List[List[String]] =
  for{ sp<- 0 to phone.length
       word<- numberPairString(phone take sp)
       rest<- encode(phone drop sp)
     } yield word :: rest

  
  

def msort[T](less: %28T, T%29 => Boolean)
(xs: List[T]): List[T] = {
def merge(xs: List[T], ys: List[T], acc: List[T]): List[T] =
(xs, ys) match {
case (Nil, ) => ys.reverse ::: acc
case (, Nil) => xs.reverse ::: acc
case (x :: xs1, y :: ys1) =>
if (less(x, y)) merge(xs1, ys, x :: acc)
else merge(xs, ys1, y :: acc)
}
val n = xs.length / 2
if (n == 0) xs
else {
val (ys, zs) = xs splitAt n
merge(msort(less)(ys), msort(less)(zs), Nil).reverse
}
}
Using non-strictness involves either passing parameters by-name, or using non-strict collections such as Stream. The following code uses Stream just to prevent stack overflow, and List elsewhere:

def msort[T](less: %28T, T%29 => Boolean)
(xs: List[T]): List[T] = {
def merge(left: List[T], right: List[T]): Stream[T] = (left, right) match {
case (x :: xs, y :: ys) if less(x, y) => Stream.cons(x, merge(xs, right))
case (x :: xs, y :: ys) => Stream.cons(y, merge(left, ys))
case _ => if (left.isEmpty) right.toStream else left.toStream
}
val n = xs.length / 2
if (n == 0) xs
else {
val (ys, zs) = xs splitAt n
merge(msort(less)(ys), msort(less)(zs)).toList
}
}