Những điều bạn đã biết, và chưa biết về Variance và Functor trong scala
Scala
50
White

huydx viết ngày 29/05/2016

alt text

Hệ thống type (type system) của scala là một hệ thống khá toàn diện, cho phép chúng ta đánh dấu một kiểu dưới một trong 3 dạng: covariant, contravariant và invariant.
3 cách đánh dấu này cho phép chúng ta mô tả type một cách tốt hơn, trong bối cảnh chúng ta sử dụng type constructor để truyền một type vào một type context khác (như là List[Int] hoặc là Sequence[Float]).

Trong giới lập trình hàm, thì không chỉ có variant, contravariant và invariant trong type, mà còn có variant functor, contravariant functor và invariant functor, mà tôi sẽ nói cụ thể hơn dưới đây.

Đầu tiên , hãy tìm hiểu về covariant, contravariant và invariant.

Covariance

Một ví dụ hay được dùng nhất là List[+A], mà covariance ở đây thể hiện ở dấu + phía trước type parameter là A. Một type constructor sử dụng contravariant khi :

Nếu tồn tại một mối quan hệ kế thừa (subtyping) giữa type parameter, thì sẽ tổn tại mối quan hệ kế thừa (subtyping) giữa type constructor (mà ở trong ví dụ trên, type parameter là A, và type constructor là List)

Như vậy có thể hiểu đơn giản là, nếu A là con của B, thì List[A] cũng là con của List[B], có vẻ khá là hiển nhiên đúng không. Mối quan hệ này giúp chúng ta làm một việc giống như nguyên tắc liskov trong lập trình hướng đố tượng, tức là ở đâu có A thì cũng có thể thay thế được bằng B , và với covariant chúng ta có thể làm được một thứ còn hơn thế, đó là ở đâu có List[A] thì cũng có thể được thay thế bằng List[B].

Để hiểu thêm, dưới đây sẽ lướt qua một số type phổ biến có thể coi là covariant, cũng như không thể coi là covarant

Read

Read là một type khá phổ biến trong lập trình hàm, nó mô tả một kiểu mà có thể được "lấy một giá trị ra từ trong nó". Bạn có thể hiểu Read giống như một cái hộp vậy. Read có thể được mô tả như sau:

trait Read[+A] {
  def read(s: String): Option[A]
}

Từ định nghĩa trên chúng ta có thể thấy, hoàn toàn hợp lý khi Read là một kiểu dạng covariant, bởi nếu bạn có thể read được giá trị từ 1 type con (subtype), thì cũng có thể read được giá trị từ cha của chúng, chỉ bằng việc lược bỏ đi những thứ không cần thiết từ type con. Cụ thể hơn, nếu chúng ta có thể read được từ type Circle, thì chúng ta cũng có thể read được từ type Shape, chỉ cần bỏ qua đi những thứ không cần thiết từ Circle như bán kính đường kính...

Array

