Pull to refresh

Введение в OCaml: Типы данных и сопоставление [3]

Programming *
Translation
Original author: www.ocaml-tutorial.org
[прим. пер.: продолжение перевода. первая часть, вторая часть]

Связные списки


В OCaml, так же как в Perl, есть встроенная на уровне языка поддержка списков. Все элементы списка должны быть одного типа. Для определения типа используется выражение:

[1; 2; 3]

Обратите внимание: точка с запятой, а не запятая.

[] означает пустой список.

У списка есть голова (первый элемент) и хвост (остальные элементы, кроме головы). Голова — элемент. Хвост — список. В вышеприведённом примере голова — целое число 1, а хвост — список [2; 3].

Альтернативной формой записи является использование оператора конструирования (cons) в форме head :: tail. Нижеприведённые строки полностью эквивалентны друг другу.

[1; 2; 3]
1 :: [2; 3]
1 :: 2 :: [3]
1 :: 2 :: 3 :: []

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

Тип данных для связного списка


Тип данных для связного списка целых будет int list; общий тип для связного списка объектов типа foo будет foo list.

Это подразумевает, что все элементы списка должны быть одного типа. Но мы можем использовать полиморфные списки (например, 'a list), которые очень полезны при написании общий функций, которые работают с «списком чего-либо». (Обратите внимание, 'a list не означает, что элементы списка могут быть разного типа, вы по-прежнему не можете, например, сделать список состоящий из смеси целых чисел и строк. Эта форма записи означает «список элементов любого типа, но одного и того же типа»).

Хорошим примером является функция length определённая в модуле List. Не имеет значения, содержит ли список целые числа, или строки, или объекты, или маленьких пушистых зверьков, функция List.length может быть использована для любого типа списка. Таким образом тип List.lenght:

List.length : 'a list -> int


Структуры


В Си и Си++ есть концепция struct (сокращение для structure). Java имеет классы, которые могут использоваться аналогичным образом, хотя их использование требует более кропотливой работы.

Взглянем на простую структуру на Си:

struct pair_of_ints {
  int a, b;
};

Простейшим эквивалентом в OCaml будет кортеж (touple), такой как (3,4), у которого типа int * int. В отличие от списков кортежи могут содержать элементы разных типов, так что, например, (3, «helo», 'x') имеет тип int * string * char.

Несколько более сложным вариантом реализации Си'шной структуры будет использование записи (record). Записи, подобно структурам на Си, позволяют вам использовать именованные элементы. Кортежи не имеют именованных элементов, но в замен хранят порядок вхождения элементов в кортеж. Вот эквивалент структуре на Си с использованием записей:

type pair_of_ints = { a : int; b : int };;

Вышеприведённая строка определяет тип, а ниже мы действительно создаём объект такого типа:

{ a=3; b=5 }

Заметьте, что мы использовали ":" в определении типа и "=" в момент создания объекта заданного типа.

Вот несколько примеров для верхнего уровня (toplevel):
# type pair_of_ints = { a : int; b : int };;
type pair_of_ints = { a : int; b : int; }
# {a=3; b=5};;
- : pair_of_ints = {a = 3; b = 5}
# {a=3};;
Some record field labels are undefined: b

OCaml запрещает оставлять элементы записи неопределёнными.

Варианты (квалифицированные объединения и перечисления)


Тип объектов «квалифицированное объединение» в Си не существует, хотя в gcc есть некоторая его поддержка. Вот пример того, как часто реализуют квалифицированное объединение в Си:

struct foo {
  int type;
#define TYPE_INT 1
#define TYPE_PAIR_OF_INTS 2
#define TYPE_STRING 3
  union {
    int i;        // If type == TYPE_INT.
    int pair[2];  // If type == TYPE_PAIR_OF_INTS.
    char *str;    // If type == TYPE_STRING.
  } u;
};

Как видно, это не слишком приятное зрелище. И вообще, не слишком-то безопасное: программист может использовать значение u.i в тот момент, когда структура содержит строку. И компилятор тут не поможет проверить, что все возможные значения были проверены внутри выражения switch (конкретно эта проблема частично решается использованием enum). Программист может забыть выставить значение поля type, что приведёт к всякого рода забавам и игрищам с жуками. Да и громоздко всё это.

Вот элегантный и компактный вариант на OCaml:

type foo = Nothing | Int of int | Pair of int * int | String of string;;

Это определение типа. Первая часть каждого участка, ограниченного | называется конструктором. Она может называться как угодно, однако должна начинаться с большой буквы. Если конструктор может быть использован для определения значения, за ним следует of part, где type всегда начинается с маленькой буквы. В примере выше Nothing — это константа, а все остальные конструкторы используются с значениями.

Для реального создания пишется следующее:

