Примеры решения задач

Задача 3.1. В заданной строке символов будем считать числом произвольную последовательность цифр, слева и справа от которой не находится цифра. Напишите функцию sumNumbers:: String -> Integer, которая вычисляет сумму всех «чисел» в заданной строке. Например, для аргумента «0012. Зе-1000» результатом должно быть число 1015(12 + + 3 + 1000).

Решение. Прежде всего, необходимо выделить в строке фрагменты, представляющие числа. Фактически эта задача эквивалентна задаче о выделении слов, одно из решений которой было представлено в листинге 3.5. Одним из обсуждаемых решений было также решение, использующее стандартную функцию words. Воспользуемся этим подходом. Для этого сначала напишем функцию, которая по заданной строке получает новую строку, в которой все символы, удовлетворяющие заданному условию, заменены на заданный символ (в нашем случае нужно будет все символы, не являющиеся цифрами, заменять на пробел): replace:: (Char -> Bool) -> Char -> String -> String replace condition replacement text = map replaceChar text.

where replaceChar c = if condition c then replacement else c.

Если для проверки того, является ли символ цифрой, использовать стандартную функцию isDigit модуля Data. Char, то функция, выделяющая список всех изображений чисел в строке, будет выглядеть так: getNumbers:: String -> [String].

getNumbers text = words $ replace (not. isDigit) ' ' text.

Проверим, как работает наша функция:

>> getNumbers «0012.Зе-1000» .

