Вычисления с неопределенным результатом

Во многих широко распространенных языках программирования есть понятие неопределенного, или «пустого» значения, которое часто обозначается специальным идентификатором null. Такое значение принадлежит сразу всем типам и позволяет представлять неопределенное значение, которое, в частности, может быть получено в результате вычислений. Например, в языке Java при попытке извлечь из отображения (Мар) значение по ключу, которого нет в этом отображении, функция get выдает в качестве результата null. К сожалению, для примитивных типов, таких, как.

int, char, double, понятие «пустого значения» не определено. В различных ситуациях в качестве такого значения могут выступать различные значения, являющиеся обычными значениями из множества, определенного конкретным примитивным типом. Например, функция поиска подстроки в строке из стандартной библиотеки Java — функция indexOf — в случае неудачи поиска выдает целое число -1 в качестве «неопределенного индекса», а в арифметических операциях с вещественными в качестве неопределенного значения часто выступает NaN (not a number — неопределенное число).

В Haskell для определения понятия неопределенного значения используется тип данных Maybe, определение которого выглядит следующим образом:

data Maybe, а = Nothing | Just a.

Здесь конструктор Nothing определяет «пустое значение», аналогичное значению null в языке Java, а конструктор Just задает «непустое» значение, содержащееся внутри значения типа Maybe. Важно, что тип значения Nothing всегда определяется из контекста. Конечно, если запросить тип этого значения " :t Nothing Nothing:: Maybe a.

вы получите не вполне определенный результат, но этот результат совершенно аналогичен тому, что вы получаете при запросе типа и многих других значений, например,.

" :t 23.

23:: Num, а => а сообщает о том, что значение 23 может в разных ситуациях изображать значение разных типов при условии, что этот тип принадлежит классу Num.

Тип Maybe используется во всех случаях, когда функция может выдать в качестве результата неопределенное значение. Например, стандартная функция find, определенная в пакете Data. List и предназначенная для поиска элемента с заданным свойством в списке, имеет следующее определение типа:

find:: (а -> Bool) -> [а] -> Maybe, а Аргументами этой функции являются предикат, определяющий свойство элементов списка и собственно список, а результатом является первый найденный элемент, обладающий заданным свойством, или значение Nothing, если элемента с заданным свойством нет в списке. Проверим работу этой функции на примерах:

>> import Data.List.

>> find (x -> x 'mod' 3 == 0) [1, 5, 6, 9, 11, 4].

Just 6.

>> find (x -> x 'mod' 7 == 0) [1, 5, 6, 9, 11, 4].

Nothing.

Функция нашла в списке из шести целых элемент, делящийся на 3, но не нашла элементов, делящихся на 7.

Тип данных Maybe является экземпляром многих стандартных классов, в частности, классов Eq, Ord, Show и Read. Определения операций этих классов для типа Maybe совершенно стандартные, т. е. фактически тип Maybe можно было бы определить так:

data Maybe, а = Nothing | Just a deriving (Eq, Ord, Read, Show).

В частности, это означает, что значения этого типа можно сравнивать между собой, при этом неопределенное значение Nothing оказывается меньше любого определенного значения. То, что эти значения представимы в виде строки (принадлежат классу Show), мы видели хотя бы потому, что интерпретатор GHC выдавал нам в текстовом виде результаты работы функции find. Обратное преобразование с помощью функции read также возможно. Вот как выглядят результаты работы некоторых операций над значениями типа Maybe:

" Nothing <= Just 25 True.

>> Just 17 > Just 20 False.

" read «Just 3.14»: Maybe Double.

Just 3.14.

Как и раньше, для корректного применения функции read нам понадобилось явно указать тип получаемого значения, так как интерпретатор не может самостоятельно из контекста определить этот тип.

В пакете Data. Maybe определены также некоторые удобные функции, посредством которых можно: проверить, с помощью какого из двух конструкторов создано значение типа Maybe; извлечь значение из-под конструктора Just; представить полученное значение типа Maybe в виде обычного значения, для которого, как в случае функции indexOf языка Java, одно из значений выделено как «неопределенное».

