понедельник, 9 февраля 2015 г.

Хотите 2 + 2 = 5 в haskell?

Ничего сверхъестественного. Просто
2 + 2
5
Это фрагмент сессии ghci. Чтобы получить этот результат, строкой выше я ввел
let 2 + 2 = 5
Те, кто не первый день работает с haskell, легко разберутся в смысле этого выражения. Новички, наверное, посчитают его некой волшебной синтаксической конструкцией, на низком уровне переопределяющей семантику языка. Адепты языка C++ возможно предположат, что здесь происходит перегрузка оператора +. Это неверно, поскольку в haskell нет никаких операторов в смысле C++, но уже теплее. На самом деле, здесь объявлена инфиксная функция (+) (именно так, в скобках). Ее инфиксность в данном объявлении выражается в записи ее двух аргументов (2 и 2) слева и справа. Мы могли бы записать функцию (+) в обычной форме, когда аргументы расположены справа.
let (+) 2 2 = 5
В этом случае нам пришлось записать ее полное имя с окружающими скобками, чтобы избежать синтаксической ошибки. А что если аргументы функции отличаются от двоек? У нас ведь нет определения для этого случая.
3 + 4
*** Exception: <interactive>:40:5-13: Non-exhaustive patterns in function +
Так и есть. Тогда другой вопрос. Куда делась стандартная функция (+)? А никуда не делась: она по-прежнему определена в стандартном модуле Prelude, только теперь ее определение скрыто нашим новым определением. Чтобы использовать стандартный +, нужно полностью квалифицировать имя функции (+).
2 Prelude.+ 2
4
2 Prelude.+ 3
5
Пусть наш новый + возвращает 5 на 2 + 2 и стандартное значение в других случаях. Для этого нужно определить функцию (+) следующим образом.
:{
let 2 + 2 = 5
    a + b = a Prelude.+ b
:}
Все клозы одной функции должны быть объявлены в ghci одновременно, поэтому я использовал синтаксис многострочного объявления ghci с маркерами начала :{ и конца :}. Говоря более формально, данный синтаксис позволил связать (bind) все возможные клозы и аргументы функции (+) в едином лексическом пространстве (lexical scope). Проверяем.
2 + 2
5
3 + 4
7
Еще одна проверка.
3 + 4 * 2
14
А должно быть 11! Вычисление произошло таким образом, как если бы 3 и 4 сперва сложились, а затем результат сложения (7) был умножен на 2. Ну так и есть, мы же не определили ассоциативность и приоритет нашей инфиксной функции! По умолчанию в haskell любая инфиксная функция левоассоциативна и имеет наибольший приоритет, равный 9. Давайте определим значения ассоциативности и приоритета стандартного +
:i Prelude.+
class Num a where
  (Prelude.+) :: a -> a -> a
  ...
        -- Defined in ‘GHC.Num’
infixl 6 Prelude.+
и установим их для нашего +.
:{
let 2 + 2 = 5
    a + b = a Prelude.+ b
    infixl 6 +
:}
Вот теперь результаты вычислений в инфиксных выражениях (за исключением того, что 2 + 2 = 5) должны быть верными.
3 + 4 * 2
11
Кстати, есть весьма тонкое отличие в типе стандартной функции (+) и определенной нами. Прежде всего, обратите внимание на определение стандартного (+) в выводе :i Prelude.+ выше. Оно начинается со строки class Num a where. Это нестандартная функция в том смысле, что она объявлена как метод класса Num. Класс Num предоставляет базовый интерфейс для типов, которые хотят быть похожими на числа. Вот его определение.
:i Num
class Num a where
  (Prelude.+) :: a -> a -> a
  (*) :: a -> a -> a
  (-) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a
        -- Defined in ‘GHC.Num’
instance Num Integer -- Defined in ‘GHC.Num’
instance Num Int -- Defined in ‘GHC.Num’
instance Num Float -- Defined in ‘GHC.Float’
instance Num Double -- Defined in ‘GHC.Float’
Здесь перечислены все методы, которые должен реализовать тип, который хочет быть похожим на число, а также список типов (элементы после слов instance Num), которые уже реализовали методы класса Num. А теперь посмотрим на определение нашего +.
:i (+)
(+) :: (Num a, Eq a) => a -> a -> a
        -- Defined at <interactive>:7:7
infixl 6 +
Это простая функция, поэтому ее определение начинается сразу с описания типа, который равен (Num a, Eq a) => a -> a -> a. Выражения в скобках — это ограничения на тип (type constraints), буква aпеременная типа. Вся запись означает, что наш + реализует полиморфную функцию, то есть функцию, которая принимает аргументы любого типа с условием, что он должен предоставить реализации (instances) классов, перечисленных в списке ограничений на тип. Поскольку мы не стали определять тип функции (+) вручную, компилятор вывел его за нас. В определении первого клоза функции (+) мы использовали число 5 (его тип равен Num a => a), а в определении второго клоза — функцию Prelude.+, которая тоже ограничена классом Num — отсюда ограничение Num a. А откуда ограничение на Eq a, которого нет в стандартной функции (+)? Класс Eq предоставляет интерфейс для сравнения элементов типа: функции (==) и (/=). А теперь посмотрите на образец (pattern) первого клоза функции (+), он записан в инфиксной форме как 2 + 2. Чтобы механизм сопоставления с образцом (pattern matching) мог выбрать правильный клоз, он должен уметь сравнивать аргументы с двойкой — отсюда ограничение Eq a. Но несмотря на дополнительное ограничение Eq a, наша функция (+) будет работать со всеми типами, с которыми работает Prelude.+, поскольку все типы, реализующие методы класса Num, как правило реализуют и методы класса Eq.