Nothing
Int 3
Pair (4, 5)
String "hello"
     &c.

Каждое выражение из примера выше имеет тип foo.

Обратите внимание: of используется в определении типа, но НЕ в создании элементов заданного типа.

Продолжая. Простое перечисление на Си определяется как

enum sign { positive, zero, negative };

Оно же может быть записано на OCaml следующим образом:

type sign = Positive | Zero | Negative;;


Рекурсивные варианты (для деревьев)


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

type binary_tree = Leaf of int | Tree of binary_tree * binary_tree;;


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

Leaf 3
Tree (Leaf 3, Leaf 4)
Tree (Tree (Leaf 3, Leaf 4), Leaf 5)
Tree (Tree (Leaf 3, Leaf 4), Tree (Tree (Leaf 3, Leaf 4), Leaf 5))


Параметризованные варианты


Двоичное дерево в примерах выше хранило целое число в каждом листе. Но что, если мы хотим описать форму двоичного дерева, а уточнение того, что именно хранить в листьях мы оставим на потом? Мы можем делать это с использованием параметризованных (полиморфных) вариантов, примерно вот так:

type 'a binary_tree = Leaf of 'a | Tree of 'a binary_tree * 'a binary_tree;;

Это общий тип. Точный тип, который хранит целые в каждом листе называется int binary_tree. Аналогично, точный тип, который хранит строки в каждом листе называется string binary_tree. В следующем примере мы определим типы некоторых экземпляров в верхнем уровне и позволим системе выведения типов показать их типы для нас:

# Leaf "hello";;
- : string binary_tree = Leaf "hello"
# Leaf 3.0;;
- : float binary_tree = Leaf 3.


Заметим, что имя типа записывается в обратном порядке. Сравните это с именем типов для списков, например, int list.

На самом деле, это не совпадение, что a' list тоже записывается в таком же «в обратном порядке». Списки — это всего лишь параметризованные варианты с вот таким вот (немного странным) определением:

 type 'a list = [] | :: of 'a * 'a list   (* это не настоящий код на OCaml *)

Хотя это не совсем полное определение. Вот существенно более точное определение:

# type 'a list = Nil | :: of 'a * 'a list;;
type 'a list = Nil | :: of 'a * 'a list
# Nil;;
- : 'a list = Nil
# 1 :: Nil;;
- : int list = :: (1, Nil)
# 1 :: 2 :: Nil;;
- : int list = :: (1, :: (2, Nil))

Вспомним, что мы говорили ранее — списки могут быть записаны двумя методами: либо с небольшим количеством синтаксического сахара [1; 2; 3], либо более формально, как 1 :: 2 :: 3 :: []. Если мы посмотрим на определение a' list выше, то мы увидим объяснение формальной записи.

Списки, структуры, варианты — итог


Имя в OCaml Определение типа примера Использование примера
list int list [1; 2; 3]
tuple int * string (3, «hello»)
record type pair = { a: int; b: string } { a = 3; b = «hello» }
variant type foo = Int of int
| Pair of int * string
Int 3
variant type sign = Positive | Zero
| Negative
Positive
Zero
parameterized
variant
type 'a my_list = Empty
| Cons of 'a * 'a my_list
Cons (1, Cons (2, Empty))


Сопоставление с образцом (для типов данных)


Одна из Реально Клёвых Фич функциональных языков программирования — это способность разбирать структуры и делать сопоставление с образцом (pattern matching) для данных. Это не совсем «функциональная» фича — мы можем представить себе некое подобие вариации на Си, которая позволит делать подобное, но в любом случае, это Клёвая Фича.

Начнём с реальной задачи для программирования: Я хочу иметь средство записи для математических выражений, таких как n * (x + y) и выполнять символическое умножение для того, чтобы из выражения выше получить n * x + n * y.

Давайте определим тип этих выражений:

type expr = Plus of expr * expr        (* means a + b *)
          | Minus of expr * expr       (* means a - b *)
          | Times of expr * expr       (* means a * b *)
	  | Divide of expr * expr      (* means a / b *)
          | Value of string            (* "x", "y", "n", etc. *)
	  ;;

Выражение вида n * (x + y) запишется как:

Times (Value "n", Plus (Value "x", Value "y"))


Теперь напишем функцию, которая выведет (Value "n", Plus (Value "x", Value "y")) как нечто, более похожее на n * (x+y). Для этого мы напишем две фунции, одна из которых конвертирует выражение в красивую строку и одну, которая выводит её (причина разделения в том, что возможно, мне нужно будет записать эту же строку файл и я не хочу повторять всю функцию ради этого).