[" 0012″ ," 3″ ," 1000″ ].

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

" :t read.

read:: Read a => String -> a >> :t show.

show:: Show a => a -> String.

Действительно, функция read преобразует строку в значение некоторого типа, а при условии, что этот тип принадлежит классу Read, а функция show, наоборот, берет значение произвольного типа а, принадлежащего классу Show, и превращает его в строку. С функцией show мы уже знакомы — она используется всякий раз, когда интерпретатор Haskell выводит результат вычисления выражения. Строки, числа, списки чисел и строк — все эти значения имеют типы, принадлежащие классу Show, поэтому такие значения могут быть выведены в качестве результатов работы интерпретатора. Однако не все значения могут быть преобразованы в строку. Например, если попробовать вывести на экран функциональное значение, скажем, функцию сложения, то мы получим сообщение об ошибке:

" (+).

:2:1:

No instance for (Show (aO -> aO -> aO)) arising from a use of 'print' которое говорит о том, что значение типа (аО -> аО -> аО), а это и есть тип функции сложения, не принадлежит классу Show, точнее, не является экземпляром этого класса.

Теперь попробуем проверить, как работает функция преобразования из строки в значение:

" read " 125″

:23:1:

No instance for (Read aO) arising from a use of 'read'.

The type variable 'aO' is ambiguous Получается ошибка! Оказывается, дело в том, что функция read «не знает», значение какого типа она должна получить. Нужно уточнить тип значения, которое мы ожидаем получить в результате анализа строки. Это можно сделать, указав тип вычисляемого выражения напрямую или уточнив тип функции read:

" read «125»:: Integer.

>> (read: String -> Integer) «125» .

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

>> readlnt:: String -> Integer.

readlnt str = foldl (umber c -> number*10 + digitToInt c) 0 str Теперь мы умеем преобразовывать текст, состоящий из десятичных цифр, в число, так что полное решение задачи можно представить в виде следующей программы (листинг 3.6).

Листинг 3.6. Программа суммирования чисел, изображения которых есть в тексте

import Data. Char (isDigit, digitToInt).

• — Функция замены символов, удовлетворяющих заданному условию — на заданный символ.
• — Аргументы:

условие замены символа; символ для замены;

• — исходный текст.
• — Результат:

текст с замененными символами, replace:: (Char -> Bool) -> Char -> String -> String replace condition replacement text = map replaceChar text.

where replaceChar c = if condition c then replacement else c.

• — Функция выделения из текста подстрок, изображающих числа.
• — Выделяемые числа — целые, беззнаковые. getNumbers:: String -> [String]

getNumbers text = words $ replace (not. isDigit) ' ' text.

• — Функция преобразования строки в целое число при условии,
• — что в исходной строке нет ничего, кроме цифр.

readlnt:: String -> Integer.

readlnt str = foldl attachDigit 0 str.

where attachDigit n c = n*10 + (fromlntegral $ digitToInt c).

— Функция суммирования чисел, представленных своими — изображениями в заданной строке. sumNumbers:: String -> Integer.

sumNumbers text = sum $ map readlnt $ getNumbers text Легко проверить, что наша функция работает правильно.

Задача 3.2. Напишите функцию maxProd: Real, а => [а] ->

[ а ], которая в списке арифметических значений находит тройку подряд идущих элементов с максимальным произведением (можно считать, что список содержит, по крайней мере, три элемента). Например, в списке [1,3,3,6,7,31 такой тройкой будет [3,6,7] (или [ 6, 7,3 ]), а в списке [-10,8,4,2,4,4,4] результатом может быть любой из двух списков — [8,4,2] или [4,4,4].

Решение. Класс Real, упомянутый в условии, — это класс типов, в которых определены арифметические операции (как в типах класса Num) и операции сравнения (как в типах класса Ord). Прежде всего, необходимо получить список всех троек рядом стоящих элементов списка. Это можно сделать, если применить функцию zip3 к трем копиям исходного списка, только из одной копии нужно удалить первый элемент, а из второй — два первых элемента:

>> let list = [1,3, 3, 6,7, 3].

list: [ Integer].

" zip3 list (tail list) (drop 2 list).

[ (1,3,3), (3,3,6), (3,6,7), (6,7,3) ].

Теперь можно вычислить произведения этих троек и выбрать из них максимальную. Подобную задачу мы уже решали (см. листинг 2.21), так что здесь мы можем повторить тот же прием: соединить тройки элементов с их произведениями в кортеж и затем выбрать максимум из полученных кортежей. В условии задачи требуется получить результат в виде списка элементов тройки, так что на этапе формирования троек можно сразу вместо кортежей из трех элементов списка генерировать списки из троек. Это можно сделать, заменив функцию zip3 на zipWith3. Приведем теперь полную программу для решения задачи (листинг 3.7).

Листинг 3.7. Нахождение тройки элементов с максимальным

произведением

• — Функция преобразования списка в список троек
• — рядом стоящих элементов. Предполагается, что исходный список — содержит по крайней мере 3 элемента, triples:: [а] -> [ [а] ]

triples list = zipWith3 makeTriple list (tail list) (drop 2 list) where makeTriple a b c = [a, b, c].

• — Функция вычисления тройки рядом стоящих элементов из списка,
• — имеющей максимальное произведение элементов тройки. maxProd:: Real, а => [а] -> [а]

maxProd list = snd $ maximum $ zip (map product t) t where t = triples list.

Проверка:

" maxProd [1,3,3,6,7,31 [6,7,3].

" maxProd [-10,8,4,2,4,4,4].

[8,4,2].

Задача 3.3. Напишите функцию, которая вычисляет количество инверсий в заданном списке элементов. Инверсией называется пара элементов списка, в которой первый элемент имеет в списке меньший индекс, чем индекс второго элемента, но больше его по значению. Например, в упорядоченном, но возрастанию списке инверсий нет. В списке, в котором элементы расположены строго по убыванию, любая пара элементов образует инверсию, так что число инверсий в нем равно числу пар; в списке из п элементов будет п (п-1) /2 инверсий. В списке [3,5,7,6,8,5] инверсию образуют пары (7,6), (7,5), (6,5) и (8,5) — всего четыре инверсии.

Решение. Сначала нужно научиться составлять списки пар элементов списка. В качестве первого шага напишем функцию, которая составляет пары из первого и всех остальных элементов списка. Для этого следует просто отделить первый элемент списка (head list) и составлять пары из этого элемента и всех остальных элементов списка (tail list). Функцию, которая это делает, назовем pairsl:

pairsl: [а] -> [(а, а)].

pairsl list = map (е -> (head list, e)) $ tail list.

Заметим, что функция неприменима к пустому списку, у которого нет первого элемента. Теперь эту функцию нужно применить ко всему списку, к этому же списку без первого элемента, списку без первых двух элементов и т. д. Функцию, которая строит список «хвостов» заданного списка, можно легко написать самому, но в модуле Data. List есть стандартная функция tails, которая решает эту задачу. Приведем ее рекурсивное определение: tails:: [а] -> [[а]].

tails [] = [[]].

tails list = list: tails (tail list).

Из определения очевидно, что функция порождает в том числе и пустой список, как «последний» хвост исходного списка. Действительно, если применить эту функцию, скажем, к списку [ 1, 2, 3 ], то получим следующий результат:

" tails [1, 2, 3].

[[1,2,3], [2,3], [3], []].

Пустой список нас нс интересует, к тому же наша функция pairsl на пустом списке не определена. Можно пойти несколькими путями: доопределить функцию pairsl так, чтобы она для пустого списка выдавала пустой список пар, или определить свой вариант функции tails, который не будет генерировать пустой хвост. Наконец, можно применять стандартный вариант tails, но «отрезать» от результата последний (пустой) список. Выберем второй вариант — свое определение функции tails: tails:: [а] -> [ [а] ].

tails [] = [].

tails list = list: tails (tail list).

Теперь если составить выражение map pairsl (tails list), то мы получим список списков всех пар элементов исходного списка list, например:

>> map pairsl (tails [1.4]).

[[(1,2), (1,3), (1,4)] / [(2,3), (2,4) ], [ (3,4)], [] ].

Мы получили четыре списка пар, последний из которых пуст (это список пар одноэлементного списка [4]). Соединить все нары в один список можно с помощью функции concat:

>> concat $ map pairsl (tails [1.4]).

[ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)].

но для сочетания функций concat и map есть удобное сокращение — функция concatMap, так что список всех пар элементов заданного списка list мы можем получить, написав выражение concatMap pairsl (tails list).

Осталось из полученных пар выбрать те, в которых первый элемент больше второго, и сосчитать их количество. Программа для решения задачи 3.3 приведена в листинге 3.8.

Листинг 3.8. Подсчет числа инверсий пар элементов в списке

• — Функция, образующая список пар элементов заданного непустого
• — списка, в котором первые элементы пар — это первый элемент списка,
• — а вторые элементы пар — это все остальные элементы списка, pairsl: [а] -> [ (а, а)]

pairsl list = map (е -> (head list, e)) $ tail list.

• — Функция порождения всех хвостов заданного списка. Аналогична
• — функции Data.List.tails, но не порождает пустого хвоста,

tails:: [а] -> [[а]].

tails [] = [].

tails list = list: tails (tail list).

— Функция, образующая список всех пар элементов заданного списка,.

pairs: [а] -> [(а, а)].

pairs list = concatMap pairsl $ tails list.

— Функция подсчета числа инверсий в заданном списке.

inversions:: Ord, а => [а] -> Int.

inversions list = length $ filter ((a, b) -> a > b) $ pairs list.

Проверка программы на нескольких простых примерах дает следующие результаты:

" inversions [1.5].

О.

>> inversions [5,4.1].

>> inversions [3,5,7,б, 8,5].

" inversions [].