Приведем определения типов для некоторых из этих функций: isNothing:: Maybe, а -> Bool isJust:: Maybe a -> Bool fromJust:: Maybe a -> a fromMaybe:: a -> Maybe a -> a maybe:: b -> (a -> b) -> Maybe a -> b catMaybes:: [Maybe a] -> [a] mapMaybe:: (a -> Maybe b) -> [a] -> [b].

Функции isNothing и isJust нужны для проверки того, каким конструктором создано значение типа Maybe, т. е. можно проверить, получен ли в результате вычислений неопределенный или определенный результат. Смысл их действий совершенно очевиден.

Функция fromJust применима только к значениям, созданным конструктором Just, так что имеет смысл применять ее только в том случае, когда вы уверены, что получено «определенное» значение. В отличие от нее, функция fromMaybe позволяет задать замещающее значение для случая, если ее аргументом является Nothing. С помощью этой функции мы можем, например, определить функцию indexOf для поиска заданного символа в строке, которая будет использовать стандартную функцию findlndex из пакета Data .List. Функция findlndex, так же, как и ранее упомянутая функция find, производит поиск в списке элемента, удовлетворяющего некоторому условию, только в качестве результата она выдает не сам этот элемент, а его индекс. Разумеется, как и в случае функции find, функция может выдать неопределенное значение Nothing, если элемент с заданным свойством не найден. Нашу функцию indexOf мы определим аналогично тому, как это сделано в языке Java: функция будет выдавать индекс найденного символа в случае его присутствия в строке, и выдавать значение -1, если такого символа в строке нет: indexOf:: Char -> String -> Int.

indexOf c s = fromMaybe (-1) $ findlndex (e -> e == c) s.

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

>> indexOf 'o' «Hello, world» .

" indexOf 'a' «Hello, world» .

— 1.

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

indexOf:: Char -> String -> Maybe Int indexOf c s = findlndex (e -> e == c) s.

Функция maybe представляет расширенный вариант функции fromMaybe. Она позволяет не только задать некоторое значение в качестве «представителя» неопределенного значения Nothing, но и привести полученное «определенное» значение к другому типу. Например, если бы мы хотели в качестве результата функции indexOf получать не значение индекса, а строку, представляющую этот индекс, и строку «not found» в случае отсутствия символа в строке, то определение нашей функции могло бы выглядеть так:

indexOf:: Char -> String -> String.

indexOf c s = maybe «not found» show $ findlndex (e -> e == c) s Функция show, переданная в качестве аргумента в функцию maybe, осуществляет преобразование найденного индекса в строку, а вместо неопределенного значения Nothing теперь выдается строка «not found». Результаты работы этой функции теперь будут выглядеть по-другому:

" indexOf 'o' «Hello, world» .

Н 4 «.

" indexOf 'a' «Hello, world» .

" not found" .

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

catMaybes:: [Maybe а] -> [а].

catMaybes list = map fromJust $ filter isJust list.

Если имеется функция, которая применяется к каждому элементу некоторого списка, причем некоторые результаты могут оказаться неопределенными, то удобно применить функцию mapMaybe. Эта функция сначала применит свой первый аргумент ко всем элементам списка, а затем отберет получившиеся непустые значения: mapMaybe:: (а -> Maybe b) -> [а] -> [Ь].

mapMaybe func list = catMaybes $ map func list.

В некоторых из разобранных нами ранее примеров было бы уместно использовать тип данных Maybe и связанные с этим типом функции. Например, в реализации алгоритма Веллмана — Форда для поиска кратчайших путей в нагруженном графе (см. листинг 4.16) использовалась функция оценки расстояний, имеющая тип type Weight w = (Int -> w).

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

type Weight w = (Int -> Maybe w).

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

Листинг 5.2. Алгоритм Веллмана — Форда с использованием неопределенных значений.

import Graph import Data.Maybe.

type ArcList w = [Arc w].

type Weight w = (Int -> Maybe w).

• — Начальная оценка расстояний — все расстояния неопределенные,
• — кроме расстояния до начальной точки, которое равно нулю.
• — Аргументы: и — вершина графа, от которой будут считаться все

расстояния; gr — граф.

initDistance:: Num w => Int -> Graph w -> Weight w initDistance u gr = replace u 0 (v -> Nothing).

• — Выдает оценки расстояний в виде списка.
• — Аргументы: gr — исходный граф;
• — weights — функция оценки расстояний, distances:: Graph w -> Weight w -> [Maybe w] distances g weights = map weights [0.verts g — 1]
• — Заменяет значение оценки расстояния для одной заданной вершины. — Аргументы: и — номер вершины;

new — новое значение оценки; weights — оценочная функция, replace:: Int -> w -> Weight w -> Weight w.

replace u new weights = v -> if u == v then Just new else weights v.

• — Реализация процесса релаксации дуги.
• — Аргументы: weights — текущая функция оценки;
• — arc — дуга, релаксация которой производится, relax:: Real w => Weight w -> Arc w -> (Bool, Weight w) relax weights arc = if isJust wFrom &&
• (isNothing wTo | | fromJust wFrom + w < fromJust wTo) then (True, replace t (fromJust wFrom + w) weights) else (False, weights) where f = from arc t = to arc w = weight arc wFrom = weights f wTo = weights t
• — Реализация одного шага алгоритма Веллмана — Форда:
• — однократный проход по всем дугам графа с их релаксацией.
• — Аргументы: weights — начальная функция оценки; gr — исследуемый граф.

bfCycle:: Real w => Weight w -> Graph w -> (Bool, Weight w) bfCycle weights g = gfold func (False, weights) g.

where func (ch, weight) arc = (ch | | newCh, newWeight) where (newCh, newWeight) = relax weight arc.

— Поиск минимальных расстояний от заданной вершины до всех — остальных вершин графа с помощью алгоритма Веллмана — Форда. — Аргументы: start — номер начальной вершины;

gr — исследуемый граф.

— Результат: список найденных расстояний или пустой список в случае, если в графе имеется цикл с суммарной отрицательной нагрузкой.

bellmanFord:: (Real w, Show w) => Int -> Graph w -> [Maybe w] bellmanFord start gr = if changed then [] else distances gr final where (changed, _, final) = steps (0, initDistance start gr) steps (k, weights) | k > n = (True, n, weights).

| ch = steps (k+1, newWeights).

| otherwise = (False, k, weights) where (ch, newWeights) = bfCycle weights gr n = verts gr.

Сравните эту реализацию с реализацией, показанной в листинге 4.16. Несколько усложнилась функция релаксации ребра relax, однако в целом решение стало лучше, из некоторых функций удалось убрать лишний аргумент, обозначавший ранее «бесконечно большое» значение, да и результат работы стал более наглядным, так как отсутствие пути в некоторую вершину теперь естественным образом обозначается значением Nothing.

Иногда недостаточно сказать, что значение неопределенное, в некоторых случаях нужно уточнить причину, по которой вычисление закончилось неудачно. Рассмотрим стандартную операцию индексации списка (! !). Если значение индекса меньше нуля, то возникает ошибка, и интерпретатор сообщает о ней примерно следующим образом:

" [0.5] ! ! (-1).

*** Exception: Prelude.(!!): negative index.

Если наоборот, значение индекса слишком велико, то сообщение об ошибке будет другим:

" [ 0.. 5 ] ! ! 7.

*** Exception: Prelude.(!!): index too large.

Напишем функцию, аналогичную стандартной операции индексации, по выдающую неопределенное значение, если индекс задан неверно:

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

list !!+n | n= length list = Nothing | otherwise = Just (list ! ! n).

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

" [0.5] !!+ 3.

Just 3.

" [0.5] !!+ (-1)

Nothing.

" [0.5] !!+ 7.

Nothing.

Однако теперь мы потеряли информацию о том, что произошло в случае неудачной индексации — индекс был слишком маленьким или слишком большим? Для того чтобы сохранять дополнительную информацию в случае неудачного завершения работы функции, в Haskell имеется тип данных Either, определение которого выглядит так: data Either a b = Left, а I Right b.

Здесь конструктор Right используется для того, чтобы представлять корректно определенное значение типа Ь, а конструктор Left предназначен для сохранения информации об ошибке. Например, в нашей повой операции «улучшенного» индексирования можно в случае ошибки сохранять текстовое сообщение о природе ошибки или значение неправильно заданного индекса. Вот как теперь будет выглядеть реализация операции (! ! +): (!!+): [а] -> Int -> Either Int а.

list !!+n | n= length list = Left n I otherwise = Right (list ! ! n).

Проверим, как работает это определение:

" «Haskell» !!+ 3 Right? k '.

" «Haskell» !!+ (-3).

Left (-3).

>> «Haskell» !!+ 8 Left 8.

Конечно, можно вместо числового значения индекса выдавать в случае ошибки развернутое текстовое сообщение:

(!!+): [а] -> Int -> Either String а.

list ! !+ n | n < 0 = Left («negative index «++ show n).

I n < length list = Right (list ! ! n).

I otherwise = Left («index «++ show n ++ «too large»).

Примеры решения задач Задача 5.1. Определите для двоичного дерева поиска функцию, которая находит в дереве первое в порядке возрастания значение, которое удовлетворяет заданному предикату, и выдает найденное значение или Nothing, если значение не найдено.

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

Листинг 5.3. Функция поиска значения в упорядоченном дереве

data Tree, а = Null | Tree a (Tree a) (Tree a) tfind:: (a -> Bool) -> Tree a -> Maybe a tfind _ Null = Nothing.

tfind func (Tree rt tl tr) = case tfind func tl of found@(Just _) -> found.

Nothing -> if func rt then Just rt else tfind func tr.

Задача 5.2. Опишите функцию, которая находит порядковый номер (индекс) заданного значения в двоичном дереве поиска. Нумерация элементов производится с нуля по возрастанию значений.

Решение. В этой задаче, как и в предыдущей, нужно производить поиск по дереву, поэтому она может быть решена схожим способом. Однако в отличие от предыдущей задачи, здесь необходимо, перемещаясь по дереву, запоминать, сколько элементов пройдено. Будем искать индекс элемента следующим образом. Сначала сравним заданное значение с корневым элементом дерева, чтобы понять, в каком поддереве — левом или правом — нужно искать значение (или, возможно, значение находится в корне дерева). В зависимости от результата мы вычисляем искомый индекс, при этом если значение лежит в корне или в правом поддереве, то к найденному индексу следует прибавить число узлов левого поддерева, которое в этом случае можно вычислить с помощью отдельной функции. В результате получается программа, показанная в листинге 5.4.

Листинг 5.4. Поиск индекса элемента в дереве

tfindlndex:: Ord, а => а -> Tree, а -> Maybe Int tfindlndex _ Null = Nothing tfindlndex val (Tree rt tl tr).

| val < rt = tfindlndex val tl | val == rt = Just (count tl).

| otherwise = case tfindlndex val tr of Nothing -> Nothing Just n -> Just (n + count tl + 1) where count Null = 0.

count (Tree _ tl tr) = count tl + count tr + 1.

Задача 5.3. Определите тип данных для дерева, каждый узел которого может иметь произвольное число поддеревьев. Определите функцию show для этого дерева так, чтобы дерево выводилось в скобочной записи.

Решение. Самый простой способ определить такое дерево — это считать, что в каждом узле дерева имеется список поддеревьев. Таким образом, приходим к следующему определению типа данных:

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

Недостатком этого представления является то, что в нем не представимо пустое дерево.

Скобочная запись дерева, имеющего корень root и список поддеревьев t-p t₂, может выглядеть следующим образом: root' (tp, t₂',…).

где root' — представление корня дерева в виде строки, a t₁', t₂', … — скобочные записи поддеревьев t_v t₂,…. Тогда функцию show для такого дерева можно описать следующим образом:

show (Tree root list) = show root ++ «(«++.

(concat $ intersperse $ map show list) ++ «)» .

Здесь intersperse — функция из пакета Data. List, которая вставляет заданное значение (в данном случае — строку «, «) между элементами списка, заданного вторым аргументом. Таким образом, полный текст программы будет выглядеть так, как показано в листинге 5.5.

Листинг 5.5. Скобочная запись дерева с произвольным числом ветвей

import Data. List (intersperse) data Tree a = Tree a [Tree a] instance Show a => Show (Tree a) where.

show (Tree root list) = show root ++ «(» ++.

(concat $ intersperse $ map show list) ++ «)» .

