Implicit scala что это
Перейти к содержимому

Implicit scala что это

  • автор:

Implicit scala что это

В этом уроке вы узнаете:

  • Видимое ограничение («Классы-типы»)
  • Типы высшего порядка и специальный полиморфизм
  • F-ограниченный полиморфизм / рекурсивные типы
  • Структурные типы
  • Абстрактные типы членов
  • Тип чисток и манифесты
  • Пример: Finagle

Видимое ограничение («Классы-типы»)

Неявные функции в Scala позволяют использовать функции по требованию, когда это может помочь при выводе типа, например:

scala> implicit def strToInt(x: String) = x.toInt strToInt: (x: String)Int scala> "123" res0: java.lang.String = 123 scala> val y: Int = "123" y: Int = 123 scala> math.max("123", 111) res1: Int = 123

Видимое ограничение, подобно ограничению типа, требует функцию, которая существует для данного типа, например:

scala> class Container[A defined class Container

Это говорит, что A должен быть «видим» подобно Int. Давайте попробуем.

scala> (new Container[String]).addIt("123") res11: Int = 246 scala> (new Container[Int]).addIt(123) res12: Int = 246 scala> (new Container[Float]).addIt(123.2F) :8: error: could not find implicit value for evidence parameter of type (Float) => Int (new Container[Float]).addIt(123.2) ^

Другие ограничения типов

Методы могут запросить конкретные «доказательства» для типа, а именно:

A =:= B A должен быть равен B
A

A должен быть подтипом B
A

A должен выглядеть как B
scala> class Container[A](value: A) < def addIt(implicit evidence: A =:= Int) = 123 + value >defined class Container scala> (new Container(123)).addIt res11: Int = 246 scala> (new Container("123")).addIt :10: error: could not find implicit value for parameter evidence: =:=[java.lang.String,Int]

Кроме того, учитывая наше предыдущее неявное значение, мы можем ослабить ограничение для видимости:

scala> class Container[A](value: A) < def addIt(implicit evidence: A defined class Container scala> (new Container("123")).addIt res15: Int = 246
Обобщенное программирование с помощью видов

В стандартной библиотеке Scala, виды в основном используются для реализации обобщенных функций коллекций. Например, функция «min» (Seq[]), использует эту технику:

def min[B >: A](implicit cmp: Ordering[B]): A = < if (isEmpty) throw new UnsupportedOperationException("empty.min") reduceLeft((x, y) =>if (cmp.lteq(x, y)) x else y) >

Основными преимуществами этого являются:

  • Элементам коллекции не требуется реализовывать Ordered, хотя Ordered по-прежнему использует статическую проверку типов.
  • Вы можете определить свой собственный порядок сортировки без необходимости использовать дополнительную библиотеку:
scala> List(1,2,3,4).min res0: Int = 1 scala> List(1,2,3,4).min(new Ordering[Int] < def compare(a: Int, b: Int) = b compare a >) res3: Int = 4

Небольшое замечание, есть виды в стандартной библиотеке, которые переводят Ordered в Ordering (и наоборот).

trait LowPriorityOrderingImplicits < implicit def ordered[A >
Ограничения контекста и implicitly[]

В Scala 2.8 введена сокращенная форма для передачи и для доступа с использованием неявных аргументов.

scala> def foo[A](implicit x: Ordered[A]) <> foo: [A](implicit x: Ordered[A])Unit scala> def foo[A : Ordered] <> foo: [A](implicit evidence$1: Ordered[A])Unit

Неявные значения могут быть доступны через implicitly

scala> implicitly[Ordering[Int]] res37: Ordering[Int] = scala.math.Ordering$Int$@3a9291cf

В совокупности это часто приводит к меньшему количеству кода, особенно при передаче с использованием видов.

Типы высшего порядка и специальный полиморфизм

Scala может абстрагировать типы «высшего порядка». Это похоже на каррирование функции. Например, в то время как «унарные типы» имеют конструкторы вроде этого:

List[A]

То есть мы должны удовлетворять определенному «уровню» типовых переменных с целью получения конкретных типов (подобно тому, как uncurried функция должна применяться только к одному списку аргументов, при вызове), типам высшего порядка требуется больше:

scala> trait Container[M[_]] < def put[A](x: A): M[A]; def get[A](m: M[A]): A >scala> val container = new Container[List] < def put[A](x: A) = List(x); def get[A](m: List[A]) = m.head >container: java.lang.Object with Container[List] = $anon$1@7c8e3f75 scala> container.put("hey") res24: List[java.lang.String] = List(hey) scala> container.put(123) res25: List[Int] = List(123)

Заметьте, что Container является полиморфным в параметрическом типе («тип контейнер»).

Если мы объединим использование контейнеров с неявными выражениями, мы получим «специальный» полиморфизм: возможность писать обобщенные контейнеры поверх контейнеров.

scala> trait Container[M[_]] < def put[A](x: A): M[A]; def get[A](m: M[A]): A >scala> implicit val listContainer = new Container[List] < def put[A](x: A) = List(x); def get[A](m: List[A]) = m.head >scala> implicit val optionContainer = new Container[Some] < def put[A](x: A) = Some(x); def get[A](m: Some[A]) = m.get >scala> def tupleize[M[_]: Container, A, B](fst: M[A], snd: M[B]) = < | val c = implicitly[Container[M]] | c.put(c.get(fst), c.get(snd)) | >tupleize: [M[_],A,B](fst: M[A],snd: M[B])(implicit evidence$1: Container[M])M[(A, B)] scala> tupleize(Some(1), Some(2)) res33: Some[(Int, Int)] = Some((1,2)) scala> tupleize(List(1), List(2)) res34: List[(Int, Int)] = List((1,2))

F-ограниченный полиморфизм

Часто необходим доступ к конкретному подклассу в (обобщенном) трейте. Например, представьте себе некоторый трейт, который является обобщенным, но может быть сравним с конкретным подклассом данного трейта.

trait Container extends Ordered[Container]

Тем не менее, сейчас требуется сравнение

def compare(that: Container): Int

И поэтому мы не можем получить доступ к конкретному подтипу, например:

class MyContainer extends Container

код не скомпилируется, так как мы определяем Ordered для Container, а не конкретный подтип.

Чтобы это согласовать, мы используем F-ограниченный полиморфизм.

trait Container[A 

Странный тип! Но заметьте, как Ordered параметризован с помощью A, который сам по себе является Container[A]

class MyContainer extends Container[MyContainer]

Они сейчас упорядочены:

scala> List(new MyContainer, new MyContainer, new MyContainer) res3: List[MyContainer] = List(MyContainer@30f02a6d, MyContainer@67717334, MyContainer@49428ffa) scala> List(new MyContainer, new MyContainer, new MyContainer).min res4: MyContainer = MyContainer@33dfeb30

Учитывая, что все они являются подтипами Container[_], мы можем определить другой подкласс и создать смешанный список Container[_]:

scala> class YourContainer extends Container[YourContainer] < def compare(that: YourContainer) = 0 >defined class YourContainer scala> List(new MyContainer, new MyContainer, new MyContainer, new YourContainer) res2: List[Container[_ >: YourContainer with MyContainer : YourContainer with MyContainer 

Обратите внимание, как результирующий тип в настоящее время ограничен снизу YourContainer с MyContainer. Это работа системы вывода типов. Интересно, что этот тип не имеет дополнительного смысла, он только обеспечивает логическую нижнюю границу для списка. Что произойдет, если мы попытаемся использовать Ordered сейчас?

(new MyContainer, new MyContainer, new MyContainer, new YourContainer).min :9: error: could not find implicit value for parameter cmp: Ordering[Container[_ >: YourContainer with MyContainer : YourContainer with MyContainer 

Ordered[] не существует для единого типа. Это слишком плохо.

Структурные типы

Scala имеет поддержку структурных типов — тип выражается интерфейсом structure вместо конкретного типа.

scala> def foo(x: < def get: Int >) = 123 + x.get foo: (x: AnyRef)Int scala> foo(new < def get = 10 >) res0: Int = 133

Это может быть полезно во многих ситуациях, но реализация использует отражения, так что обращайте внимание на производительность.

Абстрактные типы членов

В трейте, вы можете оставить тип членов абстрактным.

scala> trait Foo < type A; val x: A; def getX: A = x >defined trait Foo scala> (new Foo < type A = Int; val x = 123 >).getX res3: Int = 123 scala> (new Foo < type A = String; val x = "hey" >).getX res4: java.lang.String = hey

Часто это полезный трюк, когда делается внедрение зависимостей, например.

Вы можете обратиться к абстрактному типу переменной, используя хеш-оператор:

scala> trait Foo[M[_]] < type t[A] = M[A] >defined trait Foo scala> val x: Foo[List]#t[Int] = List(1) x: List[Int] = List(1)

Тип очистки и манифесты

Как вы знаете, информация о типе теряется во время компиляции благодаря очистке. Одна из особенностей Scala — это Манифесты, которые позволяют выборочно восстановить информацию о типе. Манифесты предоставляются в качестве неявного значения, которое генерируется компилятором по мере необходимости.

scala> class MakeFoo[A](implicit manifest: Manifest[A]) < def make: A = manifest.erasure.newInstance.asInstanceOf[A] >scala> (new MakeFoo[String]).make res10: String =

Пример: Finagle

trait Service[-Req, +Rep] extends (Req => Future[Rep]) trait Filter[-ReqIn, +RepOut, +ReqOut, -RepIn] extends ((ReqIn, Service[ReqOut, RepIn]) => Future[RepOut]) < def andThen[Req2, Rep2](next: Filter[ReqOut, RepIn, Req2, Rep2]) = new Filter[ReqIn, RepOut, Req2, Rep2] < def apply(request: ReqIn, service: Service[Req2, Rep2]) = < Filter.this.apply(request, new Service[ReqOut, RepIn] < def apply(request: ReqOut): Future[RepIn] = next(request, service) override def release() = service.release() override def isAvailable = service.isAvailable >) > > def andThen(service: Service[ReqOut, RepIn]) = new Service[ReqIn, RepOut] < private[this] val refcounted = new RefcountedService(service) def apply(request: ReqIn) = Filter.this.apply(request, refcounted) override def release() = refcounted.release() override def isAvailable = refcounted.isAvailable >>

Можно определить запросы с помощью filter.

trait RequestWithCredentials extends Request < def credentials: Credentials >class CredentialsFilter(credentialsParser: CredentialsParser) extends Filter[Request, Response, RequestWithCredentials, Response] < def apply(request: Request, service: Service[RequestWithCredentials, Response]): Future[Response] = < val requestWithCredentials = new RequestWrapper with RequestWithCredentials < val underlying = request val credentials = credentialsParser(request) getOrElse NullCredentials >service(requestWithCredentials) > >

Обратите внимание, как основной сервис требует определения запроса, и что это проверяется статически. Фильтры можно рассматривать как преобразователи.

Множество фильтров могут быть объединены вместе:

val upFilter = logTransaction andThen handleExceptions andThen extractCredentials andThen homeUser andThen authenticate andThen route

Пишите безопасный код!

Built at @twitter by @stevej, @marius, and @lahosken with much help from @evanm, @sprsquish, @kevino, @zuercher, @timtrueman, @wickman, @mccv and @garciparedes; Russian translation by appigram; Chinese simple translation by jasonqu; Korean translation by enshahar;

Неявные (implicit) параметры и преобразования в Scala

Пробежавшись по предыдущим статьям на Хабре, тыц и тыц так и не удалось в быстром режиме понять, что делает неявность (implicit) в Scala. Попробуем разобраться вместе.

Итак, implicit в Scala позволяют избежать вызывания методов или явных ссылок на переменные, и взамен этого позволяют компилятору самому найти нужные неявные данные.

Например, мы могли бы написать функцию для преобразования из Float в Int(FloatToInt) и, вместо того, чтобы вызвать эту функцию явно, компилятор бы сделал это вместо нас неявно:

def double(value: Int) = value * 2 implicit def FloatToInt(value: Float):Int = value.toInt println(double(2.5F)) 

Запутанно? Давайте обо всём по порядку.

Итак, сегодня мы рассмотрим две категории implicit, а именно:

  • Неявные параметры (implicit parameters, values). Они являются автоматически переданными компилятором значениями, объявленными через implicit.
  • Неявное преобразование (implicit conversion). При несовпадении типа ожидаемого параметра с входящим параметром компилятор ищет любой метод в области видимости, отмеченный implicit и с нужными в данной ситуации ожидаемым параметром и входящим параметром и автоматически его передаёт.
Неявный параметр

Неявный параметр — это параметр функции, которому предшествует ключевое слово implicit. Оно значит, что, если не передано никакого значения при вызове функции, то компилятор собственноручно будет искать неявный параметр и передаст его за нас.

Например, такая функция, принимающая на вход неявный параметр value и удваивающая его:

def double(implicit value: Int) = value * 2 

Без неявного параметра упадёт с ошибкой:

def double(implicit value: Int) = value * 2 println(double) // error: could not find implicit value for parameter value

С переданным явно параметром сработает:

def double(implicit value: Int) = value * 2 println(double(3)) // 6

С неявным параметром это будет выглядеть так:

def double(implicit value: Int) = value * 2 implicit val multiplier = 2 println(double) // 4

Но нужно быть аккуратным:

def double(implicit value: Int) = value * 2 implicit val multiplier = 2 implicit val multiplier2 = 1 println(double) // error: ambiguous implicit values

И напоследок пример с передачей в качестве неявного параметра def:

def double(implicit value: Int) = value * 2 val cappucinoLarge: Boolean = false implicit def cappucinoPrice: Int = if (cappucinoLarge) 200 else 100 println(double) // 200

Т.е. в итоге у нас получится

double(cappucinoPrice())

Примечания по синтаксису:

 def func1(implicit value1: Int) // value1 неявно def func2(implicit value1: Int, value2: Int) // value1 и value2 неявны def func3(value1: Int, implicit value2: Int) // ошибка компиляции def func4(value1: Int)(implicit value2: Int) // только value2 неявно def func5(implicit value1: Int)(value2: Int) // ошибка компиляции def func6(implicit value1: Int)(implicit value2: Int) // ошибка компиляции 
Неявное преобразование

Возвращаясь к примеру из Float в Int:

def double(value: Int) = value * 2 implicit def FloatToInt(value: Float):Int = value.toInt println(double(2.5F)) 

При вызове double у нас происходит несовпадение типа ожидаемого параметра (Int) с входящим параметром (Float). Поэтому компилятор ищет любой метод в области видимости, отмеченный implicit и с нужными в данной ситуации ожидаемым параметром (Int) и входящим параметром (Float). Находит FloatToInt, производит преобразование и передает дальше нужное значение в double.

Теперь, надеюсь, стало понятнее. Всем успехов в освоении Scala!

  • scala
  • implicit
  • функциональное программирование
  • Программирование
  • Scala
  • Функциональное программирование

Вывод реализаций интерфейсов в Scala c библиотекой Shapeless

В статье рассмотрим пример превращения данных алгебраического типа в представлении через sealed trait family в обобщенное представление. Покажем техники работы с этим обобщенным представлением на примере структурного сравнения, операции diff . В конце статьи — работающий пример в репозитории на GitHub.

Мотивация

Наверняка многим программистам, которые пишут на статически типизированных языках, часто приходится иметь дело с введением операции сравнения (метод equals , операция == и т. д.). В большинстве языков эта операция вводится непосредственным написанием кода операции. Чаще всего это может выглядеть как-то так:

class Foo < private var bar: Int private var baz: Double private var qux: String override def equals(that: Foo): Boolean = < this.bar == that.bar && this.baz == that.baz && this.qux == that.qux >>

Однако написание такого кода бывает достаточно громоздким и трудоемким, в особенности для большого количества классов.

Еще одна проблема, с которой, возможно, многие читатели могли столкнуться при тестировании — это поиск причины, по которой два объекта не равны, и конкретных полей, которые отличаются. Написание кода, который бы по заданному объекту напрямую отыскивал и перечислял все отличающиеся поля, снова привело бы к написанию большого количества бойлерплейта и сложной инфраструктуры.

Хотелось бы иметь магический метод Compare(a,b) , который бы работал для большого количества типов и в то же время был легко настраиваемым.

Решить задачу по написанию этого метода так, чтобы бойлерплейта пришлось писать по минимуму, можно несколькими способами. Во-первых, можно применить рефлексию для выведения механизма сравнения типов данных, но рефлексия славится монструозностью кода. И, что самое главное, рефлексия работает во время исполнения кода, что чревато ошибками времени исполнения, которые, в принципе, можно отловить на этапе компиляции. Во-вторых, можно применить кодогенерацию (шаблоны/макросы), которая бы генерировала весь бойлерплейт, однако, так или иначе, нужно будет усложнять процесс сборки и компиляции и выносить генерирование всего бойлерплейта в отдельный этап. Обычно это осложнено слаборазвитым тулингом для рефлексии времени компиляции и усложняющейся сборкой.

Однако в языке Scala есть решение, которое упрощает подобную кодогенерацию, убирая любую необходимость писать код «сбоку» приложения и как-либо модифицировать сборку и компиляцию проекта. Это решение, библиотека Shapeless, является набором макросов и достаточно хорошего API к ним, которая предоставляет разные абстракции для обобщенного программирования, такие как гетерогенный список, копроизведение, функции с зависимым от типа параметра типом возвращаемого значения и т. д. В частности, эта библиотека предоставляет механизм превращения ограниченных иерархий кейс-классов в гетерогенные списки, который и будет использоваться для решения задачи.

Будем решать эту задачу для семейств запечатанных трейтов, пользуясь их хорошими свойствами.

Семейства запечатанных трейтов в Scala (sealed trait family)

В Scala конструкции, состоящие из некоторого количества «интерфейсов», доступных к расширению в рамках одного файла (sealed trait), и классов, содержащих только неизменяемые данные ( case class и case object ), их наследующих, называются ограниченной иерархией кейс-классов. Эта конструкция довольно неплохо справляется с моделированием замкнутых ADT (Algebraic Data Type).

sealed trait Color sealed trait PredefColor extends Color case object Red extends PredefColor case object Green extends PredefColor case object Blue extends PredefColor case class RGB(r: Byte, g: Byte, b: Byte) extends Color case class RGBA(r: Byte, g: Byte, b: Byte, a: Byte) extends Color case class HSV(h: Byte, s: Byte, v: Byte) extends Color
case class Id(text: Id) sealed trait WithId < def id: Id >sealed trait UserData < def login: String def email: String >sealed trait AdminPriviledges sealed trait User case object Unregistered extends User case class New(id: Id) extends WithId case class LoggedUsser(id: Id, login: String, email: String) extends WithId with UserData case class Admin(id: Id, login: String, email: String, priviledges: Set[String]) extends WithId with UserData with AdminPriviledges

В свою очередь, программы на Scala очень часто пишутся с использованием принципа отделения данных от операций над ними, и ADT достаточно хорошо подходит для описания данных в таких программах.

ADT располагает рядом хороших свойств, например, данные иммутабельные и не содержат никаких сложных процедур построения внутреннего состояния. Или же ADT замкнуто (то есть то, что унаследовано от одного sealed trait, находится внутри одного файла), что позволяет делать полный перебор по структуре ADT, будучи уверенным, что все варианты будут перебраны. Кроме этого, все поля внутри конечных кейс-классов — открытые, что вместе с предыдущим фактом делает ADT весьма удобным типом данных с простой и понятной структурой.

Имплиситы и тайпклассы в Scala

Тайпкласс, как гласит Википедия, это конструкт для ad-hoc полиморфизма. Иными словами, способ для выбора конкретной реализации полиморфной функции по типу аргумента.

Реализация тайпкласса в Scala использует неявные значения и неявные аргументы функций, которые в этом языке являются очень мощным средством. Вообще-то на Хабрахабре по этому поводу есть довольно неплохая статья, но краткое их описание, необходимое для решения задачи, будет приведено ниже.

Во-первых, существуют неявные значения, они помечаются ключевым словом implicit , например:

implicit val foo: Int =5 implicit val

Существуют неявные аргументы функции, которые помечаются отдельным блоком параметров:

def functionWithImplicitParameters( regularParam: String )(implicit implicitParam1: String, implicitParam2: Int ): (String, String, Int)= (regularParam, implicitParam1, implicitParam2)

На места неявных параметров в месте вызова функции компилятор во время компиляции подставляет первые наиболее подходящие параметры. Если же параметров одного типа на место одного неявного параметра претендует больше одного, это вызывает ошибку компиляции diverging implicit expansion.

Несколько замечаний об этом виде неявных сущностей: неявные параметры могут быть функциями, которые имеют неявные параметры, и поиск неявных параметров рекурсивен. То есть следующий код будет валиден:

type T1 type T2 type T3 implicit def foo(implicit t1: T1): T2 implicit def bar(implicit t2: T2): T3 implicit val t1: T1 = . val res = bar

В данном случае вызов

bar(foo(t1))

Для типов неявных параметров нет строгих ограничений: типы неявных параметров и значений могут вполне быть как функциями, так и высшими кайндами.

Для неявных параметров с местом для еще одного параметра существует специальный синтаксический сахар, который позволяет превращать

type Bar[T] def foo[F](implicit b: Bar[F]): Unit
def foo[F : Bar]:Unit

При условии, что тип Bar имеет место для одного параметра.

Есть еще один тип имплиситов — неявные классы. Они могут иметь только один параметр, и в основном используются для добавления функциональности существующим объектам, таким образом чтобы не изменять код самих существующих объектов.

sealed trait Color sealed trait PredefColor extends Color case object Red extends PredefColor case object Green extends PredefColor case object Blue extends PredefColor case class RGB(r: Int, g: Int, b: Int) extends Color implicit class ToRgbOps(val color: PredefColor) extends AnyVal < def toRgb: RGB = < case Red =>RGB(255 byteValue, 0, 0) case Green => RGB(0, 255 byteValue, 0) case Blue => RGB(0, 0, 255 byteValue ) > >

И тогда мы сможем писать Red.toRgb или Green.toRgb .

Это очень удобный инструмент для предотвращения превращения класса в километровую простыню, в особенности вместе с тайпклассами.

Итак, переходим непосредственно к самим тайпклассам. Каждый тайпкласс состоит условно из компонентов. Первый — это интерфейс, заявляющий саму функциональность тайпкласса.

trait Show[A]

Второй компонент — это companion object этого трейта, который даст возможность использовать определенный синтаксис.

object Show

А сам синтаксис использования будет выглядеть так:

Show[A](a)

Третий компонент — это набор реализаций: implicit val showString: Show[String] = s> /* синтаксический сахар для анонимных классов c одним методом был создан, потому что писать new Foo каждый раз слишком громоздко*/

implicit val showString: Show[String] = s> /* синтаксический сахар для анонимных классов c одним методом, был создан, потому что писать new Foo каждый раз слишком громоздко*/ implicit val showInt: Show[Int] = i.toString> implicit def showList[T : Show]: Show[List[T]] = list.map.mkString("List(", ",", ")") >

Четвертый, не обязательный, но крайне желательный компонент — это «синтаксис» тайпкласса, который позволит вызывать этот метод через точку:

implicit class ShowSyntax[T](val t: T) extends AnyVal

А вызов будет выглядеть вот так:

println(List(1,2,3,4,5,6).show)

Деконструкция sealed trait family

Теперь мы попробуем построить sealed trait family из набора «примитивных» типов. Для этого нам потребуются следующие компоненты: набор идентификаторов Id , набор примитивных типов PT и несколько операций. Строить будем некоторое множество типов T . Во-первых, любой примитивный тип является и типом Т . Нам понадобится операция связывания идентификатора с типом, будем обозначать ее символом @ . То есть, если id — идентификатор и t — тип, то lt := t @ id — тип с идентификатором. Далее, введем операцию конструирования на типах с идентификаторами: если t1, …, tn — типы из Т и id1, …, idn — идентификаторы, то t := (t1 @ id1, t2 @ id2, …, tn @ idn) — тип из Т . Далее, вводим операцию «или» на типах: если t1, …, tn — типы из Т , то t := t1 | t2 | … | tn — тип из Т . Такая модель упрощенно показывает структуру ADT.

В нашем случае примитивными типами выступают, собственно, встроенные типы данных из разряда Int, Byte, Long, String, Double, Boolean и, кроме этого, различные типы, которые не являются частью ADT, такие как, например, java.time.Instant .

Операция конструирования моделирует введение нового типа при помощи кейс-классов или кейс-обджектов, например, из типов Int, String, String, идентификаторов foo, bar, baz мы можем построить новый тип Qux case class Qux(foo: Int, bar: String, baz: String) , который в нашей модели будет представлен как Qux := (Int @ foo, String @ bar, String @ baz) .

При этом различные вопросы по поводу того, какие поля включать в этот перечень и какие не включать и нужны ли дополнительные пометки о свойствах этих полей, мы можем смело отметать по той простой причине, что все поля равноправны и неизменяемы.

Операция «или» моделирует sealed trait. Ограниченность sealed trait рамками одного файла позволяет гарантировать, что перечень типов, которые наследуются от данного sealed trait, полон и известен на этапе компиляции.

sealed trait PredefColor case object Red extends PredefColor case object Green extends PredefColor case object Blue extends PredefColor

То есть в этом случае мы можем смоделировать PredefColor := Red|Green|Blue .

При этом разные обязательства по наличию полей в кейс-классах, которые наследуют трейты, в этой модели не учитываются.

Остается вопрос о параметрических типах вроде List[T] и т. д., но пока на этом останавливаться и вводить дополнительный формализм не будем: большинство вопросов, связанных с высшими каиндами, уже решено в механизме поиска имплиситов в компиляторе Scala.

На нашей модели вполне можно строить алгоритм структурного сравнения. Итак, нам нужно сравнить две структуры одинакового типа, но потенциально разного значения, и вывести список различных полей. Различные сложности сравнения неупорядоченных и упорядоченных коллекций, с которыми мы можем столкнуться, пока оставим за кадром и будем выводить наиболее простое решение.

Допустим, у нас есть некоторый набор операций сравнения для примитивных типов, тогда нам остается определить операцию сравнения для операции конструирования и для операции «или».

Для операции конструирования мы будем определять сравнение как объединение различия для всех элементов.

Для операции «или», с учетом объектов ob1, ob2. obn типов t1|. |tn , понятно, что настоящие типы этих объектов будут t_i и t_j для некоторых i,j из 1. n . Тогда если i == j , мы возвращаем результат сравнения внутренностей объектов, а если i != j , возвращаем несовпадение действительных типов.

Инструментарий

Нам понадобятся абстракции для представления операций @, (_. _) и “|” . К счастью, библиотека Shapeless предоставляет таковые.

Для операции @ существует отдельный тип FieldType[Identifier, T] , который представляет абстракцию для поля класса, названного некоторым именем. О его использовании — ниже.

Для моделирования операции конструирования Shapeless представляет гетерогенный список HList . Отличие гетерогенного списка от обычного состоит в том, что этот список хранит информацию о типе каждого элемента в типе самого списка.

Дело в том, что сам тип HList — это надтип для очень широкого семейства типов, но конструктора у конкретных типов всего два: HNil — пустой список и ::[+Head, +Tail

HList умеет очень многое, связанное с информацией о типах. Более подробную информацию можно получить в описании библиотеки на GitHub.

Нам же пригодится только возможность рекурсивно проходить по элементам этого списка.

Далее, операцию «или» представляет тип Coproduct . Он подобен HList в том, что имеет структуру, похожую на цепь, но на этот раз у него есть несколько конструкторов. Общий тип Coproduct населен типами T1 :+: T2 :+: … :+: TN :+: CNil, для N= 1,2,3. . Каждый тип для фиксированного N= N0 состоит из элементов Inl(t1: T1), Inr(Inl(t2: T2), … , Inr(Inr(,, Inl(tn0: TN0))) . Где в H :+: T при T

Рекурсивное прохождение по всем возможным вариантам принадлежности конкретного объекта к типу будет очень похоже на такое у гетерогенного списка.

Теперь нам необходимо связующее звено, которое выведет тип представления конкретного объекта через описанные выше три типа данных и предоставит механизм для превращения из конкретного объекта в обобщенное представление. В Shapeless существует тайпкласс LabelledGeneric , экземпляры которого генерируются неявным макросом (как и большинство экземпляров тайпклассов в этой библиотеке, так что открытие портала в измерение неявных макросов и призыв реализаций — это вполне обыкновенный способ взаимодействия с ней) на этапе компиляции. Чтобы «призвать» LabelledGeneric для типа T в скоупе, в котором объявлен, достаточно написать:

import shapeless._ val v = LabelledGeneric[T]

Для того чтобы призвать экземпляр тайпкласса для параметра типа T , необходимо потребовать implicit параметр lgen: LabelledGeneric.Aux[T, Repr] , и ввести дополнительный параметр, который будет нести тип представления Repr .

Из чего будет состоять тип Repr ? Этот тип будет действовать именно по описанной выше модели. Для кейс-классов он будет выдавать HList из FieldType[FieldName, TypeName] , тегированный специальным образом, для sealed trait — coproduct.

Следует отметить, что у IDE возникают определенные сложности с определением типов репрезентации labelled generic . Например, для класса

case class Foo(s: String, i: Int, b: Boolean)

. мы получим тип LabelledGeneric[Foo] , который, естественно, соответствовать настоящему не будет, но даст нам некоторое представление о том, как это выглядит в реальности.

LabelledGeneric.Aux[ Foo, FieldType[String with KeyTag[Symbol with Tagged[], String], String] :: FieldType[Int with KeyTag[Symbol with Tagged[], Int], Int] :: FieldType[Boolean with KeyTag[Symbol with Tagged[], Boolean], Boolean] :: HNil ]

Здесь страшные типы вроде String with KeyTag[Symbol with Tagged[], String] — это способ библиотеки Shapeless генерировать уникальные теги на уровне типов для полей классов.

sealed trait All case class Foo(s: String, i: Int, b: Boolean) extends All case class Bar(l: Long, f: Foo) extends All case class Baz(foos: List[Foo], bars: List[Bar]) extends All

Мы получим выражение:

LabelledGeneric.Aux[ All, Bar with KeyTag[Symbol with Tagged[Symbol with Tagged[]], Bar] :+: Baz with KeyTag[Symbol with Tagged[Symbol with Tagged[]], Baz] :+: Foo with KeyTag[Symbol with Tagged[Symbol with Tagged[]], Foo] :+: CNil ]

И снова, приписки with KeyTag[_, _] относятся к техническому аспекту shapeless выдавать уникальные типы на каждый класс. (Подробнее — Singleton types)

Естественно, работать с этими типами вручную не нужно — с ними нужно работать при помощи рекурсии, и это мы рассмотрим чуть ниже.

Решение

Итак, объявим интерфейс и несколько вспомогательных классов. ComparisonResult для результата сравнения в виде Success и Failure. FailEntry[T] для представления различий. Path для определения местонахождения сравниваемого элемента.

package object genericComparators < sealed trait ComparisonResult < def append(fe: FailEntry[_]): ComparisonResult def &&(that: ComparisonResult): ComparisonResult def fails: Chain[FailEntry[_]] >object ComparisonResult < case object Success extends ComparisonResult < override def append(fe: FailEntry[_]): ComparisonResult = Failure(Chain(fe)) override def &&(that: ComparisonResult): ComparisonResult = that override def fails: Chain[FailEntry[_]] = Chain.empty[FailEntry[_]] >case class Failure(fails: Chain[FailEntry[_]]) extends ComparisonResult < override def append(fe: FailEntry[_]): ComparisonResult = Failure(fails :+ fe) override def &&(that: ComparisonResult): ComparisonResult = Failure(this.fails ++ that.fails) >> case class FailEntry[T](path: AdtPath, left: T, right: T) object AdtPath < val root = AdtPath(Chain.empty[PathElement]) >sealed trait PathElement case object Root extends PathElement case class DownGeneric(generic: String) extends PathElement case class DownField(field: Symbol) extends PathElement case class DownCoproductElement(coproductType: Symbol) extends PathElement case class Primitive(field: String) extends PathElement case class DownIterable(index: Long) extends PathElement case class DownManual(tag: String) extends PathElement case class AdtPath(steps: Chain[PathElement], last: PathElement = Root) < def downHlist(fieldName: Symbol): AdtPath = last match < case DownField(_) =>AdtPath(steps, DownField(fieldName)) case Primitive(_) => throw new RuntimeException(s"should not never happen") case _ => AdtPath(steps :+ last, DownField(fieldName)) > def downCoproduct(element: Symbol): AdtPath = last match < case DownCoproductElement(_) =>AdtPath(steps, DownCoproductElement(element)) case Primitive(_) => throw new RuntimeException(s"should not never happen") case _ => AdtPath(steps :+ last, DownCoproductElement(element)) > def downGeneric(className: String): AdtPath = last match < case Primitive(_) =>throw new RuntimeException(s"should not never happen") case _ => AdtPath(steps :+ last, DownGeneric(className)) > def downIterable(index: Long): AdtPath = last match < case DownIterable(_) =>AdtPath(steps, DownIterable(index)) case Primitive(_) =>throw new RuntimeException(s"should not never happen") case _ => AdtPath(steps :+ last, DownIterable(index)) > def downManual(manual: String): AdtPath = AdtPath( steps :+ last, DownManual(manual)) def primitive(primitiveTag: String): AdtPath = AdtPath( steps :+ last, Primitive(primitiveTag)) > >

Далее, определяем интерфейс нашего тайпкласса и несколько простых реализаций:

object GenericComparer < def compare[T](first: T, second: T)(implicit compare: GenericComparer[T] ): ComparisonResult = compare.apply(first, second)(AdtPath.root, ComparisonResult.Success) def instance[U](f: (U, U) =>Boolean)(tag: String = ""): GenericComparer[U] = new GenericComparer[U] < override def apply(t1: U, t2: U)(implicit path: AdtPath, result: ComparisonResult): ComparisonResult = if (f(t1, t2)) result else result.append(FailEntry(path, t1, t2)) >> trait GenericComparer[T]

Неявный параметр path нужен для возможности «записывать» пройденный путь по структуре класса при рекурсивном применении этой функции. Неявный параметр result является аккумулятором в рекурсии.

В компанион обджекте создан метод def compare[T](first: T, second: T)(implicit compare: GenericComparer[T]): ComparisonResult , который предоставляет интерфейс для использования тайпкласса как GenericComparer.compare(a,b) .

Там же функция для создания реализации из функции сравнения instance .

Пользуясь этой функцией, можно сделать набор реализаций для примитивов:

implicit val scompare: GenericComparer[String] = GenericComparer.instance[String] < _ == _ > implicit val icompare: GenericComparer[Int] = GenericComparer.instance[Int] < _ == _ > implicit val lcompare: GenericComparer[Long] = GenericComparer.instance[Long] < _ == _ > implicit val bcompare: GenericComparer[Byte] = GenericComparer.instance[Byte] < _ == _ > implicit val boolcompare: GenericComparer[Boolean] = GenericComparer.instance[Boolean] < _ == _ > implicit val ccompare: GenericComparer[Char] = GenericComparer.instance[Char] < _ == _ > implicit val shortcompare: GenericComparer[Short] = GenericComparer.instance[Short] < _ == _ > implicit val bicompare: GenericComparer[BigInt] = GenericComparer.instance[BigInt] < _ == _ > implicit val dcompare: GenericComparer[Double] = GenericComparer.instance[Double] < _ == _ >

Далее, приступим к созданию операции для композитного объекта, который представим в виде LabeledGeneric .

//decompose sealed trait family implicit def lgenCompare[T, Repr]( implicit ctag: ClassTag[T], lgen: LabelledGeneric.Aux[T, Repr], reprCompare: Lazy[GenericComparer[Repr]]): GenericComparer[T] = new GenericComparer[T] < override def apply(t1: T, t2: T)(implicit path: AdtPath, result: ComparisonResult): ComparisonResult = < reprCompare.value.apply( lgen.to(t1), lgen.to(t2))( path.downGeneric(ctag.runtimeClass.getSimpleName), result ) >>

Эта реализация функции тайпкласса пытается «призвать» LabelledGeneric с каким-либо типом представления и вывести реализацию для обобщенного представления. Но сама по себе эта реализация бесполезна без реализаций для примитивов, случая с HList и Coproduct . Обратите внимание на то, что операция сравнения для обобщенного представления Repr обернута в Lazy , для того чтобы избежать ошибки diverging implicit expansion .

Итак, сначала случай HList .

Терминальная точка для рекурсии:

implicit val hnilCompare: GenericComparer[HNil] = GenericComparer.instance[HNil] < (_, _) =>true >

И сама рекурсия, метод который выводит операцию сравнения для непустого списка Head :: Tail :

implicit def hconsCompareKeyed[Key >

Откуда такой набор типов и такая сигнатура? Во-первых, нам необходимо имя поля, его достаем при помощи типа Key , который является символом. Для «вызова» значения имени поля используем неявный параметр key: Witness.Aux[Key] , который и вызовет то значение, которое кодируют страшные типы из главы выше. Это и есть тот обещанный способ не работать напрямую с типом тега, который тегирует конкретное поле в классе — введя его как параметр функции, компилятор попытается его вывести автоматически.

Далее, Head — это тип тегируемого при помощи Key поля в классе, нам необходимо иметь для него операцию сравнения, поэтому мы заявляем это как еще один неявный параметр — compareHeads: GenericComparer[Head] .

И наконец, чтобы сделать рекурсивный вызов, мы вводим параметр типа хвоста списка Tail , который снова должен быть гетерогенным списком, и просим вывести для хвоста реализацию при помощи заявления еще одного неявного параметра: compareTails: Lazy[GenericComparer[Tail]] .

Почему это будет рекурсивным вызовом? Потому что под тип GenericComparer[Tail] подпадает эта же реализация, или же терминальная точка рекурсии hnilCompare . При этом мы избавились от необходимости рассматривать все типы списка сразу, а рассматриваем их только по одному за вызов, что позволяет обрабатывать списки произвольной длины.

Внутренности этой реализации довольно примитивные, основную работу делают неявные параметры.

Теперь рассмотрим случай Coproduct . Терминирование рекурсии будем производить при помощи:

implicit val cnilCompare: GenericComparer[CNil] = GenericComparer.instance[CNil] < (a, b) =>a.impossible >

Этот метод никогда не будет вызван, но необходим, чтобы остановить поиск неявных параметров. Теперь непосредственно реализация для непустого произведения, подобная той, что мы привели для HList .

implicit def cconsCompareKeyed[Key compareHeads.apply(a, b)(newPath, result) case (Inl(_), Inr(_)) | (Inr(_), Inl(_)) => result.append(FailEntry(newPath, Coproduct.unsafeGet(t1), Coproduct.unsafeGet(t2))) case (Inr(tail1), Inr(tail2)) => compareTails.value.apply(tail1, tail2) > > >

В этой реализации мы проходим по всем возможным типам объектов, которые входят в произведение, и для случая, когда типы объектов совпадают, проводим сравнение содержимого. Механизм рекурсии и получения имени конкретного элемента-типа произведения — точно такой же, как и в случае с HList .

Для завершенности приведем очень ограниченную базовую реализацию сравнения последовательностей (на самом деле, скрещивания алгоритма для диффов последовательностей и множества с иерархической структурой нетривиальны и достойны отдельной статьи, но все предложения по усовершенствованию принимаются).

def compareIterables[T: GenericComparer]: GenericComparer[Iterable[T]] = new GenericComparer[Iterable[T]] < override def apply(t1: Iterable[T], t2: Iterable[T])(implicit path: AdtPath, result: ComparisonResult) : ComparisonResult = < if (t1.size == t2.size) < (t1 zip t2).foldLeft((result, 0)) < case ((res, i), (el1, el2)) =>(implicitly[GenericComparer[T]].apply(el1, el2)(path.downIterable(i), res), i + 1) >._1 > else result.append(FailEntry(path.downIterable(-1), t1, t2)) > >

Объединение

Теперь необходимо соединить все в единую структуру, пригодную к использованию. Нам бы хотелось при всем том, что умеет эта библиотека, уметь заменять генерацию операции своей реализацией, иначе бы от такой библиотеки пользы было мало. Достичь этого можно при помощи механизма затенения неявных значений (implicit shadowing). Для этого нужно положить реализацию для Labelled generic, HList и Coproduct в трейт GenericComparatorsLowestPriority . Затем от него наследовать трейт AllComparators со всеми реализациями для примитивов. Далее — в любой точке применения наследовать AllComparators своим классом/обджектом/трейтом.

При этом для одного и того же типа компилятор будет выбирать только тот имплисит, который находится наименее глубоко в иерархии наследования. Поэтому имплисит для LabelledGeneric будет легко перекрываться вашим собственным. При этом импортировать значение из GenericComparatorsLowestPriority категорически нельзя.

Готовый результат можно посмотреть в репозитории на GitHub.

Наиболее простой способ запустить этот код локально — установить intellij IDEA Community edition и Scala plugin к ней, далее просто открыть проект и импортировать — плагин и IDE сделают все сами.

Преимущества и недостатки

В итоге мы малыми усилиями добились способа получать операцию структурного сравнения без написания бойлерплейта, при этом написав совсем немного кода. При добавлении новых классов нам необходимо перегружать эту операцию только для типов-примитивов.

Основным недостатком текущей реализации является то, что выяснение причины, по которой компилятор не может вывести операцию сравнения для чего-нибудь, может занимать определенное время, но опция компилятора «-Xlog-implicits» станет хорошим подспорьем — пройдясь по сообщениям, можно понять, чего именно не хватает. Единственное утешение — вы всегда узнаете об этом до запуска программы.

Второй недостаток — не самая хорошая работа со множествами и коллекциями, но это как раз дело поправимое.

Послесловие

На самом деле продемонстрированным способом можно получать реализации для других тайпклассов, не только операции сравнения. Например, для процедуры кодирования/декодирования в разные форматы.

Все про українське ІТ в телеграмі — підписуйтеся на канал DOU

Заметки о функциональном программировании. Статическая типизация и декомпозиция.

lambda

В этой статье речь пойдет о системе статической типизации и ее применениях. Начнем снова с темы ООП и покажем, наконец, что функциональный язык может быть чистым ОО языком. Далее я постараюсь продемонстрировать преимущества статической типизации и рассказать про ее основные возможности, такие как границы типов и вариантность. Потом мы поговорим о том, как механизмы сопоставления с образцом и implicit преобразования, основанные на статической типизации, позволяют декомпозировать программы. Все нижесказанное относится к большинству функциональных языков, поэтому будет полезно не только Scala разработчикам.

Везде объекты

В предыдущих постах (этом, этом и этом) мы определили в нашей модели вычислений три примитивных типа: функции, примитивные типы-значения и объекты классов. Три типа - это слишком много, поэтому в этом разделе мы сведем их все к объектам.

На самом деле в Scala функции реализованы в виде объектов. Например тип функции A => B просто псевдоним для класса, являющегося потомком scala.Function1[A,B]:

package scala trait Function1[A,B]  def apply(x: A): B >

Теперь очевидно что функция - это просто объект с методом apply . Синтаксический сахар позволяет добавить к имени объекта список аргументов и вызвать метод apply : f(1) == f.apply(1) . Для функций с двумя параметрами существует класс scala.Function2 и так далее до 22 (в текущей версии языка).

Стоит заметить (спасибо Ivan Yurchenko), что методы классов в целях оптимизации и защиты от бесконечной рекурсии (касается метода apply ) не являются функциями. Например метод def apply(x: Int): Boolean = . не является объектом Function1 . Подобная строка кода вообще не возвращает значения. В случае необходимости создается функциональный объект-обертка. В большинстве случаев Scala скрывает от нас разницу между функцией и ее оптимизированным представлением в виде метода. Но существуют исключения из этого правила, о которых мы поговорим в других статьях.

Анонимные функции реализованы схожим образом. В качестве примера рассмотрим реализацию функции (x: Int) => x * x . Это выражение трактуется как следующий код:

 class AnonFunc extends Function1[Int, Int]  def apply(x: Int) = x * x > new AnonFunc >

Результатом этого блока кода будет объект класса AnonFunc . Этот класс недоступен вне своей области видимости. Похожего результата можно добиться, воспользовавшись анонимным классом:

val f = new Function1[Int, Int]  def apply(x: Int) = x * x >

Работа с анонимными классами в Scala аналогична Java.

Завершим разговор о функциях примером. Дополним реализацию списка из предыдущей статьи объектом-компаньоном, который будет использоваться для создания списков следующим образом:

 List[Int]() // -> Nil List(1) // Список из одного элемента List(1, 2) // Список из 2-х элементов 

Этого можно достичь, определив методы apply в объекте-компаньоне:

object List  def apply[T]() = new Nil[T] def apply[T](x1: T) = new Cons(x1, Nil) def apply[T](x1: T, x2: T): List[T] = new Cons(x1, new Cons(x2, Nil)) >
  • apply может быть параметрически полиморфной функцией;
  • Scala умеет выводить параметр типа из значения аргумента, что видно на примере List(1) и List(1, 2) ;
  • Scala позволяет объявлять функции с одним именем, но разным количеством или типом аргументов. Подобные объявления называются перегрузкой функций и являются примером специального полиморфизма (или ad hoc полиморфизма).

С функциями закончили. Теперь приступим к более сложной задаче - выразим примитивные типы через объекты. Scala в целях оптимизации оптимизации представляет типы-значения в виде примитивных типов JVM. Но для полного понимания модели вычислений полезно уяснить, что примитивные типы не нужны. Я продемонстрирую справедливость этого утверждение на примере двух примитивных типов - логических значений и натуральных чисел.

Начнем с класса логических значений. Идеальная реализация класса Boolean , не использующая ничего кроме объектов, может выглядеть так:

package idealized.scala abstract class Boolean  def ifThenElse[T](then: => T, else: => T): T def && (x: => Boolean): Boolean = ifThenElse(x, false) def || (x: => Boolean): Boolean = ifThenElse(true, x) def unary_!: Boolean = ifThenElse(false, true) def == (x: Boolean): Boolean = ifThenElse(x, x.unary_!) def != (x: Boolean): Boolean = ifThenElse(x.unary_!, x) >

Наибольший интерес вызывает абстрактный метод ifThenElse . Он принимает (по имени) в качестве аргументов два произвольных объекта и возвращает один из них. Какой конкретно зависит от подкласса. Подклассов, как известно, два:

object true extends Boolean  def ifThenElse[T](then: => T, else: => T): T = then > object false extends Boolean  def ifThenElse[T](then: => T, else: => T): T = else >

Метод && реализует логическое “И” и работает по следующим правилам:

this/x true false
true 1 0
false 0 0

Реализация метода && в true возвращает значение, переданное в качестве аргумента. Реализация в false возвращает false . Наш && полностью соответствует таблице. Остальные методы работают схожим образом.

Теперь давайте рассмотрим задачу по-сложнее - числовой тип. Правда вместо класса Int , из соображений экономии места и времени, рассмотрим его упрощенную версию - класс натуральных чисел Nat с операцией сложения. Натуральные числа определим по индукции начиная с 0:

  • ноль - натуральное число;
  • число, следующее за натуральным числом тоже является натуральным числом.

Формально этот способ описан в виде аксиом Пеано. Код будет следующим:

abstract class Nat  def isZero: Boolean // true если ноль def predecessor: Nat // предыдущее натуральное число def successor: Nat = new Succ(this) // следующее натуральное число def + (that: Nat): Nat def - (that: Nat): Nat > object Zero extends Nat  def isZero: Boolean = true def predecessor = throw new IlligalStateException("0.predecessor") def + (that: Nat): Nat = that def - (that: Nat): Nat = that.isZero.ifThenElse(Zero, () => (throw new IlligalStateException("0.predecessor"))) > class Succ(n: Nat) extends Nat  def isZero: Boolean = false def predecessor = n def + (that: Nat): Nat = new Succ(n + that) def - (that: Nat): Nat = that.isZero.ifThenElse(this, n - that.predecessor) >

Начиная с единицы каждое последующее число строится на базе предыдущего. Операции сложения и вычитания определены рекурсивно. Сложение на каждом шаге рекурсии пытается сложить аргумент с числом, на единицу меньшим чем на предыдущем шаге, пока рекурсивный процесс не спустится до Zero. К результату сложения на каждом шаге добавляется единица. Подобная схема не работает с вычитанием, так как n может быть равно Zero , поэтому код немного сложнее.

Подведем итоги. Scala чистый объектно-ориентированный язык, в котором все значения - объекты, а все типы - классы. Но этот факт не мешает Scala быть функциональным языком с соответствующей моделью вычислений.

Границы типов и вариантность

В этой части статьи я бы хотел рассмотреть одну важную вещь - связь параметрического полиморфизма и иерархии классов. Долгое время этой проблеме уделялось мало внимания, в том числе разработчиками основных языков программирования. Последнее время эта тенденция изменилась. Одним из преимуществ Scala является способность ее механизма типизации решать задачи соотнесения иерархии полиморфных типов с иерархией классов.

Начнем с демонстрации актуальности проблемы. Вспомним наш список целых чисел и напишем метод assertAllPos , который:

  • принимает аргумент IntList ;
  • возвращает аргумент IntList если все его элементы положительны;
  • иначе бросает исключение.

Можно написать такой код:

 def assertAllPos(s: IntList): IntList

Это рабочее решение, но есть один недостаток. Интерфейс не полностью описывает спецификацию. Хотелось бы при взгляде на метод понять что assertAllPos(Nil) вернет Nil , а assertAllPos(Cons(. )) вернет Cons . В Scala решение достаточно простое:

def assertAllPos[S  IntList](r: S): S = . 

Выражение S верхнюю границу типа S или, проще говоря, определяет, что тип S должен быть потомком IntList .

Границы типа позволяют определить связь параметра типа с иерархией классов. У аргумента типа существует три границы:

  • верхняя S
  • средняя S: T , означающая что тип S точно соответствует T (нужна для implicit параметров, о них в конце статьи);
  • нижняя S >: T , означающая, что S базовый класс T .

Scala позволяет задать верхнюю и нижнюю границы одновременно:

 [S >: B  

Этот код определяет место S в иерархии классов между B и A .

Полиморфный класс или метод ковариантен, если иерархия производных по параметру типа классов совпадает с иерархией параметра типа.

Массивы Java или C# ковариантные и объявляются так: T[] . Следующий, корректный с точки зрения синтаксиса, код имеет большие проблемы с типизацией:

NonEmpty[] a = new NonEmpty[] new NonEmpty(1, Empty, Empty) > IntSet[] b = a b[0] = Empty // OLOLOLOLOLOLO. NonEmpty s = a[0]

Мы положили в массив непустых множеств пустое множество, затем мы присвоили пустое множество переменной, которая имеет тип непустого множества. Java решает эту проблему сохранением и анализом параметра типа во время выполнения. Код выше бросит исключение ArrayStoreException на третей строке. Но это костыль, ведь суть проблемы в том, что массивы не могут быть ковариантными. Все ли операции с IntSet[] применимы к NonEmpty[] ? Ответ - нет! Мы не можем, например, присваивать элементам NonEmpty[] значения Empty , в то время как IntSet[] можем. В Scala массивы никак не связанны с иерархией параметра типа или, другими словами, являются невариантными

В Java и C# массивы ковариантные для того, чтобы можно было передавать любые массивы в методы принимающие Object[] . До введения дженериков в Java 1.5 подобные костыли были единственным способом реализовать, например, универсальный метод сортировки массивов.

Заметим, что предыдущий пример не вписываются в нашу функциональную модель вычислений потому что массивы изменяемые. Операции изменения состояния (мутаторы) делают массивы невариантными. Неизменяемые списки Scala, напротив, ковариантные и отлично работают. Вообще полиморфные типы могут быть трех видов (для случая A

  • невариантные, если C[A] и C[B] никак не связаны
  • ковариантные, если C[A]
  • контрвариантные, если C[A] >: C[B]

Scala использует следующий синтаксис для описания этих случаев вариантности:

  • невариантность class C[A]
  • ковариантность class C[+A]
  • контрвариантность class C[-A]

Можно сформулировать следующие упрощенные правила применимости разных типов вариантности для полиморфных методов (компилятор Scala проверяет соблюдение подобных правил автоматически):

  • параметр типа, по отношению к которому метод невариантен, может быть безопасно использован как в списке аргументов, так и в качестве типа возвращаемого результата
  • параметр типа, по отношению к которому метод ковариантен, могжет являться типом возвращаемого значения
  • параметр типа, по отношению к которому метод контрвариантен, может являться типом аргумента

Продемонстрируем справедливость этих правил на примере двух типов:

type A = IntSet => NonEmpty type B = NonEmpty => IntSet

Работать с A можно так же как с B , но не наоборот. Можно сказать, что A является B или A потомок B . Общее правило иерархии функциональных типов таково:

 если A2 B1 B2. 

Это правило полностью подтверждает сказанное выше.

В качестве примера практического применения вариантности рассмотрим два случая. Первый из них - это класс Function1 из предыдущего раздела. Ранее мы давали упрощенную реализацию. Чтобы иметь возможность использовать одни функции вместо других нам нужно выстроить иерархию их типов. Сделать это можно следующим образом:

package scala trait Function1[-T, +U]  def apply(x: T): U >

Теперь все хорошо и, например, объект типа IntSet => NonEmpty может быть передан как аргумент в метод с типом NonEmpty => IntSet .

Второй пример - улучшенная реализация списка из предыдущей статьи. Оригинальная реализация такова:

trait List[T]  def isEmpty: Boolean def head: T def tail: List[T] > class Cons[T](val head: T, val tail: List[T]) extends List[T]  def isEmpty = false > class Nil[T] extends List[T]  def isEmpty: Boolean = true def head: Nothing = throw new NoSuchElementException("Nil.head") def tail: Nothing = throw new NoSuchElementException("Nil.tail") >

Хорошим решением было бы заменить класс Nil объектом-одиночкой, но этот класс типизирован. Мы можем решить эту проблему воспользовавшись тем фактом, что списки ковариантные и тип Nothing является подклассом любого другого типа:

trait List[+T]  def isEmpty: Boolean def head: T def tail: List[T] > class Cons[T](val head: T, val tail: List[T]) extends List[T]  def isEmpty = false > object Nil extends List[Nothing]  def isEmpty: Boolean = true def head: T = throw new NoSuchElementException("Nil.head") def tail: T = throw new NoSuchElementException("Nil.tail") >

Теперь все в порядке и код вроде val x: List[String] = Nil синтаксически корректен.

Декомпозиция программы в функциональном стиле и сопоставление с образцом

Многие сталкивались с проблемой выбора способа разбиения программы на классы. С одной стороны стоят компактные варианты, но с грязными хаками вроде привидений типа, с другой - ОО паттерны-костыли и куча служебного кода. В функциональном программировании такие проблемы решаются просто и элегантно с помощью сопоставления с образцом (pattern matching).

Проиллюстрируем проблему на примере. Предположим нам нужен простой интерпретатор арифметических выражений. Требуется поддержка чисел и их сложения. Естественным желанием будет объявить интерфейс Expr и реализовать два его подкласса - Number и Sum :

trait Expr  def isNumber: Boolean def isSum: Boolean def numValue: Int def leftOp: Expr def rightOp: Expr > class Number(n: Int) extends Expr  def isNumber: Boolean = true def isNum: Boolean = false def numValue: Int = n def leftOp: Expr = throw new Error("Number.leftOp") def rightOp: Expr = throw new Error("Number.rightOp") > class Sum(e1: Expr, e2: Expr) extends Expr  def isNumber: Boolean = false def isSum: Boolean = true def numValue: Int = throw new Error("Sum.numValue") def leftOp: Expr = e1 def rightOp: Expr = e2 >

В интерфейсе мы имеем два метода для определения типа объекта и три метода для получения данных (гетера). Использовать эти классы можно следующим образом:

def eval(e: Expr): Int =  if (e.isNumber) e,numValue else if (e.isSum) eval(e.leftOp) + eval(e.rightOp) else throw new Error("Unknownt expression" + e) >

Кому-то этот код понравится, но я считаю, что это эталонный быдлокод из палаты мер и весов. Предположим нам нужно добавить операцию умножения. Для этого придется добавить метод определения типа Prod в Expr , реализовать его во всех подклассах, добавить класс Prod и дописать eval . Количество методов, которые необходимо определить растет нелинейно от количества классов. Таким образом наше первое решение никуда не годится.

Лучшим решением будет убрать отовсюду методы для определения типа объекта. Для определения типа можно использовать механизмы определения и привидения типов. В Scala эти механизмы реализованы посредством двух методов Any :

def isInstanceOf[T]: Boolean def asInstanceOf[T]: T

Эти методы позволят убрать из интерфейса методы isNumber , isSum и им подобные. Нужно будет только изменить eval :

def eval(e: Expr): Int = if (e.isInstanceOf[Number]) e.asInstanceOf[Number].numValue else if (e.isInstanceOf[Sum]) eval(e.asInstanceOf[Sum].leftOp) + eval(e.asInstanceOf[Sum].rightOp) else throw new Error("Unknown expression " + e)

Наше второе решение имеет следующие особенности:

  • кода стало меньше, а масштабируемость гораздо больше;
  • подобная работа с типами не позволяет компилятору проверить типизацию и может привести к ошибкам во время выполнения программы.

Избежать проблем с типизацией позволяет решение проблемы в ООП стиле с использованием паттерна компоновщик:

trait Expr  def eval: Int > class Number(n: Int) extends Expr  def Eval: Int = n > class Sum(e1: Expr, e2: Expr) extends Expr  def eval: Int = e1.eval + e2.eval >

Код eval теперь “размазан” по всей программе. Если нам понадобиться добавить, например, метод display для печати выражения, нам нужно будет реализовать его в каждом подклассе. Но настоящей проблемой является локальность подобных методов по отношению к объекту. Мы не сможем реализовать метод, расставляющий скобки в выражении вроде такого: (a + b) * (a + c) . Подобный метод должен работать с несколькими выражениями, на что наши локальные методы не способны. Таким образом третье решение тоже отстой. К счастью, функциональные языки позволяют решать задачи декомпозиции лучше рассмотренных подходов.

Для первой реализации можно заметить, что методы определения типа и гетеры служат для того, чтобы получить информацию, доступную в момент создания объекта. Это информация о имени класса и его аргументах. Например результаты вычисления методов isSum, leftOp, rightOp дают ту же информацию, что и код new Sum(exp1, exp2) . Поэтому, если бы мы имели безопасный доступ к типу объекта и аргументам класса, мы бы могли устранить недостатки предыдущих реализаций. Такую возможность дает механизм сопоставления с образцом.

Для того, чтобы получать информацию о моменте создания объекта его класс нужно объявить как case-класс:

trait Expr case class Number(n: Int) extends Expr case class Sum(e1: Expr, e2: Expr) extends Expr

Для case-классов автоматически создаются объекты-компаньоны:

object Number  def apply(n: Int) = new Number(n) > object Sum  def apply(e1: Expr, e2: Expr) = new Sum(e1, e2) >

Поэтому для создания объекта case-класса необязательно слово new . Кроме того, для каждого case-класса создается метод equals и его параметры доступны вне класса (как будто они объявлены с val ).

Мы видим, что методов у наших классов нет вообще и они не нужны! Нам достаточно информации о том, как объект создавался. Для анализа этой информации используется сопоставление с образцом - концепция, обобщающая switch из Java или C#. В Scala для сопоставления с образцом используется синтаксическая конструкция match :

def eval(e: Expr): Int = e match  case Number(n) => n case Sum(e1, e2) => eval(e1) + eval(e2) >

Работает конструкция e match e1; . ; case pN => eN> по следующим правилам:

  • каждый case определяет соответствие паттерн => выражение , соответствия упорядочиваются в порядке объявления;
  • если найден паттерн, соответствующий первому операнду match , переменные паттерна подставляются в выражение (далее подробнее) и выражение возвращается как результат;
  • если совпадений не найдено бросается MatchException.

Паттерны состоят из следующих элементов:

  • конструкторы case-классов;
  • констант, например 1 или true;
  • переменных, являющихся идентификаторами Scala, начинающихся с маленькой буквы;
  • символа подстановки _ , означающего в паттерне любое значение.

В момент сопоставления определяется тип входного выражения и аргументы класса. Далее происходит сопоставление с паттерном по следующим правилам:

  • конструктор и константы должны совпадать с типом объекта и значениями соответствующих аргументов (применяется ==);
  • на месте переменных в паттерне может находиться любое значение;
  • на месте символа _ может находиться любое значение.

В примере видно, что переменные могут входить как в паттерн, так и в выражение. В паттерне они связываются со значениями соответствующих аргументов case-классов и эти значения могут быть использованы в выражении. Переменная может встречаться в паттерне не более одного раза. Кроме того аргументами case-класса могут быть объекты case-классов и естественно, что match работает рекурсивно. Например код case Sum(Number(x), Numer(y)) => x + y вполне корректен.

В завершении темы добавим в нашу реализацию интерпретатора метод display и возможность выполнять произведение чисел. Это делается очень просто:

trait Expr case class Number(n: Int) extends Expr case class Sum(e1: Expr, e2: Expr) extends Expr case class Prod(e1: Expr, e2: Expr) extends Expr def eval(e: Expr): Int = e match  case Number(x) => x case Sum(e1, e2) => eval(e1) + eval(e2) case Prod(e1, e2) => eval(e1) * eval(e2) > def display(e: Expr): String = e match  case Number(x) => x.toString case Sum(e1, e2) => display(e1) + " + " + display(e2) case Prod(e1, e2) =>  def inParentheses(e: Expr): String = e match  case Sum(_,_) => "(" + display(e) + ")" case _ => display(e) > inParentheses(e1) + " * " + inParentheses(e2) > >

Этот код лишен недостатков предыдущих решений - способен расставлять скобки, прост и лаконичен, очень хорошо масштабируется.

Классы типов и implicit преобразования

Реализация интерпретатора была бы еще удобнее, если бы мы могли вместо Number(2) писать просто 2 . Этого можно добиться при помощи концепции, называемой классом типов. Непонятное определение:

Класс типов (type class) - это элемент системы типов, позволяющий использовать ограничения на параметры типа полиморфного типа. Ограничения, например, могут быть выражены в требовании к наличию определенных методов в интерфейсе параметра типа.

Проще говоря, если во время компиляции кода компилятор Scala не может найти метод, то он проверяет, есть ли метод с таким же именем, но другим типом или другим количеством аргументов. Например требования к интерфейсу аргумента являются классом типов. Компилятор автоматически выполняет поиск удовлетворяющих классу типов implicit-функций или implicit-аргументов. impliced-функции используются для прозрачного и безопасного приведения типов:

implicit def intToNumber(x: Int) = Number(x)

Теперь вместо Prod(Number(2), Number(3)) можно просто писать Prod(2, 3) . При вызове Prod компилятор поймет, что нужно преобразовать класс типа, который определяет интерфейс Int в класс типа, определяющего интерфейс Number . Будет выполнен поиск объявлений implicit def и выбрано то, которое возвращает наиболее близкий по иерархии тип. В нашем примере есть единственное подходящее объявление implicit def intToNumber(x: Int) .

Если компилятор не может найти имя метода, то он постарается преобразовать объект к типу, у которого этот метод есть. Подобные преобразования задаются implicit-классами. В качестве примера расширим интерфейс класса String новым методом:

implicit class TunedString(x: String)  def bang = x + ". " > "Ololo".bang //-> Ololo. 

Мы расширили интерфейс класса String без изменения самого класса и наследования. По сути мы реализовали паттерн pimp-my-library.

implicit-классы имеют ограничения:

  • должны быть определены внутри другого класса или объекта;
  • имя класса должно быть уникально в рамках его области видимости;
  • не может быть case-классом;
  • класс может принимать только один не implicit аргумент.

И наконец, если компилятор обнаружит, что не все аргументы переданы и отсутствующие аргументы объявлены как implicit, то будет выполнен поиск implicit object или implicit val. Рассмотрим этот случай на примере сортировки. Пусть у нас есть метод sort , который принимает список и объект-компаратор, определяющий порядок:

implicit val numComparator = new Comparator[Int]  def compare(oneNumber: Int, anotherNumber: Int): Int = oneNumber - anotherNumber > def sort[T](l: List[T])(implicit c: Comparator[T]): List[T] = . sort(List(3,2,4)) // не передаем c

Выше мы не передали в функцию последний аргумент, компилятор сам подставит вместо него implicit val numComparator . В то же время, если мы изменим тип компаратора на implicit val personNameComparator = new Comparator[String] , то его класс типа не совпадет с тем, который ищет компилятор и компаратор не сможет быть использован. В результате возникнет ошибка компиляции. Кроме этого implicit аргументы имеют следующие особенности:

  • могут быть переданы явно, как обычные аргументы;
  • они всегда должны находиться после обычных аргументов;
  • должны находиться в отдельных списках аргументов.

implicit аргументы позволяют упростить код, убрав из него технические подробности вроде передачи служебных объектов. Но, что более важно, они уменьшают связанность кода. Мы в любой момент можем добавить или убрать (если ранее не передавались явно) impliced аргументы и это потребует минимальных усилий.

Поиск implicit val, imlicit object, implicit class, implicit def происходит в следующем порядке:

  • implicit объявления в текущей области видимости
  • точно заданные операции import
  • заданные шаблоном ( _ ) операции import
  • объекты-компаньоны
  • области видимости каждого из аргументов метода
  • области видимости аргумента типа
  • если текущий тип вложенный, то в области видимости родительского типа

Заключение

В этой статье мы свели все типы к классам и увидели как мощная система типизации может помочь в правильной декомпозиции программ. Скудная типизация языков прошлого заставила некоторых программистов думать, что статическая типизация зло и искать пути ее обхода. Другие программисты выдумали целые справочники костылей-паттернов, призванных обойти ограничения системы типов. На самом же деле грамотно спроектированная система типизации облегчает жизнь программисту. Мы увидели насколько полезной может быть статическая система типов, связанная с ОО иерархией классов. С помощью умного компилятора мы можем лаконично описать хорошо декомпозированную и масштабируемую программу, избежав при этом кучи ошибок.

В следующей статье мы подробно поговорим о списках, так как они являются базовой структурой данных в функциональном программировании.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *