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

Задача 8.1. Дерево, в котором каждый узел содержит список потомков определено так, как это сделано в задаче 5.3:

data Tree, а = Tree a [Tree а].

Определите для такого дерева экземпляр класса Foldable.

Решение. Для того чтобы сделать структуру данных экземпляром класса Foldable, нужно определить одну из двух функций f oldMap или foldr. Во всех случаях для этого требуется определить, в каком порядке выстраиваются элементы нашей структуры. Для дерева, описанного конструктором типов Tree, можно определить несколько порядков прохождения элементов, некоторые из которых реализуются очень просто, а другие требуют более серьезного программирования.

Выстроить узлы в порядке рекурсивного обхода сверху вниз можно, если взять в качестве первого элемента корень дерева, а затем рекурсивно обходить в том же порядке все поддеревья корня. Легко определить функцию foldMap для такого порядка обхода. Модуль, определяющий эту функцию, приведен в листинге 8.2. Обратите внимание, что в определении функции foldMap есть вызов функции foldr, но это не свертка дерева, а свертка списка, поэтому используется функция, определенная в стандартной библиотеке Prelude.

Листинг 8.2. Свертка дерева с произвольным числом поддеревьев в узлах module FoldTree (Tree (Tree)) where

import qualified Data. Foldable as F import Data.Monoid.

data Tree a = Tree a [Tree a].

instance F. Foldable Tree where

foldMap f (Tree node children) =.

f node foldr (mappend. F. foldMap f) mempty children.

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

tree: Tree Integer.

tree = Tree 1 [Tree 2 [Tree 3 [], Tree 4 []], Tree 5 [Tree 6 []]].

Свернем это дерево в список:

" Data.Foldable.foldr (:) [] tree.

[1,2,3,4,5,6].

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

>> Data.Foldable.foldr (+) 0 tree.

Сложнее определить порядок обхода «в ширину», т. е. такой, при котором последовательно проходятся узлы, ближайшие к корню дерева. Для нашего примера дерева tree порядок такого обхода узлов определяется списком [1,2,5, 3,4, б]. Обход «в ширину» может быть традиционно реализован с помощью очереди из узлов деревьев и поддеревьев. Такая очередь станет дополнительным накапливающим аргументом вспомогательной функции, и реализация свертки дерева может получиться такой, как это представлено в листинге 8.3.

Листинг 8.3. Свертка дерева с помощью обхода «в ширину» module FoldTree (Tree (Tree)) where

import qualified Data. Foldable as F import Data.Monoid.

data Tree a = Tree a [Tree a].

instance F. Foldable Tree where

foldMap f t = queue f [t] mempty.

queue:: Monoid m => (a -> m) -> [Tree a] -> m -> m.

queue _ [] result = result.

queue f ((Tree a ch):trees) result =.

queue f (trees ++ ch) (result 'mappend' f a).

Проверим, как работает наше решение:

" F. foldr (:) [] tree.

[1,2,5,3,4,6].

>> F. foldr (+) 0 tree.

Задача 8.2. Монада нс обязана быть функтором. Однако можно написать функцию, которая работает с монадой так же, как функция fmap работает с функторами. Напишите функцию шшар, которая имеет тип mmap:: Monad m => (а -> b) -> m, а -> m b.

и образует монаду, применив свой первый аргумент к значению, находящемуся внутри монады, заданной вторым аргументом.

Решение. Функцию типа (а -> Ъ) можно легко превратить в функцию тина (а -> m b) с помощью композиции ее с функцией return. После этого требуемая операция mmap сводится к применению связывания:

mmap f m = m >>= return. f.

Замечание. Такая функция «поднятия» унарной операции до монады уже есть в стандартном пакете Control. Monad и называется liftM. Есть также аналогичные функции поднятия двуместных, трехместных и так далее до пятиместных операций. Например, вот как выглядит определение функции liftM3 для «поднятия» до монады трехместной операции: liftM3:: Monad m =>

(а -> b -> с -> d) -> m a -> m b -> m c -> m d liftM3 f ml m2 m3 =.

do { a <- ml; b <- m2; c <- m3; return (f a b c) }

Задача 8.3. Напишите диалоговую программу, которая угадывает задуманное вами число из диапазона от 0 до 99 методом двоичного поиска, задав не более семи вопросов.

Решение. Диалоговая программа не очень характерна для функционального стиля программирования, так как требует интенсивного применения операций ввода и вывода строк. Ее программирование по стилю скорее соответствует императивному стилю. Основу нашего решения будет составлять рекурсивная функция guess, которая будет, задавая вопросы, последовательно сужать интервал чисел [from, to), в котором лежит задуманное число. В основной программе эта функция вызывается с аргументами 0 и 100. Решение приведено в листинге 8.4. В программе используется функция форматированного вывода printf из пакета Text. Printf.

