Теория Основные понятия и типы данных

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

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

5

True

'a'

(1,True)

[1,2,3,4,5]

Очевидно, что сложно назвать значением следующие конструкции:

5+6

x-1

Integer

Если рассмотреть различные пары значений, то можно обнаружить, что некоторые из них нам кажутся интуитивно более "похожими" друг на друга, чем другие. Например, значения 1 и 2 гораздо более похожи друг на друга, чем значения 1 и "one". Любой программист сразу скажет, что значения 1 и 2 принадлежат одному и тому же типу Integer. Типом можно назвать множество значений (как очень маленькое, так и потенциально бесконечное), которые в некотором смысле похожи все друг на друга, как братья.

А если более конкретно? Чем значение 1 похоже на значение 2 и отличается от значения "one"? Да тем, что к значению 1 можно прибавить 10, а к значению "one" – нельзя. Чуть позже мы увидим, как это проявляется формально, а пока просто констатируем: тип – это множество значений одной природы, похожих тем, какие операции к ним всем применять можно, а какие нельзя.

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

5 :: Integer

5 :: Int

5 :: Float

True :: Bool

'a' :: Char

Типы Integer и Int отличаются длиной: значения типа Int имеют ограниченную длину, а вот тип Integer может содержать целое число с любым количеством цифр. Если вы так и не поняли, к какому типу принадлежит число 5, то я вам скажу – ко всем этим трем сразу. А еще оно является, к тому же, рациональным и комплексным.

Следующее очень важное понятие – это переменная. В обычных языках программирования под переменной понимают определенную область памяти, имеющую определенное имя и текущее значение, которое может меняться в процессе выполнения программы. В математике вместо слова "переменная" иногда используют слово "неизвестная": например, в уравнении sin(x) = x, говоря о неизвестном "x" имеют в виду, что вместо x можно подставлять разные числа, и какие-то из них удовлетворяют уравнению, а какие-то нет.

В языке Haskell нет переменных, и если x получает, или имеет, значение 1, то это значение не изменяется на всем протяжении жизни этого x. Правильнее в этом случае говорить просто об "имени" x, которое имеет определенное неизменное значение. Раз значение имени x не меняется на протяжении жизни этого x, а любое значение имеет тип, то и любое имя x имеет неизменный тип, например:

x :: Int

Давайте сразу договоримся: когда мы будем произносить слово "переменная" в применении к языку Haskell, мы будем иметь в виду именно эти неизменные x, y, z – за которыми скрывается какое-то значение, изменить которое мы не в состоянии.

Заметки на полях: Haskell довольно строго регламентирует регистр имен: все они – и "переменные", и функции (а по сути это одно и то же) должны начинаться с строчных букв, и могут содержать буквы, цифры и одинарную кавычку. Прописные зарегистрированы за типами данных и за специфическими значениями вроде True, False – но об этом потом.

Когда имя x получает свое значение? Некоторые имена получают свои значения, можно сказать, при сотворении мира запуске программы. Если у вас в программе написано: pi=3.1415, то имя pi получает свое значение однажды и навсегда. А если у вас есть функция tg x = sin x / cos x, то имя x рождается и получает значение каждый раз при вызове этой функции (уничтожаясь при завершении функции), и каждый раз оно может быть разным – но изменить его внутри функции мы не можем.

Выражение, неформально говоря – это какая-то конструкция, которую в отличие от значения можно "упростить", "дальше вычислить", или вот еще термин – "редуцировать". Например, выражение 4+5 можно редуцировать до значения 9, а выражение (4+5)*2 можно упростить до выражения 9*2, которое, в свою очередь, упростить до значения 18. Этот факт мы будем отображать следующим образом:

4+5 → 9

(4+5)*2 → 9*2 → 18

(x-1)^2 + (x+1)^2 → x^2+2*x+1 + x^2-2*x+1 → 2*x^2+2

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

Из простых типов данных конструируются сложные, к которым относят список, кортеж и функцию.

Списки

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

[1,3,4,2] :: [Integer]

['h','e','l','l','o'] :: [Char]

[[1,2],[],[3,1]] :: [[Integer]]

Обратите внимание, из типа выражения сразу видно, что это список. Если тип какого-то выражения есть [SomeType], то мы имеем дело со списком значений типа SomeType, даже если SomeType в свою очередь есть что-то сложное – опять список, кортеж, список кортежей, кортеж списков или вообще функции:

[sin, cos] :: [Float -> Float]

[sin 5, cos 5] :: [Float]

Обратите внимание, в первом списке мы имеем дело со списком функций, в котором лежат синус и косинус, сами по себе, как функции. А во втором случае у нас банальный список значений типа Float.

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

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

"hello" :: String

"hello" == ['h','e','l','l','o']