Чистые исключения в Хаскеле

Question

Как можно использовать исключения в Haskell, не проходя через IO?

У меня есть следующий код для вставки элемента в двоичное дерево поиска с минимальным сравнением и без копирования, когда элемент является членом дерева. Я заметил, что either используется как catch и Left как throw:

insert x t = either (const t) id (insert' x t Nothing)
    where
    insert' x E m = maybe (Right (T E x E)) (\v -> if x==v then Left E else Right (T E x E)) m
    insert' x t@(T l v r) m = if x<v
                                 then fmap (\l' -> T l' v r) (insert' x l Nothing)
                                 else fmap (\r' -> T l v r') (insert' x r (Just v))

Поэтому я попытался переписать его, используя Control.Monad.Error, надеясь упростить код, но у меня возник большой беспорядок. Есть предложения?

Answer 1

Это зависит от того, для чего вы хотите исключения.

Если вы пытаетесь вернуть значение ошибки из функции (например, «ключ не найден» или «ключ уже существует»), то вам следует использовать что-товдоль этих линий.«Левый» традиционно используется для значения ошибки на том основании, что «Правый» является правильным результатом.Монада Error здесь используется так же, как и монада «Maybe»: при возникновении ошибки остальная часть вычислений не выполняется, без необходимости связывать множество «если тогда еще, если тогда…»все вместе.В этом случае «исключение» не является действительно исключительным;ваш код должен либо обработать его, либо каким-то образом передать его на следующий уровень.

С другой стороны, вы также можете захотеть отловить непредвиденные исключения, такие как «head []», где вы подумалиникогда не могло случиться, но ты был неправ.Поскольку эти исключения непредсказуемы, могут быть недетерминированными и обычно не вписываются в систему типов, они должны рассматриваться как события ввода-вывода.Обычный шаблон - игнорировать эти исключения, за исключением самого верхнего уровня вашей программы, где вы можете попытаться сохранить работу пользователя и создать полезное сообщение, например «пожалуйста, сообщите об этой ошибке».

Бросив эту последнююТакое исключение легко: просто назовите «ошибка».Но используйте его только для тех вещей, которые, по вашему мнению, не могут произойти;это никогда не должно быть нормальной частью вашего кода.

Answer 2

Пакет monadLib в Hackage имеет монаду Exception (и преобразователь монад ExceptionT), которую можно использовать без IO. Когда вы запускаете его, в результате вы получаете тип Either.

Answer 3

Tricky! Это действительно хороший механизм для сравнения значений с (==) в последний момент, и только если это необходимо. Быт, почему вы не прокомментировали это хотя бы с информацией о типе?

data Tree a = E | T (Tree a) a (Tree a)

insert :: (Ord a) => a -> Tree a -> Tree a
insert x t = const t `either` id $ insert' x t Nothing
    where
    -- insert' (insert_this) (into_this_empty_tree) (except_if_it_equals_this) (because_then_the_tree_is_Left_unchanged)
    insert' :: (Ord a) => a -> Tree a -> Maybe a -> Either (Tree a) (Tree a)
    insert' x E Nothing = Right (T E x E)
    insert' x E (Just v) | x==v      = Left E
                         | otherwise = Right (T E x E)
    -- insert' (insert_this) (into_this_nonempty_tree) ((anyway)) (recursive:if_it_branches_to_the_left_insert_it_there)
    -- insert' (insert_this) (into_this_nonempty_tree) ((anyway)) (recursive:if_it_equals_or_branches_to_the_right_insert_it_there_except_if_the_right_branch_is_empty)
    insert' x t@(T l v r) _ | x<v       = (\l' -> T l' v r) `fmap` insert' x l Nothing
                            | otherwise = (\r' -> T l v r') `fmap` insert' x r (Just v)

Почему вы использовали Either, если выбросили чехол Left, а затем использовали копию? Было бы более эффективно, если бы вы не хранили эту копию для замены равного дерева, а вместо этого вообще не создавали равное дерево. Как-то так ...

insert' :: (Ord a) => a -> Tree a -> Maybe a -> Maybe (Tree a)

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

--insert'1 :: (Ord a) => a -> Tree a -> Nothin -> Maybe (Tree a)
--insert'2 :: (Ord a) => a -> Tree a -> Just a -> Maybe (Tree a)
insert'1 :: (Ord a) => a -> Tree a -> Maybe (Tree a)
insert'2 :: (Ord a) => a -> Tree a -> a -> Maybe (Tree a)

Решение будет выглядеть так:

insert :: (Ord a) => a -> Tree a -> Tree a
insert x t = fromMaybe t $ insert'1 x t
    where
    insert'1 :: (Ord a) => a -> Tree a -> Maybe (Tree a)
    insert'2 :: (Ord a) => a -> Tree a -> a -> Maybe (Tree a)
    insert'1 x E = Just (T E x E)
    insert'1 x (T l v r) | x<v       = do l' <- insert'1 x l
                                          Just (T l' v r)
                         | otherwise = do r' <- insert'2 x r
                                          Just (T l v r')
    insert'2 x E v = guard (x/=v) >> Just (T E x E)
    insert'2 x t _ = insert'1 x t

(EDIT:)

В Control.Monad.Error определен этот экземпляр:

Error e => MonadError e (Either e)

Это означает, что (любая строка), вероятно, то, что вы ищете.

insert :: (Ord a,MonadError String m) => a -> Tree a -> m (Tree a)
insert x t = maybe (throwError "Error: element already in tree") return $ insert'1 x t
    where ...