246
частности, функция, которая определяет, состоят ли две заданные строки
из одних и тех же букв. Во втором модуле эта функция используется для
того, чтобы определить все анаграммы в заданном наборе слов, то есть все
подмножества слов, состоящих из одних и тех же букв. Третий модуль
задает главную тестирующую функцию.
Функция
проверки того, состоят ли два слова из одних и тех же букв,
может просто отсортировать буквы в каждом из двух заданных слов и
после этого проверить, равны ли получившиеся отсортированные списки
букв. Сортировку будем производить простейшим методом простых
вставок, так что текст модуля будет иметь вид, показанный в листинге
П1.6.
Листинг П1.6. Модуль некоторых функций над строками
{-------------------------------------------------------------
Модуль, определяющий некоторые функции над строками
------------------------------------------------------------}
module Strings (anagrams, split) where
--------------------------------------------------------------
-- сортировка списка простыми вставками
--------------------------------------------------------------
-- основная функция insSort осуществляет сортировку списка.
-- Аргумент: исходный список;
-- Результат: отсортированный список
--------------------------------------------------------------
insSort :: Ord a => [a] -> [a]
insSort = insSort' []
--------------------------------------------------------------
-- Вспомогательная функция insSort' имеет дополнительный
-- накапливающий аргумент - отсортированная часть списка
-- Аргументы: 1) уже отсортированная часть списка;
-- 2) еще не отсортированные элементы
-- Результат: полностью отсортированный список
--------------------------------------------------------------
insSort' :: Ord a => [a] -> [a] -> [a]
insSort' lst [] = lst -- все элементы уже отсортированы
insSort' lst (x:tail) = insSort' (insert x lst) tail
--------------------------------------------------------------
-- Вспомогательная функция insert вставляет заданное значение
-- в отсортированный список
-- Аргументы: 1) элемент для вставки;
-- 2) упорядоченный список
-- Результат: список (2) с вставленным в него элементом (1)
--------------------------------------------------------------
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]