Ngược lại vơi Read, Array lại không thể là một kiểu có thể giả sử là có tinh chất covariant được. (Lưu ý lại là Array ở đây khác với List, bởi Array trong scala là mutable, còn List lại là immutable.
Để chứng minh Array không thể là covariant, chúng ta thử giả sử ngược lại, là nếu Array là covariant thì sao. Nếu vậy thì Array[Shape] có thể thay thế cho Array[Circle] được tại bất kì đâu. Nếu vậy hãy xem đoạn code sau

val circles: Array[Circle] = Array.fill(10)(Circle(..))
val shapes: Array[Shape] = circles //sẽ hoạt động nếu Array là covariant
shapes(0) = Square(..) // Square is a subtype of Shape

Khi chạy thử bạn sẽ thấy lỗi compile

covariant.scala:7: error: type mismatch;
 found   : Array[this.Circle]
 required: Array[this.Shape]

Kiểu read-only và covariance

Về cơ bản, một type có thể được coi như là covariant nếu nó là read-only, tức là bạn chỉ có thể có những method để "đọc" giá trị từ nó ra, chứ không có method nào để biến đổi giá trị bên trong nó. Điều này có thể được chứng minh bằng một logic khá đơn giản là: nếu bạn có khả năng đọc một kiểu cụ thể nào đó thì chúng ta co thể đọc một kiểu generic hơn, bằng việc bỏ đi những thông tin không cần thiết. Quay lại ví dụ ở trên, thì List có thể được coi là covariant vì nó là immutable, còn Array chúng ta có thể thay đổi giá trị nên không phải là covariant.

Functor

Như chúng ta vừa thấy, covariance là khi nếu A là con (subtype) của B, thì F[A] là con (subtype) của F[B]. Nói một cách khác, nếu A có thể "biên thành" B, thì F[A] có thể biến thành F[B]. Hành vi này chúng ta có thể thấy trong Functor:

trait Functor[F[_]] {
  def map[A, B](f: A => B): F[A] => F[B]
}

Chúng ta có thể viết lại định nghĩa trên khác một chút bằng cách thay đổi thứ tự hàm

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

Chúng ta có thể implement Functor cho List và Read như sau

val listFunctor: Functor[List] =
  new Functor[List] {
    def map[A, B](fa: List[A])(f: A => B): List[B] = fa match {
      case Nil => Nil
      case a :: as => f(a) :: map(as)(f)
    }
  }

val readFunctor: Functor[Read] =
  new Functor[Read] {
    def map[A, B](fa: Read[A])(f: A => B): Read[B] =
      new Read[B] {
        def read(s: String): Option[B] =
          fa.read(s) match {
            case None => None
            case Some(a) => Some(f(a))
          }
      }
  }

Sử dụng Functor chúng ta có thể implement một xử lý khá thú vị gọi là upcast

val circles: List[Circle] = List(Circle(..), Circle(..))
val shapes: List[Shape] = listFunctor.map(circles)(circle => circle: Shape) // upcast

val parseCircle: Read[Circle] = ...
val parseShape: Read[Shape] = readFunctor.map(parseCircle)(circle => circle: Shape) // upcast

hay là có thể viết lại một cách generic hơn:

def upcast[F[_], A, B <: A](functor: Functor[F], fb: F[B]): F[A] =
  functor.map(fb)(b => b: A)

Bạn có thể thấy hàm upcast này có hành vi y hệt như covariance: tức là nếu có một type cha A (supertype) , như ở ví dụ trên là Shape, và type con B (subtype) , hay như trong ví dụ là Circle, thì chúng ta có thể cast một cách "an toàn" từ F[B] sang F[A] ở bất kì đâu. Hay nói một cách khác, ở đâu cần F[A] thì chúng ta có thể đưa F[B] thay thế. Chính vì thế, Functor có thể gọi một cách khác là Covariant Functor

Contravariance

Contravariance, một cách đơn giản là đảo ngược định nghĩa của covariance. Theo như ví dụ ở trên , thì F[Shape] có thể coi là con của F[Circle]. Việc này nghe khá kì lạ đúng không, tức là A là con của B, thì F[B] sẽ là con của F[A] =.=. Ngay từ đầu tôi cũng không hiểu khi nào thì Contravariance sẽ có ích??
Cụ thể hơn, nếu chúng ta có List[Shape] chúng ta sẽ không thể coi một cách an toàn rằng đó là List[Circle], làm vậy sẽ tạo ra warning khi compile về việc downcasting, do đó List không phải là một contravariance.

Vậy khi nào thì contravariance là có ích? Chúng ta sẽ đi qua một số type là contravariance

Show

Có một rule có thể rút ra khá dễ dàng là: những kiểu read-only sẽ không bao giờ là contravariant được. Vậy nếu suy nghĩ một cách logic, nếu contravariance là đảo ngược của variance, vậy nếu đảo ngược kiểu read-only thành kiểu mà chúng ta có thể viết giá trị vào trong đó, thì chúng ta sẽ có contravariance type? Thay vì read giá trị từ trong String ra, chúng ta cần một kiểu có thể viết giá trị vào trong String, và đó chính là Show. (Show chính là kiểu mô tả cho thuộc tính to_string giống như trong các ngôn ngữ hiện đại)

trait Show[-A] {
  def show(a: A): String
}

Show chính là nửa ngược lại của kiểu Read, thay vì từ String -> A, chúng ta đi từ phía ngược lại là A -> String. Như vậy nếu chúng ta được hỏi để cung cấp một cách show Circle thông qua implement type Show[Circle] thì chúng ta có thể cung cấp một cách để Show[Shape] thay thế. Việc này sẽ cho một kết quả generic hơn, nhưng vẫn chấp nhận được, bởi những thuộc tính của Shape vẫn là bản chất của Circle.

Một cách tổng quát, chúng ta có thể show một type con nếu chúng ta biết cách show của type cha tương ứng, bằng cách vứt đi những thuộc tính không tổng quát.

Xem lại Array

Array, rất tiếc cũng không thể là một contravariant. Nếu có thì chúng ta có thể làm thao tác như sau:

val shapes: Array[Shape] = Array.fill(10)(Shape(..), Shape(..))
val circles: Array[Circle] = shapes // Works only if Array is contravariant
val circle: Circle = circles(0)

Biến circle, có thể được đọc ra từ array circles dưới kiểu Circle tại compile time, tuy nhiên tại runtime thì trong circles có thể tồn tại những phần tử không đúng kiểu, ví dụ như Regtangle, và khi đó chương trình sẽ bị crash.

Contravariant Functor

Functor vốn dĩ có tính chất covariant một cách tự nhiên, vậy để thêm tính chất contravariant vào cho Functor, chúng ta phải implement thêm một số hành vi cho nó. Functor này phải đảm bảo tính chất: nếu type A có thể được thay thế vào type B , thì F[B] có thể thay thế được cho F[A].

trait Contravariant[F[_]] {
  // Alternative encoding:
  // def contramap[A, B](f: B => A): F[A] => F[B]

  // More typical encoding
  def contramap[A, B](fa: F[A])(f: B => A): F[B]
}

Chúng ta có thể implement Show Functor như sau

val showContravariant: Contravariant[Show] =
  new Contravariant[Show] {
    def contramap[A, B](fa: Show[A])(f: B => A): Show[B] =
      new Show[B] {
        def show(b: B): String = {
          val a = f(b)
          fa.show(toShow)
        }
      }
  }

Chúng ta cũng có thể implement hàm upcast trên Contravariant Functor

def contraUpcast[F[_], A, B >: A](contra: Contravariant[F], fb: F[B]): F[A] =
  contra.contramap(fb)((a: A) => a: B)

Function Variance

Chúng ta đã quan sát được là những type read-only sẽ là covariance, và type write-only sẽ là contravariance. Quan sát này cũng áp dụng cả khi định nghĩa Function.

Parameters

Giả sử chúng ta có hàm dưới đây

// Right now we only care about the input
def squiggle(circle: Circle): Unit = ???

// or
val squiggle: Circle => Unit = ???

Lúc đó function này sẽ có type Circle => Unit, vậy type con (subtype) của Circle => Unit là gì?? Lưu ý là chúng ta không quan tâm đến type của thứ sẽ được pass vào function, mà chúng ta quan tâm đến type của function, mà ở đây là Circle => Unit. Vậy chúng ta hãy thử đoán xem nên input thế nào sẽ thu được subtype như ý nhé.

Chắc sẽ có bạn nghĩ bằng , thử thay Circle bằng một subtype của nó, ví dụ là Dot (Circle với bán kinh là 0) xem sao.

val squiggle: Circle => Unit =
  (d: Dot) => d.someDotSpecificMethod()

Có vẻ thử nghiệm này không đúng, bởi việc gọi someDotSpecificMethod sẽ đem đến một vài hành vi không lường trước được, do đó thay thế Circle bởi subtype của nó có vẻ là một giả thuyết không an toàn.

Vậy thì chúng ta làm ngược lại, nếu thay thế Circle bằng một supertype của nó, ví dụ là Shape

val squiggle: Circle => Unit =
  (s: Shape) => s.shapeshift()

Trong có vẻ an toàn hơn đúng không? Nhìn từ ngoài chúng ta có một hàm nhận vào Circle và làm gì với nó, còn ở trong chúng ta có thể upcast parameter đó lên Shape rồi sau đó làm gì với nó sau. Nếu viết lại ví dụ trên dưới một phương thức functional hơn, chúng ta sẽ có

type Input[A] = A => Unit
val inputSubtype: Input[Shape] = (s: Shape) => s.shapeshift()
val input: Input[Circle] = inputSubtype

hay chúng ta có thể nói là Input[Shape] là con của Input[Circle], khi mà Circle là con của Shape, hay chinh là tính chất contravariant. Chính vì tính chất đặc biệt đấy của function mà trong ví dụ dưới đây, khi chúng ta cố tình nhét một biến covariant vào vị trí parameter của một function, thì sẽ dẫn đến compile error

scala> trait Foo[+A] { def foo(a: A): Int = 42 }
<console>:15: error: covariant type A occurs in contravariant position in type A of value a
       trait Foo[+A] { def foo(a: A): Int = 42 }
                               ^

Chính vì thế để vượt qua tình thế trên, vẫn muốn sử dụng covariant type cho parameter, chúng ta phải trick compiler như sau, thay vì dùng trực tiếp A thì sẽ dùng một supertype của A.

scala> trait Foo[+A] { def foo[B >: A](a: B): Int = 42 }
defined trait Foo

Return

Ở ví dụ trên chúng ta đã thử thí nghiệm với variance thông qua Input tức là đầu vào của function, ở phần này chúng ta sẽ thử thí nghiệm với Return, hay là đầu ra của function.
Giả sử chúng ta có hàm như sau:

val squaggle: Unit => Shape = ???

Ở ví dụ trên, sử dụng supertype có vẻ hoạt động với input, chúng ta thử làm tương tự với output xem sao, với việc thay thế kêt quả trả về là một Object

val squaggle: Unit => Shape =
  (_: Unit) => somethingThatReturnsObject()

Hãy thử nghĩ logic một chút: hàm cần chúng ta trả về một Shape, nhưng chúng ta lại trả về Object, thứu mà không phải lúc nào cũng là một valid Shape, và khi đó có thể dẫn đến một số hành vi không mong muốn, hay nói cách khác là nhỡ đâu thứ trả về không có method mà chúng ta mong đợi từ Shape?
Do đo sử dụng supertype với kết quả trả về của function chăc chắn là không hoạt động, vậy chúng ta thử với subtype xem sao:

val squaggle: Unit => Shape =
  (_: Unit) => Circle(..)

Có vẻ hợp lý hơn rồi đấy nhỉ. Chúng ta có thể sử dụng Circle thay cho Shape bằng cách lược bỏ đi các tính chất thừa thãi của Circle.

Từ đó có thể khẳng định: Output của một function có tính chất covariant.

Làm ví dụ tương tự ở trên khi defined trait, chúng ta cũng phải trick compiler khi muốn sử dụng contravariant với vị trí là type trả về

scala> trait Bar[-A] { def bar(): A = ??? }
<console>:15: error: contravariant type A occurs in covariant position in type ()A of method bar
       trait Bar[-A] { def bar(): A = ??? }
                           ^

scala> trait Bar[-A] { def bar[B <: A](): B = ??? }
defined trait Bar

Tổng hợp lại về function

Vậy có thể tóm gọn lại là: input của function là contravariant, và ouput là covariant. Từ đó chúng ta có một kết luận khá thú vị sau: Một function có kiểu là Shape => Circle sẽ có thể thay thế cho một function có kiểu là Circle => Shape ở bất kì đâu :smile:. Chỉ cần nhớ cái kết luận này là bạn đã nhớ về tính chất variant của function rồi :P.

Invariance

Invariant là một type mà không có annotation + lẫn -, tức là type nào không phải contravairant, không phải covariant, thì sẽ là invariant. Như vậy nếu bạn định nghĩa một type F[_] thì F[Circle] sẽ không có quan hệ gì với F[Shape], và bạn sẽ phải cung cấp một cách biến đổi giữa F[Circle]F[Shape], một cách explicit.

Lại quay lại Array

Do như ở trên chúng ta đã chứng minh Array không phải covariant, cũng không phải contravariant, vậy thì nó là invariant rồi. Do đó kể cả 2 kiểu AB có quan hệ họ hàng với nhau, khi put nó vào context của Array thì cũng ta vẫn phải convert thủ công Array[A] thành Array[B] và ngược lại.

Invariant Functor

Tương tự trên, chúng ta cũng có thể implement một Invariant functor:

trait Invariant[F[_]] {
  def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B]
}

