Техника работы со списками

В традиционных языках программирования для построения объектов, более сложных, чем элементарные числа или логические значения, используют различные встроенные механизмы для построения сложных объектов из более простых. Например, в языке Паскаль для этого применяют записи, массивы и списковые структуры, а в языках Java, C# и C++ основным механизмом построения сложных значений являются классы. Аналогом паскалевской записи в языке Haskell является кортеж, структуру которого мы уже коротко описывали выше. Правда, в отличие от Паскаля в языке Haskell поля в кортежах чаще всего не имеют имен и различаются лишь по позициям в кортеже. Имена для отдельных полей кортежа задавать и использовать можно и в языке Haskell, но эта возможность используется в Haskell сравнительно редко.

Способов построения массивов в языке Haskell нет. Тип данных Array, который определен в подключаемой библиотеке Data. Array, лишь внешне похож на привычный массив, а на самом деле его структура устроена совершенно по-другому. Причина этого состоит в том, что для привычной работы с массивом требуется, чтобы отдельные компоненты этого массива вели себя как отдельные переменные, но это плохо соответствует функциональному стилю. Зато в языке Haskell имеется один способ, позволяющий строить структуры данных произвольной степени сложности из более простых объектов, — списки.

Списки в Haskell одновременно напоминают и списковые структуры традиционных языков программирования, и обычные массивы. Список — это последовательность объектов одного и того же типа, состоящая из произвольного числа объектов (возможно, ни одного — соответствующий список называется пустым). Тип списка определяется типом его компонент и в языке Haskell обозначается [Т], где Т — тип компонентов списка. Таким образом, [Integer] будет обозначать тип списка, содержащего в качестве компонентов целые числа, а [ ([Char], Double) ] — это тип списка, компонентами которого являются кортежи из двух полей, причем первым полем в каждом кортеже будет список символов, а вторым полем — вещественное число.