Листинг 8.4. Программа «угадывания» задуманного числа.

import Data. Char (toLower) import Text. Printf (printf).

askUser: Int -> Int -> 10 ().

askUser from to = do

let m = (from + to) 'div' 2.

printf «Задуманное меньше, чем %d? (yes, no) «m response <- getLine.

if not (null response) && toLower (head response) == ' y' then guess from m else guess m to.

guess: Int -> Int -> 10 () guess from to =.

if to — from == 1.

then printf «Это %d! «from else askUser from to.

main = do

putStrLn «Задумайте число от 0 до 99» guess 0 100.

Если задумать число 90 и корректно отвечать па вопросы программы, то ее запуск приведет к следующему результату:

" main.

Задумайте число от 0 до 99 Задуманное меньше, чем 50? (yes, по) по Задуманное меньше, чем 75? (yes, по) по Задуманное меньше, чем 87? (yes, по) по Задуманное меньше, чем 93? (yes, по) yes.

Задуманное меньше, чем 90? (yes, по) по Задуманное меньше, чем 91? (yes, по) yes.

Это 90 !

Приведенную программу можно скомпилировать и запускать как обычное приложение.

Задача 8.4. Обобщите ситуацию со школьным учителем математике, приведенную в параграфе 8.2. Пусть имеется список функций, которые последовательно преобразуют заданное значение, получая при этом результат того же тина. Пусть также имеется функция проверки корректности получаемого значения, которая выдает значение True, если значение корректно, и False, если нет. Требуется написать функцию, которая будет выдавать результат последовательного применения функций из заданного списка, оборачивая этот результат в монаду, если все промежуточные результаты применения функций корректны, и будет выдавать ошибку в случае, если хотя бы один промежуточный результат некорректен.

Например, для заданного начального значения 5 и последовательности функций [(+3), (*5), (subtract 8), (*3), (subtract 15)].

результатом последовательного применения этих функций будет значение ((5+3)*5−8)*3−15 = 81, причем как окончательный результат, так и все промежуточные результаты вычислений лежат в пределах первой сотни натуральных чисел («корректны»). Для того же начального значения 5 и похожей последовательности функций [ (+3), (*5), (subtract 5),.

(*3), (subtract 15) ] получим корректный результат ((5 + 3) *5- -5) *3−15 = 90, однако в процессе вычислений один из промежуточных результатов будет лежать за пределами первой сотни, поэтому все вычисление в условиях нашей задачи должно завершиться неудачей.

Искомая функция должна иметь следующий тип: evaluate:: Monad m => (а -> Bool) -> а -> [а -> а] -> ш, а где первый аргумент функции задает функцию проверки корректности значения, второй — начальное значение для последовательности вычислений, и третий — последовательность применяемых функций.

Решение. Прежде всего, напишем функцию, которая преобразует заданную обычную функцию типа, а -> а в функцию типа, а -> m а. Эта новая функция будет получать тот же результат, что и исходная «обычная» функция, но будет оборачивать этот результат в монаду, если он корректен с точки зрения некоторой функции проверки корректности, и будет закапчиваться неудачно, если результат некорректен:

toM:: Monad m => (а -> Bool) -> (а -> а) -> (а -> m а) toM cond func arg | cond result = return result | otherwise = fail «Fail» where result = func arg.

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

evaluate:: Monad m => (а -> Bool) -> а -> [а -> а] -> m, а evaluate cond seed = foldl (>>=) (return seed). map (toM cond) Проверим полученное решение. Пусть функция проверки корректности тестирует результат на предмет принадлежности его к первой сотне натуральных чисел:

check:: Integral, а => а -> Bool check х = х>0&&х< 100.

Теперь напишем простую функцию проверки корректности примера на арифметические действия с натуральными числами из первой сотни:

testEx:: Integral, а => а -> [а -> а] -> Maybe, а testEx = evaluate check.

и проверим два приведенных в тексте задачи примера на корректность:

" testEx 5 [(+3), (*5), (subtract 8), (*3), (subtract 15)].

Just 81.

" testEx 5 [(+3), (*5), (subtract 5), (*3), (subtract 15)] Nothing.

Интересно заметить, что тип результата полностью определяется типом, заданным нами для функции testEx. Например, если сделать минимальное изменение, заменив монаду Maybe монадой Either, testEx: Integral, а => а -> [а -> а] -> Either () а то получаемые результаты по смыслу будут теми же, но форма их представления изменится:

>> testEx 5 [(+3), (*5), (subtract 8), (*3), (subtract 15)].

Right 81.

" testEx 5 [(+3), (*5), (subtract 5), (*3), (subtract 15)].