Hãy sử dụng Array để demo

class Array[A] {
  private var repr = ListBuffer.empty[A]

  def read(i: Int): A =
    repr(i)
  def write(i: Int, a: A): Unit =
    repr(i) = a
}

Khi đó invariant cho Array sẽ được định nghĩa như sau

val arrayInvariant: Invariant[Array] =
  new Invariant[Array] {
    def imap[A, B](fa: Array[A])(f: A => B)(g: B => A): Array[B] =
      new Array[B] {
        // Convert read A to B before returning – covariance
        override def read(i: Int): B =
          f(fa.read(i))

        // Convert B to A before writing – contravariance
        override def write(i: Int, b: B): Unit =
          fa.write(i, g(a))
      }
  }

Serialization

Một ví dụ thú vị của invariant type chính là khi chúng ta kết hợp cả Read lẫn Show lại với nhau

trait Serializer[A] extends Read[A] with Show[A] {
  def read(s: String): Option[A]
  def show(a: A): String
}

Do có tinh chất của cả covariant lẫn contravariant nên nó không thể là cả 2 (rất thú vị đúng không). Khi đó chúng ta có thể implement invariant cho Serializer như sau:

val serializerInvariant: Invariant[Serializer] =
  new Invariant[Serializer] {
    def imap[A, B](fa: Serializer[A])(f: A => B)(g: B => A): Serializer[B] =
      new Serializer[B] {
        def read(s: String): Option[B] = fa.read(s).map(f)
        def show(b: B): String = fa.show(g(b))
      }
  }