Задача 5.4. Опишите дерево для представления арифметических выражений, операндами которого служат целые числа. Будем считать, что в арифметическом выражении могут использоваться бинарные операции сложения, вычитания, умножения, деления и вычисления остатка от деления. Опишите функцию для вычисления значения арифметического выражения по заданному дереву. Опишите еще одну функцию, которая представляет дерево в виде строки, изображающей арифметическое выражение в привычной инфиксной записи.

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

data Expression = Integral Integer |.

Binary Char Expression Expression Рекурсивная функция для вычисления значения выражения очень проста и следует рекурсивному определению типа данных для выражения:

evaluate:: Expression -> Integer evaluate (Integral n) = n.

evaluate (Binary operator el e2) = case operator of.

' + ' -> el' + e2'.

-> el' - e2'.

' -> el' * e2'.

• •/' -> el' 'div⁴ e2'
• •%' -> el' 'mod' e2¹ where el^f = evaluate el e2' = evaluate e2

Здесь знаки арифметических операций представлены символами * + ¹, * - ¹, ¹ * ^f, ¹ / ¹ и ¹ % ^? и обозначают соответственно операции сложения, вычитания, умножения, целочисленного деления и взятия остатка от целочисленного деления. Вычисление производится с помощью соответствующих стандартных операций Haskell.

Представление выражения в виде строки легко получить, если не заботиться о том, чтобы минимизировать число скобок в таком представлении. Однако при таком подходе для достаточно простого выражения 1+2*3−4 может получиться строка «((1+(2*3))-4)», в которой все скобки на самом деле излишни. Для того чтобы избежать генерации большого количества лишних скобок, введем понятие приоритета выражения. Будем считать, что приоритет константы — самый высокий, приоритет операций умножения, деления и взятия остатка — ниже, а самый низкий приоритет у операций сложения и вычитания. Порядковые значения приоритетов можно определить с помощью следующего задания типа данных Prio:

data Prio = ADD | MULTIPLY | CONSTANT deriving (Eq, Ord).

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

prio:: Expression -> Prio prio (Integral _) = CONSTANT.

prio (Binary operator _ _) =.

if operator == ' + ^f | | operator == then ADD else MULTIPLY.

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

instance Show Expression where show (Integral n) = show n show e@(Binary operator el e2) =.

• (if prio el < prio e then «(«++ show el ++ «)» else show el) ++ [operator] ++
• (if prio e2 <= prio e then «(» ++ show e2 ++ «)» else show e2)

Решение получено, оно полностью представлено в листинге 5.6. Листинг 5.6. Обработка дерева выражения

— Дерево арифметического выражения data Expression = Integral Integer |.

Binary Char Expression Expression — Приоритеты узлов дерева:

• — ADD — операция типа сложения;
• — MULTIPLY — операция типа умножения;
• — CONSTANT — константа.

data Prio = ADD | MULTIPLY | CONSTANT deriving (Eq, Ord).

— Функция вычисления значения выражения evaluate: Expression -> Integer evaluate (Integral n) = n.

evaluate (Binary operator el e2) = case operator of.

' + ' -> el' + e2'.

-> el' - e2'.

'*' -> el' * e2'.

' / ' -> el¹ ' div' e2 '.

'%' -> el' 'mod' e2' where el' = evaluate el e2' = evaluate e2.

— Функция вычисления приоритета prio: Expression -> Prio prio (Integral _) = CONSTANT.

prio (Binary operator _ _) =.

if operator == ' + ' II operator == then ADD else MULTIPLY.

• — Определение строкового представления выражения, instance Show Expression where show (Integral n) = show n show e@(Binary operator el e2) =
• (if prio el < prio e then «(«++ show el ++ «)» else show el) ++ [operator] ++
• (if prio e2 <= prio e then «(«++ show e2 ++ «)» else show e2)

Проверим правильность работы функций на нескольких простых примерах. Определим следующие простые выражения:

" let exprl = Integral 5.

>> let expr2 = Binary ' + ' (Integral 3) exprl >> let ехргЗ = Binary '*' expr2 expr2.

Проверим работу функций evaluate и show на этих выражениях, причем для проверки работы функции show просто попросим интерпретатор вывести значения этих выражений:

" map evaluate [exprl, ехрг2, ехргЗ].

[5,8,64].

>> [exprl, ехрг2, ехргЗ].

[5,3+5, (3 + 5)* (3 + 5)].

Получены разумные результаты.