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.

Disqus