Tông kết lại về invariant functor

Chúng ta có thể thấy Invariant là một khái niệm tổng quát hơn cả FunctorContravariant, do invariant đòi hỏi functions phải đi theo cả 2 hướng, trong khi FunctorContravariant chỉ yêu cầu 1 hướng. Do đó chúng ta có thể biến Invariant thành Functor hoặc Contravariant bằng việc bỏ đi 1 hướng:

trait Functor[F[_]] extends Invariant[F] {
  def map[A, B](fa: F[A])(f: A => B): F[B]

  def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B] =
    map(fa)(f)
}

trait Contravariant[F[_]] extends Invariant[F] {
  def contramap[A, B](fa: F[A])(f: B => A): F[B]

  def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B] =
    contramap(fa)(g)
}

Phần bonus

Qua bài viết chúng ta có thể thấy scala support 3 kiểu

1. invariance: A = B → F[A] = F[B]
2. covariance: A <: B → F[A] <: F[B]
3. contravariance: A >: B → F[A] <: F[B]

3 Kiểu trên có thể được biểu diễn dưới dạng graph sau:

   invariance
     ↑   ↑
    /      \
   -        +

Các bạn có thể thấy graph trên thiếu một cái gì đó, đó chính là một kiểu kêt hợp cả +-.
Rất tiếc scala không support kiểu nào có thuộc tính như trên. Trong thế giới lập trình hàm, có tồn tại một kiểu có thuộc tính như trên, gọi là Phantom type.
Phantom type rất đơn giản, một kiểu mà F[A]F[B] sẽ không phụ thuộc vào mối quan hệ giữa AB. Tuy nhiên bạn đừng nhầm với invariance, bởi invariance vẫn phụ thuộc vào mối quan hệ = giữa AB.

