3 Aug 2016

Scala: fold, foldLeft & foldRight



foldLeft vs foldRight (hình trộm từ Internet)

foldLeft được implement như sau:
override /*TraversableLike*/def foldLeft[B](z: B)(@deprecatedName('f) op: (B, A) => B): B = {
  var acc = z
  var these = this  while (!these.isEmpty) {
    acc = op(acc, these.head)
    these = these.tail
  }
  acc
}
Như vậy foldLeft là một curried function với tham số đầu vào (giá trị bắt đầu) là z có kiểu là B, và một function op. op có tham số đầu vào là 2 biến có kiểu B và A,  và giá trị trả về có kiểu là B. 
Hàm foldLeft dùng while loop (không dùng đệ quy), và thực hiện op trên biến mutable acc và phần tử đầu tiên của list these (these.head), đồng thời gán lại giá trị cho list these cho đến khi length của these = 0 (empty).

Nhìn vào hình minh hoạ đầu bài. Để minh hoạ quá trình chạy của foldLeft, ta thực hành trên một ví dụ như sau: 
List("1","2","3").foldLeft("")((x, y) => { 
  print("x="+x); print(" & "); 
  print("y="+y); 
  println(" => x+y=" + x+y); 
  x + y
})
Khi chạy, đoạn code trên cho output:
x= & y=1 => x+y=1
x=1 & y=2 => x+y=12
x=12 & y=3 => x+y=123
res44: String = 123
Kết quả trả về có kiểu String, type B trong khai báo foldLeft. Method "+" chúng ta dùng ở đây là string concatenation, không phải method addition trong toán học.

Vậy hàm trên bắt đầu bắt giá trị khởi đầu start (z) là: "" được gán cho x, và y là List("1", "2", "3").head => "1", thực hiện op("", "1") => "" + "1" là cộng chuỗi ta có kết quả 1, dùng kết quả này chạy tiếp vối op, ta có sơ đồ sau:
op("", "1") => op("1", "2") => op("12", "3")
"1"             => "12"             => "123"  
fold: Bài này nhắc đến foldLeft trước fold vì fold là một dạng triển khai của foldLeft(1)
def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1 = foldLeft(z)(op)
Chỉ khác là fold thao tác trên kiểu A1, là một supertype của A, và trả về kiểu A1. Sự khác nhau ở đây là gì? Nếu ta dùng fold với op có tham số đầu vào là Int, thì type A1 sẽ là AnyVal, do Int là một implement của AnyVal. Còn nếu dùng fold với op có tham số đầu vào là String, thì type A1 sẽ là Any, do String của scala kế thừa lại của Java, và trong Scala tất cả các kiểu đều kế thừa từ Any.

Vậy nếu ta fold trên một List có kiểu String, và dùng op với thông số đầu vào là kiểu Int, thì A1 sẽ có type là Any, do String và Int có chung supertype là Any. Và do Any không có method + (cả concatenation và addition), nên ta không thể dùng fold như bên dưới:
List("1","2","3").fold(0)((x, y) => {
  print("x="+x); print(" & ");
  print("y="+y);
  println(" => x+y=" + x+y);
  x + y
})
Hoặc
List("1","2","3").fold(0)((x, y) => {
  print("x="+x); print(" & ");
  print("y="+y);
  println(" => x+y=" + x+y);
  x + y.toInt
})
Ta chỉ có thể dùng fold với biến đầu vào cho op là String, hoặc Unit hoặc char
List("1","2","3").fold("")((x, y) => {
  print("x="+x); print(" & ");
  print("y="+y);
  println(" => x+y=" + x+y);
  x + y
})
Trong trường hợp muốn dùng fold trên một List[String] và kết quả trả về là Int, ta buộc phải dùng foldLeft hoặc foldRight.

foldRight: được implement như sau
override def foldRight[B](z: B)(op: (A, B) => B): B =
  reverse.foldLeft(z)((right, left) => op(left, right))
Tham số đầu vào của foldRight hoàn toàn giống với foldLeft. Cách implement có khác một chút:

  • reverse là một method được implement bên trong class List.scala, sẽ đảo ngược List đang làm việc. Nhìn vào có vẻ khó hiểu nếu như ta nhìn theo logic thông thường ta dễ nhầm lẫn foldLeft được gọi như một method của reverse, nhưng thật ra ta đang dùng foldLeft như method của List được trả về khi gọi hàm reverse. Tương tự như ta dùng map như bên dưới: 

List(1, 2, 3).reverse.map(_ + 1)

  •   Tương tự như ví dụ ban đầu, áp dụng foldRight:

List("1","2","3").foldRight("")((x, y) => {
print("x="+x); print(" & ");
print("y="+y);
println(" => x+y=" + x+y);
x + y})
          Khi chạy đoạn code trên, ta sẽ có output:
x=3 & y= => x+y=3
x=2 & y=3 => x+y=23
x=1 & y=23 => x+y=123
res4: String = 123
Kết quả trả về cùng kiểu String như foldLeft, như thay vì op (x + y) được apply ở foldLeft là "" + List("1", "2", "3).head thì được thay bằng List("1", "2", "3").reverse.head + "", ta có sơ đồ sau:
op("", "3") => op("3", "2") => op("23", "1")
và vì op sẽ đảo thứ tự của 2 biến đầu vào nên ta sẽ có
"3" + ""     =>  "2" + "3"     => "1" + "23" = "123"

(1)Scala có 2 dạng triển khai của method fold, một dành cho các cấu trúc dữ liệu dạng chuỗi thông thường, và một phức tạp hơn dành cho parallel collection, sẽ được nói đến trong một bài khác. 

2 Aug 2016

Scala: Một vài điểm lưu ý khi làm việc với List

a. Scala tồn tại 2 khái niệm cùng được biểu diễn bằng ::, một là method của companion class List, 2 là constructor của class scala.::.
Khi làm việc với List chúng ta có "cons" pattern hay còn có tên là prepend method. 

Method này được biểu diễn như sau:
def ::[B >: A] (x: B): List[B] =
  new scala.collection.immutable.::(x, this)
Trong đó x là phần tử được gắn vào đầu của List sau khi method này được gọi (thay vì nối vào cuối).
Do vậy nếu gọi
 1::List(2, 3)

Thì ta có kết quả là List[Int] = List(1, 2, 3) thay vì List[Int] = List(2, 3, 1) khi gọi method append (:::)
Một chú ý quan trọng trong scala, khi gặp các method bắt đầu từ dấu ":", thì method này được apply từ phải qua trái, thay vì từ trái qua phải. Với ví dụ trên, có thể viết lại thành List(2,3).::(1)

Nhưng khi làm việc với pattern matching trên List, chúng ta thường triển khai như sau:
//reverse một List

def rev[T](xs: List[T]): List[T] = xs match {
  case List() => xs
  case x :: xs1 => rev(xs1) ::: List(x)
}
Để ý khi chúng ta dùng case x::xs1, chúng ta đang không sử dụng method prepend của List, mà đang sử dụng một constructor. 
Khi sử dụng pattern matching trên List, chúng ta đang sử dụng scala.:: constructor, không phải sử dụng method prepend của List. Do vậy khi gọi x::xs1, ta  đã tạo ra một instance của class scala.::, để dễ hiểu ta có thế viết lại bàm reverse List như sau:
//reverse một List

def rev[T](xs: List[T]): List[T] = xs match {
  case List() => xs
  case scala.::(_, _) => rev(xs.tail) ::: List(xs.head)
}
b. Lấy chiều dài của List là một thao tác tốn nhiều resource, ta phải duyệt qua hết các phần tử của List cho đến phần tử cuối cùng để lấy chiều dài, do vậy nếu không có nhu cầu đặc biệt cần lấy chiều dài của List, để kiểm tra List có rỗng hay không, thay vì kiểm l.length == 0, nên dùng l.isEmpty.

c. Cũng vì lí do trên, nên trong hầu hết trường hợp, để thêm một phần tử mới vào List, ta nên dùng method prepend (::), thay vì append(::). Và cố gắng sắp xếp dữ liệu để các phần tử thường xuyên được dùng nằm ở đầu của List thay vì ở cuối.

1 Aug 2016

Tổng quan về hàm trong scala

Scala cho chúng ta nhiều cách để khai báo function, trong đó có:

Local function (ví dụ bên dưới có vẻ ngu ngốc, vì ta hoàn toàn có thể dùng filter với anonymous function x.filter(_ > 1) , nhưng nó nói lên được ý nghĩa của local function và phần nào làm rõ nghĩa được filter method của List

def filterInt(x: List[Int]): List[Int] = {
   def f(y: Int, z: Int) = {
     y > z
  }
  x.filter(f(_, 1))
}

First-class Function: Không như cách chúng ta khai báo một hàm và gọi hàm đó bằng tên, như ví dụ bên trên: filter(List(1, 2, 3), Scala còn cho phép khai báo hàm không tên (unamed literal function) và truyền vào các hàm khác như một giá trị (function value). Một cách để biểu diễn loại hàm này là viết lại hàm bên trên sử dụng filter method của List như sau:

a.filter((x) => x > 1)

hoặc lược 2 dấu  ( và )  : a.filter(x => x > 1)
như vậy
(x) => x > 1 hoặc x => x > 1

được dùng như một biến đầu vào, scala gọi là function value. Mở rộng cách dùng function value không dùng built-in method của scala:

def addMore(op: (Int) => Int, y: Int ) = {
  op(y)
}

val ten = (x: Int) => x + 10
val two = (x: Int) => x + 2

addMore(ten, 1) // 11
addMore(two, 1) // 3


Partial applied function: Trong một vài trường hợp khi khai báo một hàm nhưng ta chưa đủ các dữ liệu mà chỉ có được một phần trong danh sách dữ liệu, có thể dùng partial applied function - hàm với các biến cục bộ:



def sum(x: Int, y: Int): Int = {
  x + y
}

Có thể dùng sum như sau trong trường hợp chỉ có giá trị của x:

val plusOne = sum(1, _:Int)

sau các bước tính toán và có giá trị của y, lấy kết quả:

plusOne(10) // 11

Closure:   Thông thường khi khai báo các hàm, chúng ta thường sử dụng các biến được khai báo bên trong ngữ cảnh của hàm đó, như x và y trong ví dụ bên trên. Các biến này được gọi là bound variable hay là các biến đóng. Ngoài khái niệm biến đóng, Scala (hay các ngôn ngữ khác cho ta một khái niệm khác là biến tự do, ví dụ:


var i = 5;
val f = (x: Int) => x + i
f(10) //15
  
Khái niệm closure (closing + capturing free variables)  được tạo nên bởi thuật ngữ chỉ một function value được tạo ra khi chương trình chạy (runtime). Với ví dụ trên, khi i thay đổi, giá trị của f cũng sẽ thay đổi theo (chú ý ta không khai báo i là val mà là var) 
Nếu thay đổi giá trị của i

i = 6
println(f(10))

Thì giá trị được in ra là 6, chứ không phải là 15

Ta áp dụng closure như sau: 


def increase(more: Int) = {
  (x: Int) => x + more

}



val f1 = increase(10)

println(f1(3)) //13

val f2 = increase(11)

println(f2(3)) //14


Các cách gọi hàm khác: 


Scala cho phép tham số cuối của một hàm có thể được lặp, chú ý ta chỉ có thể lặp lại tham số cuối, cho nên ta có thể khai báo:

def repeatSecondArgs(first: Int, args: Any*): Unit = {
  println(first + args.mkString(" ", " ", ""))
}
repeatSecondArgs(1000, "Hello", "World") //prints "1000 Hello World"

Nhưng không thể khai báo:

// Compiler sẽ báo lỗi 
def printFirstArgs(first: Int*, second: String): Unit = { println(args.mkString(" ")) }

Ngoài ra chúng ta có thể truyền tham số với tên biến đầu vào:

class Student(val Name: String, val age: Int) {
  require(age >= 18)
  override def toString(): String = {
    "[" + Name + ":" + age.toString + "]"  }
}

def createStudent(name: String, age: Int): Student = {
  new Student(name, age)
}
val hung = createStudent("Hung", 30)
val hung1 = createStudent("Hung", age = 30)
val hung2 = createStudent(age = 30, name = "Hung")

println(hung) //[Hung:30]
println(hung1) //[Hung:30]
println(hung2) //[Hung:30]
Hoặc khai báo hàm với tham số mặc định:
def getSalary(workingHours: Int, factor: Float = 1.0F, payPerHour: Float = 12.0F): Float = {
  payPerHour*workingHours*factor
}

println(getSalary(60)) // 72.0
println(getSalary(60, factor = 1.2F)) // 864.00006
println(getSalary(60, payPerHour = 12.5F)) // 750.0


Partial Function: xem bài trước

Currying: là một cách biến đổi phương thức thực thi của một hàm có đầu vào là nhiều tham số thành một chuỗi các hàm riêng lẻ với đầu vào là một tham số duy nhất. Ví du với hàm bên dưới

def sum(x: Int, y: Int): Int = {
  x + y
}

Để chuyển sum thành curried function trong scala ta khai báo hàm lại như sau:

def sum(x: Int)(y: Int) = {
  x + y
}

Dùng sum được khai báo bên trên:

val plus10 = sum(10)_

println(plus10(20))



Thậm chí có thể khai báo nhiều hơn 2 danh sách tham số:

def sum(x: Int)(y: Int)(z: Int) = {
  x + y + z
} 

Để hiểu được nhu cầu sử dụng curried function trong thực tế phải có một bài riêng để nói về currying. Khi nhìn vào cách sử dụng currying thì ta thấy curry tương tự như function value. Như ví dụ bên dưới, khai báo hàm sort một List các phần tử sử dụng merge sort. Với currying ta dùng như sau:

def msort[T](cmp: (T, T) => Boolean) (xs: List[T]):List[T] = {

  def merge(xs: List[T], ys: List[T]): List[T] =
    (xs, ys) match {
      case (xs, Nil) => xs
      case (Nil, ys) => ys
      case (x::xs1, y::ys1) =>  {
        if (cmp(x, y)) x:: merge(xs1, ys)
        else y::merge(xs, ys1)
      }
  }
  val n = xs.length / 2  if (n == 0) xs
  else {
    val (ys, zs) = xs splitAt n
    merge(msort(cmp)(ys), msort(cmp)(zs))
  }
}

Khi dùng function value cũng tương tự:

def nonCurriedMsort[T](cmp: (T, T) => Boolean, xs: List[T]):List[T] = {

  def merge(xs: List[T], ys: List[T]): List[T] =
    (xs, ys) match {
      case (xs, Nil) => xs
      case (Nil, ys) => ys
      case (x::xs1, y::ys1) =>  {
        if (cmp(x, y)) x:: merge(xs1, ys)
        else y::merge(xs, ys1)
      }
    }
  val n = xs.length / 2  if (n == 0) xs
  else {
    val (ys, zs) = xs splitAt n
    merge(nonCurriedMsort(cmp, ys), nonCurriedMsort(cmp, zs))
  }
}

val l = List(1, 3, 2, 5, 4, 9, 6)
def cmp(x: Int, y: Int) = x < y
msort(cmp) (l)
nonCurriedMsort(cmp, l)

val a = msort(cmp)_ 
val b = nonCurriedMsort(cmp, _: List[Int])
a(l) 
b(l)


Ví dụ về merge sort lấy từ Programming scala 2nd. Hi vọng sẽ có cơ hội nói về một real world case sử dụng curried function trong vài ngày tới.

20 Jul 2016

Scala: Pattern matching & PartialFunction

Scala cung cấp tính năng pattern matching (và được sử dụng rất nhiều), tương ứng với switch của Java. Nhưng syntax có khác đi một chút.


Trong Java chúng ta dùng switch như  bên dưới:
String month;
switch (myNumber) {
  case 1:  month = "thang 1";
  break;
  case 2: month = "thang 2";
  break;
  case 3:
  case 4:
    default: month = "xxxx";
}

return month;
General syntax của swicth trong Java có dạng switch (selector) { alternatives } (1).
Đối với switch của Java, khi dừng câu lệnh switch, chúng ta phải dùng break, nếu không, khi gặp pattern được match, switch sẽ "fall through" đến các case tiếp theo cho đến khi nào gặp break, rất dễ xảy ra lỗi nếu như chúng ta không để ý, và IDE cũng không warning trong trường hợp có return type hợp lệ.


Dùng scala, khi sử dụng pattern matching, syntax sẽ là selector match { alternatives }

Pattern matching của scala cũng sử dụng từ khoá case như Java, tiếp theo là pattern muốn match, và dấu => để tách biệt pattern và biểu thức dùng để xử lí khi pattern được match. match trong scala khác biệt so với Java:
1. đầu tiên do pattern matching của Scala không "fall through" đến các case matching khác, nên không cần dùng break
2. Mỗi một biểu thức alternative trong scala đều phải sinh ra giá trị, cho dù rơi vào default case 
3. Đối với Java, nếu input không rơi vào case nào (không được match) và không có case default, sẽ không có lỗi xảy ra, nhưng có thể sẽ sinh ra lỗi về sau. Đối với Scala, nếu sử dụng pattern matching, mỗi khi dùng match chúng ta buộc phải return giá trị, dù input không match bất cứ case nào đi nữa, nếu không sẽ sinh ra exception MatchError.

Với ví dụ trên, khi dùng với scala sẽ như sau:

val monthName: String = month match {
  case 1 => "thang 1"  case 2 => "thang 2"  case _ => "xxx"}

Pattern matching cuả scala có thể dùng với nhiều dạng pattern: wildcard, constant (như ví dụ trên, 1, 2 là constant, _ là wildcard), case class, type, tuple, sequence, constructor...

Do vậy chúng ta hoàn toàn có thể sử dụng các cách thức sau đối với pattern matching:

case 1 => "thang 1"
hay là đối với list
case _ :: y :: _ if y > 1 => y
Với type
case s: String => s.length
v.v    

Một vấn đề khi sử dụng pattern matching là chúng ta thường không kiểm soát được input, và compiler không có cách nào để thông báo khi chúng ta dùng logic sai, một ví dụ đối với if else thông thường trong scala:

def myFunc(seq : List[Int]): Int = {
  if (seq.length > 1) seq(2)
  else 0}



Khi sử dụng myFunc với input là List Int có length nhỏ hơn 1 hoặc lớn hơn 3 sẽ cho kết quả đúng, nhưng nếu như input là một List với length bằng 2 chương trình sẽ crash:

scala> def myFunc(seq : List[Int]): Int = {
  |     if (seq.length > 1) seq(2)
  |     else 0  |   }
myFunc: (seq: List[Int])Int

scala> myFunc(List(2, 3, 4))
res6: Int = 4
scala> myFunc(List(2, 4))
java.lang.IndexOutOfBoundsException: 2at scala.collection.LinearSeqOptimized$class.apply(LinearSeqOptimized.scala:65)
at scala.collection.immutable.List.apply(List.scala:84)
at .myFunc(<console>:12)  ... 32 elided

Tương tự nếu sử dụng pattern matching mà chúng ta không cover hết tất cả các case, sẽ gặp phải Runtime exception. 

scala> val second: List[Int] => Int = { case _ :: y :: _  if y > 1 => y }
second: List[Int] => Int = <function1>
scala> second(List(1, 2))res12: Int = 2
scala> second(List(1))scala.MatchError: List(1) 
(of class scala.collection.immutable.$colon$colon)at 
$anonfun$1.apply(<console>:11)  
at $anonfun$1.apply(<console>:11)    ... 32 elided


Để khắc phục lỗi này, scala cung cấp PartialFunction.
val second: PartialFunction[List[Int],Int] = {
  case _ :: y :: _  if y > 1 => y
}

Hàm trên khi scala compile sẽ được dịch ra tương tự như 

val second = new PartialFunction[List[Int], Int]  {
  def apply(xs: List[Int]) = xs match {
    case _ :: y :: _  if y > 1 => y
  }

  def isDefinedAt(xs: List[Int]) = xs match {
    case _ :: y :: _ => true    
    case _ => false  
  }
}


Như vậy Partial function cung cấp một method dùng để kiểm tra function matcher của chúng ta có làm việc được với input cụ thể nào đó không. Nếu như không kiểm tra mà cứ dùng như ví dụ ban đầu, chúng ta vẫn sẽ gặp Runtime exception, do vậy khi define function matcher với Partial Function, thì lúc sử dụng, chúng ta dùng method isDefinedAt để kiểm tra giá trị input trước:

scala> val second: PartialFunction[List[Int],Int] = {
    case _ :: y :: _  if y > 1 => y
   }
second: PartialFunction[List[Int],Int] = <function1>

scala>   val l = 1 :: 2 :: 3 :: Nil
l: List[Int] = List(1, 2, 3)

scala>

scala>   val a = if (second.isDefinedAt(l)) second(l) else 0
a: Int = 2
scala>

scala>   val l1 = 1 :: Nil
l1: List[Int] = List(1)

scala>

scala>   val b = if (second.isDefinedAt(l1)) second(l) else 0
b: Int = 0

Ứng dụng:

Scala cung cấp các method để làm việc trên scala standard collection như Seq, List, Set... Đối với các method như filter, map chấp nhận input là các Anonymous function với parameters phù hợp để sinh ra các collection mới theo tiêu chí đặt ra trong Anonymous function, ví dụ khi làm việc với một List[Int] đơn giản như bên dưới:

val l = 1 :: 2 :: 3 :: Nil

Có thể dùng map và filter như sau:

scala> l.map({ case x => x*2 })
res7: List[Int] = List(2, 4, 6)

scala> l.filter(_ > 1)
res8: List[Int] = List(2, 3)

Để ý cấu trúc map method bên trên, ta sử dụng một Anonymous function dùng pattern matching là bất kì input nào, do đó tất cả các case đều được tính đến. Nhưng nếu như có nhu cầu chỉ lấy ra một List các số Int lớn hơn 1 trong List ban đầu, khi dùng map sẽ gặp lỗi:

scala> l.map({ case x if x > 1 => x })
scala.MatchError: 1 (of class java.lang.Integer)
at $anonfun$1.apply$mcII$sp(<console>:13)  
at $anonfun$1.apply(<console>:13)    
at $anonfun$1.apply(<console>:13)      
at scala.collection.immutable.List.map
(List.scala:273)      
... 32 elided

Vì sự khác nhau giữa switch của Java và match của Scala như đã nói từ đầu bài, tất cả các case đều cần được tính đến. Phần matching chúng ta dùng Pattern guard (if x > 1) để lọc giá trị lớn hơn 1, nhưng chưa match giá trị bằng hoặc nhỏ hơn 1, do vậy sẽ gặp MatchError Exception.

Để giải quyết vấn đề này, có thể dùng collect method với Partial Function:
scala> val moreThanOne: PartialFunction[Int,Int] = { case x if x > 1 => x }
moreThanOne: PartialFunction[Int,Int] = <function1>
scala> l.collect(moreThanOne)
res12: List[Int] = List(2, 3)

Như vậy với Partial Function chúng ta có thể giải quyết bài toán này theo một cách cực kì đơn giản.

 (1) Programming in Scala 2nd Edition

26 Feb 2016

Code review

This's let's Encrypt, where people contribute their code to build a simple, free, great thing that most sysadmin, web developer, companies really want, free ssl certificate for all.

Look at how the review a small piece of code:

https://github.com/letsencrypt/letsencrypt/pull/2453#issuecomment-189229778

That's just so great, coding style, compatibility concern, test case, follow rfc and more.

5 Mar 2015

Something I have done these days

1. Symemcache pool using common pool 1.x: https://github.com/whatvn/Spymemcache-commonpool-1 
2. Symemcache pool using common pool 2.x: https://github.com/whatvn/Spymemcache-commonpool-2 
3. A http multiplexer in java: https://github.com/whatvn/HttpMultiplexer
4. A video encoder service which makes use of libav (from fffmpeg), gearman and libftp: https://github.com/whatvn/mp4encoder
5. An example nginx module to make nginx work together with thrift backend: https://github.com/whatvn/nginx_photo_thrift_module 
6. A modified version of nginx mp4 module to fix mp4 file automatically in order to start playback immediately: https://github.com/whatvn/ngx_http_enhance_mp4_module 
7. A ported version of firebase pushid in C (can be called a better/simpler uuid generator): https://github.com/whatvn/firebase-pushid 

You can find more details in github links. 


Disqus