Списки в языке ML
> [1,2,3];
val it = [1,2,3] : int list
Язык ML определяет тип этого списка как int. Строгая типизация в ML диктует, что все элементы списка должны иметь одинаковый тип. Рассмотрим пример структуры, нарушающей это соглашение и смешивающей типы элементов в списке:
> [1,2,3.1];
Error: operator and operand don't agree [literal] operator domain: int * int list operand: int * real list in expression:
2 :: 3.1 :: nil
При необходимости смешать данные разных типов следует использовать кортеж:
Сообщение об ошибке, сгенерированное в предыдущем примере, подсказывает нам правила конструирования списков в ML, которые похожи на правила конструирования списков в Scheme.
Здесь операция :: соответствует операции cons в Scheme и создает список из элемента, стоящего слева от знака операции (который становится головой списка), и предыдущего уже созданного списка, стоящего справа от значка операции (который становится хвостом списка). К примеру:
Обратите внимание, что запись операции :: содержит запись переменной 'a, поскольку операция :: должна применяться к списку, содержащему величины любого типа. Таким образом, :: — это функция, которая из элемента любого типа 'a и любого списка из элементов того же типа 'a конструирует список такого же типа 'a.
В языке ML каждый список конструируется последовательностью применения операций :: , как показано в следующем фрагменте:
Здесь [] обозначает пустой список, который также может записываться посредством ключевого слова nil.
Язык ML — функциональный подход со статической типизацией |
635 |
Язык ML содержит операции, соответствующие car и cdr из Scheme, правда, называются они здесь hd и tl (для головы head и хвоста tail). К примеру:
В ML эти функции применяют редко, в отличие от их аналогов в Scheme, поскольку ML предлагает более удобный механизм сопоставления с паттерном. В ML для выделения головы и хвоста списка L достаточно записать для списка h::t. Среда языка ML выделит голову как h, а хвост как t (в соответствии с сопоставлением паттерна для списка L). Если L пуст, паттерн не сопоставится и будет сгенерировано подобное предостережение:
Warning: binding not exhaustive h :: t = ... val h = 1 : int val t = [2,3] : int list Обычно сопоставление с паттерном используется в определениях функций и выражениях выбора. Например, функцию append для списка можно записать в следующей форме:
Это эквивалентно следующему определению, использующему выражение case:
Сопоставление с паттерном может использоваться практически во всех определениях функций, где требуется анализ выбора; оно может устранить большинство использований условных выражений. К примеру, рекурсивная функция факториала может быть переписана на основе сопоставления с паттерном следующим образом: fun fact 0 = 1 | fact n = n * fact (n - 1); Здесь второй паттерн — переменная n — не сопоставляется ни с чем, но его позиция как второго паттерна неявно свидетельствует, что он не должен быть равен нулю; если же имеет место обратный факт, то должен сопоставляться первый паттерн (целый литерал 0). Паттерны в ML могут использовать символы подстановки, записываемые как знаки подчеркивания. Символы подстановки являются паттернами, которые сопоставляются с чем угодно, независимо от содержания. К примеру, можно определить собственную версию функции hd: fun hd (h::_) = h; На самом деле, это определение инициирует предупреждение («сопоставление неполное»), поскольку здесь не определены действия hd в случае пустого списка. В лучшем определении предусмотрим и этот вариант: fun hd (h::_) = h | hd [] = raise Empty; |
636 |
Глава 20. Функциональное программирование |