*** Exception: Fail.

Приведем те же результаты, полученные, если тестирующая функция testEx будет иметь тип testEx: Integral, а => а -> [а -> а] -> [а]:

>> testEx 5 [(+3), (*5), (subtract 8), (*3), (subtract 15)].

[81].

" testEx 5 [(+3), (*5), (subtract 5), (*3), (subtract 15)].

[].

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

" evaluate check 5 [(+ 3), (*5), (subtract 8), (*3), (subtract 15)].

Похоже, наши «монадические» вычисления просто игнорируются, и результат вычисляется «обычным» способом? Проверим второй пример:

" evaluate check 5 [(+3), (*5), (subtract 5), (*3), (subtract 15)].

*** Exception: user error (Fail).

Этот пример показывает, что наши проверки не игнорируются. Предоставляем читателям самим исследовать вопрос о том, какая монада используется здесь «по умолчанию».

Задача 8.5. В параграфе 6.3 и в решении задачи 6.6 мы ввели понятия позиции в списке и двоичном дереве для того, чтобы можно было применять модифицирующие функции к элементам списка (или узлам дерева), нс проходя для каждого изменения всю структуру от ее головы до точки модификации. Перемещение позиции по списку или дереву осуществляли функции stepLeft, stepRight, stepUp и step, а собственно модификацию элемента списка или узла дерева производила функция replace. Мы все время считали, что как передвижения позиции, так и замена значения узла всегда выполняются успешно. Однако на самом деле при сдвигах позиции и замене значения могут возникнуть ошибки, связанные с тем, что происходит попытка сдвинуть позицию за пределы рассматриваемой структуры данных, или попытка заменить несуществующее значение, если текущая позиция указывает на пустой список или пустое дерево.

Имеет смысл изменить типы упомянутых функций таким образом, чтобы результатом их работы было не значение типа Position а, а значение типа Maybe (Position а). Например, для позиционирования в списке нами использовались функции.

stepLeft, stepRight:: Position, а -> Position, а stepLeft ((x:path), list) = (path, x: list) stepRight (path, (x:list)) = (x:path, list).

Модифицированные для проверки правильности применения эти же функции могут выглядеть теперь так:

stepLeft, stepRight:: Position, а -> Maybe (Position a) stepLeft ([], list) = Nothing.

stepLeft ((x:path), list) = Just (path, x: list) stepRight (path, []) = Nothing.

stepRight (path, (x:list)) = Just (x:path, list).

Как изменятся остальные функции, переведенные в «монадическую» форму?

Решение. Прежде всего, заметим, что введенный нами оператор «обратного применения» функции ($>) теперь не нужен, поскольку вместо него будет использоваться оператор связывания (>>=), применяемый для работы с монадами. Вот как, например, будет теперь выглядеть функция step, которая осуществляет последовательность шагов по перемещению позиции в списке:

step:: Int -> Position, а -> Maybe (Position a) step n pos = foldl (>>=) (return pos) actions.

where action = if n >= 0 then stepRight else stepLeft actions = replicate (abs n) action Сравните эту функцию с функцией step из параграфа 6.3. Аналогичным образом изменяются и остальные функции. Полностью модуль показан в листинге 8.5.

Листинг 8.5. Модуль для последовательных действий по изменению списка.

module ListModifier (Modifier, modify) where.

type Modifier a = (Int, a -> a) type Position a = ([a], [a]).

start:: [a] -> Position a.

start list = ([], list).

stepLeft, stepRight: Position a -> Maybe (Position a) stepLeft ([], list) = Nothing.

stepLeft ((x:path), list) = Just (path, x: list) stepRight (path, []) = Nothing.

stepRight (path, (x:list)) = Just (x:path, list).

step:: Int -> Position a -> Maybe (Position a) step n pos = foldl («=) (return pos) actions.

where action = if n >= 0 then stepRight else stepLeft actions = replicate (abs n) action.

extract: Position a -> [a].

extract (path, list) = foldl (flip (:)) list path.

replace:: (a -> a) -> Position a -> Maybe (Position a) replace f (path, []) = Nothing.

replace f (path, e: list) = Just (path, f e: list).

modify: [Modifier a] -> [a] -> Maybe [a] modify actions list = do pos <- return (start list) return (extract pos).

«=.

modifyPos.

(convert actions).

modifyPos:: [Modifier a] -> Position a -> Maybe (Position a) modifyPos actions pos = foldl act (return pos) actions where act pos (n, f) = do p <- pos.

step n p >>= replace f.

convert:: [Modifier a] -> [Modifier a] convert acts = zip (diffs indices) actions where (indices, actions) = unzip acts diffs [] = [].

diffs list@ (x:e) = x: zipWith (-) e list.

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