Что такое типы строк? Являются ли они алгебраическими типами данных?

Ответ 1

Полиморфизм строк является одной из форм полиморфизма. OCaml предоставляет два вида полиморфизма - параметрические и рядные, а также отсутствие двух других - ad hoc и включение (aka subtyping) ¹.

Прежде всего, что такое полиморфизм? В контексте систем типов полиморфизм позволяет одному термину иметь несколько типов. Проблема здесь в том, что сам тип слова сильно перегружен в сообществе компьютерных наук и программирования. Поэтому, чтобы свести к минимуму путаницу, позвольте просто снова ввести его здесь, чтобы быть на одной странице ². Тип термина обычно обозначает некоторую аппроксимацию семантики. Там, где семантика может быть такой же простой, как набор значений, оснащенных набором операций или чем-то более сложным, например эффектами, аннотациями и произвольными теориями. В общем, семантика обозначает множество всех возможных поведений члена. Система типов обозначает набор правил, который допускает некоторые языковые конструкции и запрещает другие на основе их типов. I.e., он проверяет правильность составов терминов. Например, если на языке существует конструктор приложения-функции, система типов будет использовать приложение только для тех аргументов, которые имеют типы, соответствующие типам параметров. И то, где полиморфизм вступает в игру. В системах с мономорфным типом это совпадение может быть только один к одному, т.е. Буквальный. Полиморфные системы предоставляют механизмы для указания некоторого регулярного выражения, которое будет соответствовать семейству типов. Таким образом, различные виды полиморфизма - это просто разные типы регулярных выражений, которые вы можете использовать для обозначения семейства типов.

Теперь рассмотрим различные виды полиморфизма с этой точки зрения. Например, параметрический полиморфизм подобен точке в регулярных выражениях. Например, 'a list - . list - это означает, что мы точно сопоставляем list, а параметр типа list может быть любым типом. Полиморфизм строк является оператором звезды, например, <quacks : unit; ..> является таким же, как <quacks : unit; .*>. И это означает, что он соответствует любому типу, который quacks и делает что-то еще ³. Говоря об номинальном подтипинге, в этом случае у нас есть номинальные классы (классы символов в регулярном выражении), и мы указываем семейство типов с именем их базового класса. Например, duck выглядит как [:duck:]*, и любое значение, которое правильно зарегистрировано как член класса, совпадает с этим типом (через наследование класса и новый оператор) ⁴. Наконец, ad-hoc-полиморфизм на самом деле также является номинальным и сопоставляет классы символов в регулярных выражениях. Основное различие здесь заключается в том, что понятие типа в ad-hoc-полиморфизме применяется не к значению, а скорее к названию. Таким образом, имя, например имя функции или оператор +, может иметь несколько определений (реализаций), которые должны быть статически зарегистрированы с использованием какого-либо языкового механизма (например, перегрузка оператора, реализация метода и т.д.). Таким образом, ad-hoc-полиморфизм является лишь особым случаем номинального подтипирования.

Теперь, когда мы понятны, мы можем обсудить, что дает нам полиморфизм строк. Полиморфизм строк также известен как структурный подтипирование и утиная типизация. В общем, как мы обсуждали выше, это позволяет нам указывать тип как "что-либо, что может помешать", а не "что-либо, что реализует интерфейс IDuck". Итак, вы можете, конечно, сделать то же самое с номинальной типизацией, указав интерфейс утки и явно зарегистрировать все реализации как экземпляры этого интерфейса, используя некоторые механизмы inherit или implements. Но главная проблема здесь в том, что ваша иерархия запечатана, т.е. Вам нужно изменить свой код для регистрации реализации во вновь создаваемом интерфейсе. Это нарушает принцип открытия/закрытия и затрудняет повторное использование кода. Еще одна проблема с номинальным подтипированием заключается в том, что, если ваша иерархия не образует решетку (т.е. Для любых двух классов всегда существует минимальная верхняя граница), вы не можете реализовать вывод типа на нем ⁵.

¹⁾ Однако OCaml предоставляет классы с наследованием и понятием подтипа, он по-прежнему не является подтиповым полиморфизмом в соответствии с общим определением, поскольку он не является номинальным. Из оставшейся части ответа должно быть ясно.

²⁾ Я просто фиксирую терминологию, я не утверждаю, что мое определение правильное. Многие люди думают, что тип обозначает представление значения, и исторически это правильно.

³⁾ Возможно, лучшее регулярное выражение будет <.*; quacks : unit; .*>, но я думаю, что у вас есть идея.

⁴⁾Таким образом, OCaml не имеет подтипирования полиморфизма, хотя имеет понятие подтипа. Когда вы укажете тип, он не будет соответствовать подтипу, он будет соответствовать только буквально, и вам нужно использовать явный оператор повышения, чтобы значение типа T применимо в контексте, где ожидается super(T). Итак, хотя в OCaml есть подтипирование, это не о полиморфизме.

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

Ответ 2

Типы строк странны. И очень мощный.

Типы строк используются для реализации объектов и полиморфных вариантов в OCaml.

Но во-первых, вот что мы не можем делать без типов строк:

type t1 = { a : int; b : string; }
type t2 = { a : int; c : bool; }

let print_a x = print_int x.a

let ab = { a = 42; b = "foo"; }
let ac = { a = 123; c = false; }

let () =
 print_a ab;
 print_a ac

Этот код, конечно, откажется компилировать, потому что print_a должен иметь уникальный тип: либо t1, либо t2, но не оба. Однако в некоторых случаях нам может потребоваться точное поведение. Для каких типов строк. Это то, что они делают: более "гибкий" тип.

В OCaml существует два основных типа использования типов строк: объекты и полиморфные варианты. В терминах алгебры объекты дают вам "продукт строки" и полиморфные варианты "сумма строки".

Что нужно знать о типах строк, так это то, что вы можете использовать некоторые подтипы для объявления и очень противостоять интуитивно понятной типизации и семантике (особенно в классах case).

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

Ответ 3

Я завершаю отличный ответ PatJ с его примером, написанным с использованием классов.

Учитывая классы ниже:

class t1 = object
  method a = 42
  method b = "Hello world"
end

class t2 = object
  method a = 1337
  method b = false
end

И объекты ниже:

let o1 = new t1
let o2 = new t2

Вы можете написать следующее:

let print_a t = print_int t#a;;
val print_a : < a : int; .. > -> unit = <fun>

print_a o1;;

42
- : unit = ()

print_a o2;;

1337
- : unit = ()

Вы можете увидеть тип строки в подписи print_a. < a : int; .. > - это тип, который буквально означает "любой объект, у которого есть хотя бы метод a с сигнатурой int".