Современные информационные технологии/ 2. Вычислительная техника и
программирование
Бурлибаева
Ш.М., Каргабаева Д.Т.
Списки
в функциональном языке Haskell
Список в функциональном языке Haskell - это структура данных, содержащая
произвольное (в т.ч. и бесконечное) количество элементов. Чтобы задать список в
Haskell, необходимо в квадратных скобках перечислить его элементы через
запятую. Все эти элементы должны принадлежать одному и тому же типу. Тип списка
с элементами, принадлежащими типу a, обозначается как [a]. В списке может не
быть ни одного элемента. Пустой список обозначается как []. Оператор :
(двоеточие) используется для добавления элемента в начало списка. Его левым
аргументом должен быть элемент (который называется головой списка), а правым — список (хвост списка):
Prelude>1:[2,3]
[1,2,3] ::
[Integer]
Prelude>’5’:[’1’,’2’,’3’,’4’,’5’]
[’5’,’1’,’2’,’3’,’4’,’5’]
:: [Char]
Prelude>False:[]
[False] :: [Bool]
Оператор (:) ассоциативен вправо. Элементами списка
могут быть любые значения — числа, символы, кортежи, другие списки и т.д.
Prelude>[(1,’a’),(2,’b’)]
[(1,’a’),(2,’b’)]
:: [(Integer,Char)]
Prelude>[[1,2],[3,4,5]]
[[1,2],[3,4,5]] :: [[Integer]]
Для работы со списками в языке Haskell
существует большое количество функций. Рассмотрим только некоторые из них.
-
Функция head возвращает
первый элемент списка.
-
Функция tail возвращает
список без первого элемента.
-
Функция length
возвращает длину списка.
Функции head и tail определены для
непустых списков. При попытке применить их к пустому списку интерпретатор
сообщает об ошибке. Примеры работы с указанными функциями:
Prelude>head [1,2,3]
1 :: Integer
Prelude>tail [1,2,3]
[2,3] :: [Integer]
Prelude>tail [1]
[] :: Integer
Prelude>length
[1,2,3]
3 :: Int
Обратите внимание, что результат функции
length принадлежит типу Int, а не типу Integer. Для соединения (конкатенации)
списков в Haskell определен оператор ++.
Prelude>[1,2]++[3,4]
[1,2,3,4] :: Integer
Рассмотрим примеры построения списков:
1.
Построить список
нечетных натуральных чисел
sp_nech
:: Integer -> [Integer]
sp_nech
0 = []
sp_nech
n = sp_nech (n-1) ++ [n]
Результат:
2.
Построить список треугольных чисел.
(n-ое треугольное число
tn равно количеству одинаковых монет, из
которых можно построить равносторонний треугольник, на каждой стороне которого укладывается n
монет. Нетрудно убедиться, что t1
= 1 и tn = n + tn−1)
sp_tr_ch
:: Integer -> [Integer]
tr_ch 1
= 1
tr_ch
(n) = n+tr_ch (n-1)
sp_tr_ch
0 = []
sp_tr_ch
n = sp_tr_ch (n-1) ++ [tr_ch (n)]
3.
Построить
список пирамидальных чисел. (n-е
пирамидальное число pn равно количеству одинаковых шаров, из которых
можно построить правильную пирамиду
с треугольным основанием, на каждой стороне
которой укладывается n шаров.
Нетрудно убедиться, что p1 = 1 и pn = tn + pn−1)
sp_pir
:: Integer -> [Integer]
pir 1 =
1
pir n =
n + pir(n-1)
p 1 = 1
p n =
pir (n) + p(n-1)
sp_pir
0 = []
sp_pir
n = sp_pir (n-1) ++ [p(n)]
Результат:
4.
Из списка
удалить элементы,
стоящие на чётных местах
Результат:
Литература
1.
С.В.
Зыков. Введение в теорию программирования.
Функциональный подход
2.
Л.В.
Городняя. Основы функционального
программирования
3.
С. Сильван. Сильные стороны языка Haskell