Pure exceptions in Haskell

Question

How can exceptions be used in Haskell without going through IO?

I have the following code for inserting an element in a binary search tree with minimum comparisons and no copying when the element is a member of the tree. I noticed that either is used as catch and Left as 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))

So I tried to rewrite it using Control.Monad.Error hoping to make the code simpler, but I got a big mess. Any suggestions?

Answer 1

It depends on what you want exceptions for.

If you are trying to return an error value from a function (e.g. "key not found" or "key already exists") then you should be using something along these lines. "Left" is traditionally used for the error value on the grounds that "Right" is the right result. The Error monad is used in the same way here as the "Maybe" monad: when an error occurs the rest of the computation doesn't get done, without you having to chain lots of "if then else if then ...." together. In this case the "exception" isn't really exceptional; your code either has to handle it or pass it up to the next level in some way.

On the other hand you might also want to catch unforeseen exceptions, such as "head []" where you thought that something could never happen but you were wrong. Because these exceptions are unpredictable, may be non-deterministic, and generally don't fit into the type system they have to be treated as IO events. The usual pattern is to ignore these exceptions except for the very top level of your program, where you can try to save the user's work and put up a helpful message like "please report this bug".

Throwing this latter kind of exception is easy: just call "error". But only use it for things that you really believe can't happen; it should never be a normal part of your code.

Answer 2

The monadLib package on Hackage has an Exception monad (and an ExceptionT monad transformer) which you can use without IO. When you run it, you get an Either type as a result.

Answer 3

Tricky! It is a really nice mechanism to compare the values with (==) at the last moment and only iff needed. Byt why didn't you comment it at least with type information?

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)

Why did you use Either, if you throw the Left case away and then use a copy? It would be more efficient, if you would not hold that copy to replace an equal tree, and instead do not build an equal tree at all. Somehow like this...

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

And then... if you want to be really efficient, don't build that (Maybe a) parameter just to compare it afterwards.

--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)

The solution would look like this:

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:)

In Control.Monad.Error is this instance defined:

Error e => MonadError e (Either e)

That means, that (Either String) is probably what you are looking for.

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 ...