Skip to content

Latest commit

 

History

History
82 lines (57 loc) · 6.65 KB

type-level-logic-using-implcits.md

File metadata and controls

82 lines (57 loc) · 6.65 KB

Логика на ниво типова система чрез implicit-и

Инфиксен запис на типове

Да разгледаме:

def quickSort(xs: List[Int]): List[Int] = xs match {
  case Nil => Nil
  case x :: rest =>
    val (smaller, larger) = rest.partition(_ < x)
    quickSort(smaller) ::: (x :: quickSort(larger))
}

Знаем, че при x :: quickSort(larger) символът :: е метод на List. При case x :: rest символът :: изглежда като специален синтаксис от Scala. Но това не е така, :: всъщност е имлементиран в библиотеката на Scala и всеки би могъл да си добави подобна операция при pattern matching. Начинът, по който функционира, е следният. List в Scala e дефиниран по следния начин:

trait List[+A]
case class ::[+A](head: A, next: List[A]) extends List[A]
case object Nil extends List[Nothing]

Забележете, че Cons класът се казва :: , като той е case class и това значи, че има unapply метод. Това значи, че в Pattern Matching можем да пишем:

def quickSort(xs: List[Int]): List[Int] = xs match {
  case Nil => Nil
  case ::(x, rest) =>
    val (smaller, larger) = rest.partition(_ < x)
    quickSort(smaller) ::: (x :: quickSort(larger))
}

Точно както при методите обаче, като всичко друго с двама участници, Scala ни позволява да напишем горното и инфиксно, с което получаваме познатия ни синтаксис: x :: rest.

Реализация на flatten, използвайки логика на нивото на типовата система

Така, нека да видим как можем да си имплементираме операция flatten върху вложени типове. Да разгледаме конкретен случай, примерно List. Искаме flatten да можем да го извикваме само върху List[List[A]], но не и върху List[A], ако A не е списък. Тост при:

class List[A]

flatten да може да се извиква само ако A е List. Това е ограничение, което искаме да поставим само за един метод от List, но не и за другите. Та въпросът е как да го изразим в типовата система. Нека да си въведем тип =:= по следния начин:

sealed trait =:=[From, To] extends (From => To)

implicit def eqInstance[A] = new =:=[A, A] {
  def apply(a: A): A = a
}

Забележете, че лимитираме всички подтипове на =:= само до един, при който From е равно на To. Допълнително реализацията наследява функция (From => To), след малко ще разберем защо.

така може да си напишем следното (ще разгледаме малко по-просто тип Box):

case class Box[A](value: A) {
  def flatten[B](implicit evidence: =:=[A, Box[B]]): Box[B] = ???
}

Да види какво получихме. Нека да имаме val box = Box(Box(42)). Какво става, ако опитаме да извикаме box.flatten?

За целта трябва да му подадем имплицитна инстанция. Scala знае, че типа на A в този случай е Box[Int], което значи, че ще търси такава имплицитна инстанция на =:=, при която първият параметър е Box[Int], а вторият е Box[B]. Scala всъщност успява да намери такава, в лицето на eqInstance, но само и единствено ако Box[Int] е равно на Box[B], тоест ако B е равно на Int. Така Scala заключва, че B е Int и извиква метода flatten с eqInstance[Box[Int]].

Какво ще стане, ако опитаме да извикваме Box(42).flatten? Scala ще опита да намери инстанция на =:=, при която първият параметър е Int (тъй като A е Int), а вторият е Box[B]. Тук обаче Scala не намира никаква такава инстанция – невъзможно е Int да се приравни към Box[B] каквото и B да имаме. Та при този случай не успяваме да извикваме flatten и получаваме компилационна грешка.

Последната стъпка е да забележим, че =:= е тип с два типови параметъра, което значи, че можем да го запием инфиксно:

case class Box[A](value: A) {
  def flatten[B](implicit evidence: A =:= Box[B]): Box[B] = evidence(value)
}

Тук се възползваме и от това, че =:= е функция от From към To за да конвертираме стойността от тип A към стойност от тип Box[B], без да се налага да използваме неща като isInstanceOf. Така получаваме и пълно type safety. Обикновено се кръщава evidence или ev като сведения, че A == Box[B].

По напълно аналогичен начин работи и за List. Този инфиксен запис значи, че в Scala можем да си измисляме всякакви типове, които биха ни били полезни. Например в стандартната библиотека на Scala освен A =:= B, което значи, че A е равно на B, имаме и A <:< B, което значи "A е подтип на B" (всъщност това и се използва в List, тъй като List е ковариантно). Някои Scala библиотеки пък да си дефинират неща като F ~> G като тип с определен смисъл. Така Scala успява да е scalable и на ниво синтаксис за дефиниране на типпове.