Структуры данных и их типы

Одна из базовых единиц любого языка программирования — символ. Символом тра­ди­ци­онно называется последовательность букв, цифр и специальных знаков ограниченной или неограниченной длины. В некоторых языках строчные и прописные буквы раз­ли­ча­ют­ся, в некоторых нет. Так в Lisp’е различия между строчными и заглавными буквами нет, а в Haskell’е есть.

Символы чаще всего выступают в качестве идентификаторов — имен констант, пе­ре­мен­ных, функций. Значениями же констант, переменных и функций являются ти­пи­зи­ро­ван­ные последовательности знаков. Так значением числовой константы не может быть стро­ка из букв и т.п. В функциональных языках существует базовое понятие — атом. В реализациях атомами называются символы и числа, причем числа могут быть трех видов: целые, с фиксированной и с плавающей точкой.

Следующим понятием функционального программирования является список. В аб­с­т­рак­тной математической нотации использовались символы [], которые также ис­поль­зу­ют­ся в Haskell’е. Но в Lisp’е используются обычные "круглые" скобки — (). Элементы спис­ка в Lisp’е разделяются пробелами, что не очень наглядно, поэтому в Haskell’е было ре­ше­но ввести запятую для разделения. Таким образом, список [a, b, c] будет правильно за­пи­сан в синтаксисе Haskell’а, а в нотацию Lisp’а его необходимо перевести как (a b c). Од­на­ко создатели Lisp’а пошли еще дальше в своей изощрённости. Допускается ис­поль­зо­вать точечную запись для организации пары, поэтому приведенный выше список можно за­писать как (a.(b.(c.NIL))).

Списочные структуры в Lisp’е и Haskell’е описываются в соответствии с нотацией — зак­лючение одного списка в другой. При этом в нотации Lisp’а сделано послабление, т.к. пе­ред скобкой внутреннего списка можно не ставить пробел.

Как говорилось во вводной лекции, типы данных в функциональных языках оп­ре­де­ля­ют­ся автоматически. Механизм автоматического определения типа встроен и в Haskell. Од­нако в некоторых случаях необходимо явно указывать тип, иначе интерпретатор может за­путаться в неоднозначности (в большинстве случаев будет выведено сообщение об оши­б­ке или предупреждение). В Haskell’е используется специальный символ — :: (два дво­е­то­чия), который читается как "имеет тип". Т.е. если написать:

5 :: Integer

Это будет читаться: "Числовая константа 5 имеет тип Integer (Целое число)".

Однако Haskell поддерживает такую незаурядную вещь, как полиморфные типы, или шаб­лоны типов. Если, например, записать [a], то это будет обозначать тип "список из ато­мов любого типа", причем тип атомов должен быть одинаковым на протяжении всего спис­ка. Т.е. списки [1, 2, 3] и [‘a’, ‘b’, ‘c’] будут иметь тип [a], а список [1, ‘a’] будет дру­го­го типа. В этом случае в записи [a] символ a имеет значение типовой переменной.