Сами объекты-списки в простейшем случае задаются перечислением своих компонентов в квадратных скобках через запятую, так что, например, [ 1, 3, 4, 8 ] — это четырехкомпонентный список целых чисел (типом этого списка будет Num t=> [ t ]), а [ ([¹ р', ' i ' ], 3.14), ([¹ е¹ ],.

2.72)] — список вышеупомянутого типа [ ([Char], Double) ]. Заметим, что запись, в которой компонентами списка будут объекты разных типов, синтаксически неверна, так что, скажем, [ 3, 4, ' * ¹ ] не может служить изображением списка, поскольку из трех указанных компонент две первые — это числа, а третья — символ.

Отметим два полезных сокращения, использующихся для записи списков. Во-первых, список, состоящий из символов, можно записать в виде строки, заключив составляющие его символы в двойные кавычки. Например, строка «Haskell» обозначает в программе список из семи символьных значений, и такая запись полностью эквивалентна расширенной записи: [ ¹ Н ', 'a¹, 's', ' k', ' е', ' 1', '1']. Для списков символов в языке также есть специальный идентификатор типа — String, так что его можно использовать в любом месте программы вместо [Char].

Таким образом, один из примеров предыдущего абзаца можно записать так: список [(«pi», 3.14), («е^п, 2.72)] является значением типа.

[ (String, Double)].

Второе удобное сокращение или даже, скорее, средство построения списков — это задание списка чисел, образующих арифметическую прогрессию. Если шаг прогрессии равен единице, то можно указать только первый и последний элементы списка, разделив их символом из двух точек. Так, [1. .10] обозначает список из 10 последовательных натуральных чисел от 1 до 10. Если шаг прогрессии не равен единице, то указывают два первых элемента списка и последний элемент. Таким образом, изображение списка [ 3, 5.. 11 ] задает список из пяти целых чисел 3, 5, 7, 9 и 11. Отметим, что эта запись может использоваться и для задания списков с числом элементов, неизвестным в момент написания программы. Например, изображение [ 1.. п] может применяться для создания списка первых натуральных чисел от единицы до текущего значения п, которое в разных ситуациях при исполнении программы может быть различным. Комбинировать в изображении списка прогрессию с отдельными элементами, не входящими в прогрессию, нельзя. Например, запись [3, 5. .13, 14] будет некорректной.

Следует быть осторожным при составлении арифметической прогрессии из вещественных чисел. Вычисления в вещественных числах происходят приближенно, так что в языке считается, что заканчивать прогрессию следует тем элементом, который ближе всего к заявленной верхней границе списка. В целых числах, напротив, вычисления всегда производятся точно, так что список [0,3. .11] будет содержать четыре элемента: [ 0, 3, 6, 9] (поскольку элемент 12 уже не попадает в объявленный диапазон значений). А вот список [0,0.3. .1.1] будет содержать уже пять элементов [ 0.0, 0.3, 0.6, 0.89 999, 1.19 999], поскольку значение последнего элемента 1.19 999 ближе к заявленной верхней границе 1.1, чем значение предпоследнего элемента.

Списки могут создаваться в программе путем последовательного присоединения элементов к началу списка с помощью специальной операции — конструктора списков, который имеет изображение в виде двоеточия. Например, если х — список из целых чисел, равный [2,3, 4 ], то конструкция 1: х создает новый список, элементами которого будут числа 1, 2, 3, 4. Изображение списка в виде конечного набора элементов всегда можно записать с помощью конструктора списков. Например, список [ 2, 3, 4 ] может быть записан в виде 2: (3: (4: [])).В этом примере круглые скобки необязательны, так как конструктор (:) «правоассоциативен», т. е. связывание операндов происходит не слева направо, как у большинства бинарных операций, а справа налево. Таким образом, в конструкции 2:3:4: [ ] построение списка происходит «справа налево», т. е. от последнего элемента к первому. В этой записи использована также константа [ ], изображающая пустой список.

Конструктор списков, так же, как и конструкторы кортежей, — это не совсем обычные операции. Они отличаются от, скажем, операции арифметического сложения целых тем, что не «вычисляет» никакого нового значения, а просто собирает сложный объект из более простых. Эти более простые объекты остаются в составе списка или кортежа неизменными, их можно извлечь оттуда и обрабатывать отдельно, в то время как после сложения числа 3 с числом 5 получается новый объект — число 8, в состав которого никоим образом не входят ни тройка, ни пятерка. Такие операции, которые лишь соединяют объекты в новый составной объект, в функциональном программировании называются конструкторами, и конструктор списков — это лишь частный случай более общего понятия конструктора. В дальнейшем мы увидим, что изображения константных значений (литералы) также можно рассматривать как конструкторы, создающие элементарные объекты. Таким образом, список, заданный перечислением своих элементов, может быть также задан с помощью применения двух конструкторов — двоеточия и пустого списка.

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

Имеется много встроенных в язык операций обработки списков. Вот важнейшие из них:

• • head, last — функции, которые по заданному аргументу-списку выдают его первый и последний элементы соответственно. Операции применимы только к непустому списку;
• • tail — функция, выдающая остаток списка, полученный отбрасыванием первого элемента. Аналогично функция init выдает список без последнего элемента. Обе операции также неприменимы к пустому списку;
• • ! ! — операция, которая по списку и заданному номеру элемента

выдает соответствующий элемент списка. Список должен быть непустым, а номер должен лежать в пределах от нуля (первый элемент списка имеет номер ноль) до количества элементов списка без единицы. Например, вычисление конструкции [1, 2, 3, 4] !! 2 приведет к выдаче в качестве результата числа 3 — элемента списка, имеющего номер 2;

• • null — функция проверки пустоты списка. Если в качестве аргумента этой операции будет задан пустой список, то функция выдаст значение True, в противном случае — False;
• • length — функция, вычисляющая количество элементов в списке (длину списка). Если аргумент — пустой список, то результатом функции будет ноль;
• • ++ — операция соединения двух списков. В результате применения этой операции к двум спискам из элементов одного и того же типа получается новый список из элементов того же типа, составленный из элементов первого списка, за которыми следуют элементы второго списка. Часто эта операция используется для соединения (катенации) двух строк.

Запрограммируем с помощью некоторых из этих функций вычисление суммы элементов списка. Оформим эту программу в виде функции sumList, получающей список из целых значений в качестве аргумента и выдающей их сумму (листинг 2.10).

Листинг 2.10. Суммирование элементов списка.

— функция суммирования элементов целочисленного списка. sumList: [Integer] -> Integer sumList s | null s = 0.

| otherwise = head s + sumList (tail s).

Во втором уравнении для функции sumList аргумент функции s «разбирается на части» применением встроенных функций head и tail. Нет необходимости делать дважды декомпозицию одного и того же списка. Поскольку любой список «собирается» с помощью конструктора списков, то и его «разборку» достаточно сделать один раз — на первый элемент и остаток списка. Это можно сделать с помощью аппарата сопоставления с образцом, при котором в уравнении для определения функции записывается «образец» — формальное выражение с конструктором, в котором отдельные части списка — его первый элемент и остаток — обозначены отдельными идентификаторами. Например, второе уравнение в определении функции sumList могло бы выглядеть так: sumList (x:xs) = х + sumList xs.

Если в качестве аргумента функции будет передан непустой список, то при попытке использовать второе уравнение произойдет сопоставление аргумента с образцом (x:xs). Поскольку непустой список всегда имеет форму, образованную с помощью конструктора списка (явно или неявно), то сопоставление пройдет успешно, причем в результате сопоставления произойдет «разборка» списка на первый элемент (голову) и остаток (хвост) списка. Идентификатор х начнет обозначать значение головы, a xs — хвост списка. В правой части уравнения эти идентификаторы используются при рекурсивном вызове функции и в операции сложения целых.

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

Листинг 2.11. Суммирование элементов списка.

— функция суммирования элементов целочисленного списка.

sumList: [Integer] -> Integer.

sumList [] =0.

sumList (x:s) = x + sumList s.

Заметим, что первый вариант функции sumList можно легко изменить таким образом, чтобы суммировать элементы, начиная с последнего по направлению к началу списка. Для этого вместо выражения head s + sumList (tail s) нужно использовать выражение last s + sumList (init s). Во втором варианте суммировать элементы с конца не получится, поскольку конструктор списков асимметричный: он присоединяет первый элемент к остатку списка, но не может присоединить последний элемент к началу списка. На самом деле и в первом варианте, несмотря на кажущуюся легкость изменения порядка суммирования, суммирование все же следует проводить от начала списка к концу. Дело в том, что встроенные функции last и init работают существенно дольше функций head и tail и требуют для работы больше памяти. Фактически каждая из этих функций при работе просматривает весь список от начала до конца, а функция init еще и строит заново список из всех начальных элементов! В этом легко убедиться, если посмотреть, как реализованы эти функции в стандартной библиотеке. Вот как выглядят, например, основные два уравнения в определении функции init: init [х] = [].

init (x:xs) = х: init xs.

Напротив, функции head и tail реализуются очень просто с помощью механизма сопоставления с образцом и не содержат никаких вспомогательных функций или рекурсивных вызовов: head (x:xs) = х.

tail (x:xs) = xs.

Фактически во всех функциях, которые мы определяли до этого, используется механизм сопоставления аргумента с образцом. Правда, если «образец» состоит только из имени переменной, то сопоставление всегда будет успешным и значение аргумента будет сопоставлено с этой переменной. В случае образца-константы (например, числа 0, как в определении функции вычисления факториала или пустого списка [ ], как в только что приведенном примере функции суммирования элементов списка) сопоставление будет успешным только в том случае, когда фактический аргумент представляет собой эту константу. Если функция определена с помощью серии уравнений, то сопоставления с образцами продолжаются до тех пор, пока не произойдет успешного сопоставления. Тогда (при условии, что хотя бы один из сторожей выдал истинный результат) в правую часть уравнения будут подставлены результаты успешного сопоставления с образцом, и редукция будет завершена.

При составлении функций обработки списков следует учитывать скорость работы встроенных операций над списками. В случае сомнений обращайтесь к документации. В ней непременно будет написано, что скорость работы встроенных функций length, init, last и операции (++) есть 0(п), т. е. линейно зависит от длины списка-аргумента. Рассмотрим, например, реализацию уравнений для операции соединения списков. Обратите внимание на форму записи уравнений: функция представлена инфиксной операцией, поэтому в левых частях уравнений формальные вызовы также удобно записывать в инфиксной форме:

[ ] ++ S = S.

(x:sl) ++ s2 = х: (si ++ s2).

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

Мы не указывали для описываемых встроенных функций их типы. Фактически аргументами этих функций могут быть любые списки независимо от типов их элементов; нужно только, чтобы типы этих списков «соответствовали» друг другу. Например, в операции соединения списков (++) аргументы должны быть списками из элементов одного и того же типа. Результатом, конечно, будет список с элементами того же самого типа. Для таких функций используют переменные тина, указывая для тех типов, которые должны совпадать, одинаковые идентификаторы. Вот как, например, можно описать тип функции length: length:: [а] -> Int.

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

(++):: [а] -> [а] -> [а].

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

Опишем типы остальных перечисленных выше встроенных операций, включив в этот список еще и функцию sum, которая является обобщением написанной нами функции sumList, и функцию product, вычисляющую произведение элементов списка (произведение элементов пустого списка равно единице): head, tail:: [а] -> а init, last:: [а] -> [а] null:: [а] -> Bool.

(! !):: [а] -> Int -> а.

sum, product:: Num, а => [а] -> а Опишем еще одну функцию обработки списков, которая, получая список в качестве своего аргумента, выдает список с теми же элементами, но расположенными в этом списке в обратном порядке (обращение списка). В данной функции можно также с помощью сопоставления с образцом «разобрать» исходный список на элементы, однако собирать его придется уже не с помощью конструктора списков, а посредством операции соединения списков. Текст функции приведен в листинге 2.12.

Листинг 2.12. Обращение списка

— обращение списка.

reverse:: [а] -> [а].

reverse [] = [].

reverse (x:s) = reverse s ++ [x].

Если внимательно проанализировать текст функции, то видно, что время ее работы пропорционально квадрату длины списка-аргумента. Конечно, это слишком много; интуитивно ясно, что задачу можно решить за линейное время. Проблему легко разрешить с использованием накапливающих аргументов. Для этого придется ввести вспомогательную рекурсивную функцию, которая будет по сравнению с основной версией иметь лишний аргумент. Новая версия функции будет иметь вид, показанный в листинге 2.13.

Листинг 2.13. Более эффективный вариант функции обращения списка.

— обращение списка.

reverse:: [а] -> [а].

reverse s = reverse' [] s.

• — дополнительный аргумент вспомогательной функции reverse'
• — служит для накопления результата reverse': [а] -> [а] -> [а]

reverse' s [] = s.

reverse' si (x:s2) = reverse' (x:sl) s2.

Этот вариант функции работает уже за линейное по длине аргумента время. Описание функции reverse также есть в стандартной библиотеке Haskell, но если вы посмотрите на то, как там определена эта функция, то не увидите ничего похожего ни на первый, ни на второй вариант: reverse = foldl (flip (:)) [].

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

Приведем еще несколько полезных операций над списками:

• • take — строит список из заданного количества первых элементов списка-аргумента. Например, значением выражения take 4 [3,1,6,5,81 будет список [3,1,6,5]. Если в качестве первого аргумента передать ноль или отрицательное значение, то в результате получится пустой список. Если первый аргумент больше, чем длина второго аргумента, то результатом будет весь исходный список;
• • drop — имеет аналогичные аргументы — количество начальных

элементов списка и сам исходный список, но, наоборот, отбрасывает первые элементы, так что в результате вычисления drop 4 [3,1,6, 5, 8 ].

получится список из одного элемента [ 5 ]. Функция drop также допускает задание в качестве первого аргумента отрицательных чисел и чисел, значения которых больше, чем длина второго аргумента, drop n list при отрицательном или нулевом значении п выдает второй аргумент list без изменений, а при n > length list выдает пустой список;

• splitAt — представляет собой комбинацию take и drop, выдавая сразу и префикс, и постфикс заданного списка в виде кортежа из двух списков. Например, значением выражения splitAt 4 [3,1, 6,5,8] будет пара ([3,1,6,5], [8]). Вообще, во всех случаях выражения splitAt.

n list и (take n list, drop n list) совпадают.

Приведем еще одну синтаксическую конструкцию, которую будем в дальнейшем называть генератором списков. Генератор списков позволяет строить списки из элементов других списков, выполняя над исходными элементами те или иные операции. Выглядит эта конструкция так:

[ |, ].

где — конструкции для порождения элементов исходных списков, имеющие вид <-, например, х <- [ 1.. 5]; — выражения над элементами образца, вычисляющие логические условия над элементами образца, определяющие, нужно ли использовать этот элемент для построения нового списка. Например, генератор списка.

[ х*х | х <- [1.100], х 'mod' 3 /= 0, х 'mod' 5 /= 0].

задает список квадратов чисел из первой сотни, которые не делятся ни па 3,.

ни на 5.

Если источников несколько, то для построения списка берутся все комбинации элементов из всех источников. Например, построить список всех двухбуквенных слов в заданном алфавите alfa можно, записав следующую конструкцию:

[ [а, Ъ] | а <- alfa, b <- alfa ].

Проверяем результат:

" let alfa = «abc» .

>> [ [a, b] | а <- alfa, b <- alfa ].

[" aa" ," ab" ," ac" ," ba" ," bb" ," be"," ca"," cb" ," cc" ].

А вот как можно построить список строк, представляющих все двузначные натуральные числа в порядке возрастания:

" let digits = «123 456 789^й

>> [ [dl, d2] | dl <- digits, d2 <- digits, dl /=.

[" 10″ ," 11″ ," 12″ ," 13″ ," 14″ ," 15″ ," 16″ ,…," 97″ ," 98″ ,.

ii.

'O'.

99″ ].

].

(результат представлен в сокращении).

В заключение основного материала главы приведем еще одну задачу на обработку списков. В ней рассматривается чуть более сложная структура данных — список строк, т. е. список, элементами которого также служат списки символов. Пусть требуется определить, имеются ли в заданном списке строк «белые» строки. Мы будем называть «белой» строку, которая совсем не содержит символов либо содержит только пустые символы, т. е. символы пробелов, переводов строк и т. п. Для проверки того, является ли данный конкретный символ пустым, будем применять библиотечную функцию Haskell isSpace, которая описана в модуле Data.Char. Для подключения библиотечных модулей в Haskell используется предложение import, которое мы и добавим в начало текста нашей программы.

Для решения задачи сначала определим функцию, которая будет проверять, является ли строка «белой». Это очень простая функция, которую легко определить с помощью рекурсии. После этого основная задача решается уже также просто: нужно лишь последовательно перебрать все строки, проверяя «цвет» каждой из них. Если будет обнаружена «белая» строка, то функция тут же завершит работу с результатом True. Если ни одной «белой» строки не обнаружится, то результатом работы функции будет False. В листинге 2.14 представлено полное решение задачи.

Листинг 2.14. Функция проверки наличия в списке «белых» строк.

import Data.Char.

— функция определения «цвета» строки.

white white [].

white (x:s) | isSpace x.

| otherwise.

:: String -> Bool = True = white s = False.

— функция, проверяющая, имеются ли в списке строк «белые» hasWhites:: [String] -> Bool.

hasWhites [] = False.

hasWhites (x:s) | white x = True.

| otherwise = hasWhites s.

Отметим, что решение задачи записано очень просто и интуитивно понятно. Применение функционального стиля программирования помогает выразить не столько то, как надо решать задачу, сколько то, что именно нам нужно получить.