let rec to_string e =
  match e with
    Plus (left, right)   -> "(" ^ (to_string left) ^ " + " ^ (to_string right) ^ ")"
  | Minus (left, right)  -> "(" ^ (to_string left) ^ " - " ^ (to_string right) ^ ")"
  | Times (left, right)  -> "(" ^ (to_string left) ^ " * " ^ (to_string right) ^ ")"
  | Divide (left, right) -> "(" ^ (to_string left) ^ " / " ^ (to_string right) ^ ")"
  | Value v -> v
  ;;

let print_expr e =
  print_endline (to_string e);;

(Примечание: оператор ^ используется для объединения строк)

А вот функция вывода на экран в работе:
# print_expr (Times (Value "n", Plus (Value "x", Value "y")));;
(n * (x + y))


Общая форма для сопоставления с образцом:
match object with
  pattern    ->  result
| pattern    ->  result
    ...

Левая часть сопоставления с образцом может быть простой (как в случае to_string в примере выше), так и сложной, с вложениями. Следующий пример — это наша функция для умножения выражений в форме n * (x + y) или в форме (x + y) * n. Для этого мы будем использовать вложенные образцы:

let rec multiply_out e =
  match e with
    Times (e1, Plus (e2, e3)) ->
      Plus (Times (multiply_out e1, multiply_out e2),
            Times (multiply_out e1, multiply_out e3))
  | Times (Plus (e1, e2), e3) ->
      Plus (Times (multiply_out e1, multiply_out e3),
            Times (multiply_out e2, multiply_out e3))
  | Plus (left, right) -> Plus (multiply_out left, multiply_out right)
  | Minus (left, right) -> Minus (multiply_out left, multiply_out right)
  | Times (left, right) -> Times (multiply_out left, multiply_out right)
  | Divide (left, right) -> Divide (multiply_out left, multiply_out right)
  | Value v -> Value v
  ;;

Вот оно в работе:

# print_expr (multiply_out (Times (Value "n", Plus (Value "x", Value "y"))));;
((n * x) + (n * y))

Как работает multiply_out? Ключевой момент — первые два образца. Первый образец — это Time (e1, Plus (e2, e3)), который сопоставляет выражения вида e1 * (e2 + e3). Теперь взглянем на правую часть первого сопоставления с образцом и убедимся, что это экивалент (e1 * e2) + (e1 * e3).

Второй образец делает то же самое, за исключением использования выражений вида (e1 + e2) * e3.

Оставшиеся образцы не меняют формы выражения, но, по сути, они рекурсивно вызывают multiply_out на подвыражениях. Это обеспечивает умножение всех подвыражений (если вы хотите умножить только верхний уровень выражения, то вам следует заменить все оставшиеся образцы простым правилом e -> e).

Можем ли мы сделать обратное? (Факторизацию общей части подвыражений?) Разумеется! (хоть это и слегка сложнее). Нижеприведённая версия работает только для верхнего уровня выражений. Разумеется, вы можете её расширить для всех уровней выражения (и для более сложных случаев):

let factorize e =
  match e with
    Plus (Times (e1, e2), Times (e3, e4)) when e1 = e3 -> Times (e1, Plus (e2, e4))
  | Plus (Times (e1, e2), Times (e3, e4)) when e2 = e4 -> Times (Plus (e1, e3), e4)
  | e -> e
  ;;


# factorize (Plus (Times (Value "n", Value "x"), Times (Value "n", Value "y")));;
- : expr = Times (Value "n", Plus (Value "x", Value "y"))

Функция факторизации демонстрирует нам ещё несколько возможностей языка. Вы можете добавить хранителей в каждое сопоставление с образцом. Хранитель — это условие, которое следует за сопоставлением. Сопоставление с образцом срабатывает только если есть соответствие образцу И условие в when выполнено.

match object with
  pattern    [ when condition ]   ->  result
  pattern    [ when condition ]   ->  result
    ...

Вторая возможность языка — это оператор =, который проверяет «структурное соответствие» между выражениями. Это означает, что он проходит рекурсивно в каждое выражение и проверяет их соответстве на всех уровнях.

OCaml может проверять на этапе компиляции, что вы покрыли все возможные случаи в ваших шаблонах. Я изменил определение типа expr добавив в него вариант Product:
type expr = Plus of expr * expr        (* means a + b *)
          | Minus of expr * expr       (* means a - b *)
          | Times of expr * expr       (* means a * b *)
	  | Divide of expr * expr      (* means a / b *)
	  | Product of expr list       (* means a * b * c * ... *)
          | Value of string            (* "x", "y", "n", etc. *)
	  ;;

Затем я попытался скопмилировать функцию to_string не дополнив её. OCaml выдал следующее предупреждение:
Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Product _
Tags:
Hubs:
Total votes 23: ↑21 and ↓2 +19
Views 4.1K
Comments Comments 14