Để implement phantom type, chúng ta có thể implement như sau:

trait Phantom[F[_]] {
  def pmap[A, B](fa: F[A]): F[B]
}

trait Phantom[F[_]] extends Functor[F] with Contravariant[F] {
  def pmap[A, B](fa: F[A]): F[B]

  def map[A, B](fa: F[A])(f: A => B): F[B] = pmap(fa)

  def contramap[A, B](fa: F[A])(f: B => A): F[B] = pmap(fa)
}

Phantom Type có sức mạnh là , với F[A], chúng ta cso thể biến nó thành F[B] với bất kì type AB. Qua đó chúng ta có thể hoàn thành graph trên

   invariance
     ↑   ↑
    /      \
   -        +
   ↑        ↑
    \      /
    phantom

Bài viết được tham khảo từ http://typelevel.org/blog/2016/02/04/variance-and-functors.html

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

huydx

116 bài viết.
960 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
153 14
Introduction (Link) là một cuộc thi ở Nhật, và cũng chỉ có riêng ở Nhật. Đây là một cuộc thi khá đặc trưng bởi sự thú vị của cách thi của nó, những...
huydx viết gần 2 năm trước
153 14
White
126 15
Happy programmer là gì nhỉ, chắc ai đọc xong title của bài post này cũng không hiểu ý mình định nói đến là gì :D. Đầu tiên với cá nhân mình thì hap...
huydx viết hơn 3 năm trước
126 15
White
98 10
(Ảnh) Mở đầu Chắc nhiều bạn đã nghe đến khái niệm oauth. Về cơ bản thì oauth là một phương thức chứng thực, mà nhờ đó một web service hay một ap...
huydx viết 3 năm trước
98 10
Bài viết liên quan
White
10 0
Kí tự Regex cơ bản Về cơ bản thì các sử lý matching của scala.util.matching.Regex sẽ được "phó thác" (delegate) cho java Regex. Bạn có thể tạo một ...
huydx viết 3 năm trước
10 0
White
7 1
Trong scala kí tự _ được dùng với khá nhiều mục đích .. không liên quan đến nhau. Tạm note lại cái đã khi nào có time sẽ quay lại viết cẩn thận sa...
huydx viết 3 năm trước
7 1
White
0 0
(Bài viết hơi khó hiểu, dành cho bạn nào có hứng thú với type programming trong scala với các thư viện như shapeless chẳng hạn) Thông thường với m...
huydx viết hơn 2 năm trước
0 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
116 bài viết.
960 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!