Haskell net exceptions

Question

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

I have the following code to insert an element into a binary search tree with minimal comparisons and without copying when the element is a member of the tree. I noticed that either used as catch and Left as throw :

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

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

Answer 1

The monadLib package in Hackage has an Exception monad (and a Monad Transformer ExceptionT) that you can use without I / O. When you run it, you end up with a Face type.

Answer 2

It depends on what you want the exceptions for.

If you are trying to return an error value from a function (for example, “key not found” or “key already exists”), you should use something in these lines. “Left” is traditionally used to mean errors on the grounds that “Right” is the correct result. The error monad is used here just like the nun “Maybe”: when an error occurs, the rest of the calculation is not performed, without the need to link the set “if then, if then ...” together. In this case, the “exception” is not exceptional; your code must either process it or pass it on 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 not happen, but you were wrong. Since these exceptions are unpredictable, they can be non-deterministic and, as a rule, do not fit into the type system, they should be considered as I / O events. The usual pattern is to ignore these exceptions, with the exception of the very top level of your program, where you can try to save the user’s work and post a useful message, for example, "report this error."

Throwing this last exception is easy: just throw an “error”. But use it only for things that you truly consider impossible; it should never be a normal part of your code.

Answer 3

Tricky! This is a really good mechanism for comparing values ​​with (==) at the last moment and only if necessary. Byt, why didn't you comment on this, at least with type information?

 data Tree a = E | T (Tree a) a (Tree a) insert :: (Ord a) => a -> Tree a -> Tree a insert xt = const t `either` id $ insert' xt 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 (TE x E) insert' x E (Just v) | x==v = Left E | otherwise = Right (TE 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 lvr) _ | x<v = (\l' -> T l' vr) `fmap` insert' xl Nothing | otherwise = (\r' -> T lv r') `fmap` insert' xr (Just v) 

Why did you use Either if you threw out the left case and then use the copy? It would be more efficient if you did not save this copy to replace an equal tree and instead build an equal tree at all. Something like this...

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

And then ... if you want to be really effective, do not create this parameter (perhaps a) 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 will look like this:

 insert :: (Ord a) => a -> Tree a -> Tree a insert xt = fromMaybe t $ insert'1 xt 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 (TE x E) insert'1 x (T lvr) | x<v = do l' <- insert'1 xl Just (T l' vr) | otherwise = do r' <- insert'2 xr Just (T lv r') insert'2 x E v = guard (x/=v) >> Just (TE x E) insert'2 xt _ = insert'1 xt 

(EDIT:)

This instance is specified in Control.Monad.Error:

 Error e => MonadError e (Either e) 

That means (or String) you're probably looking.

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