Error handling using 'Either' inside a recursive function

Question

Assuming a binary search tree, I would like to return an error in case we are trying to insert an element that is already there. Is there a way to make this work?

data BST2 a = EmptyBST2 | Node2 a (BST2 a) (BST2 a)  deriving Show

insert2 :: a -> Either b (BST2 a) -> Either b (BST2 a)
insert2 elem (Right EmptyBST2) = Right (Node2 elem EmptyBST2 EmptyBST2)
insert2 elem (Right (Node2 root left right))
  | (elem == root) = Left "Error: Element already exist."
  | (elem < root) = (Node2 root (insert2 elem left) right)
  | otherwise = (Node2 root left (insert2 elem right))

Note: I am new to Haskell.

Answer 1

@Andre just tried to provide a minimal fix for your code. An idiomatic way to implement your error handling task in Haskell is to use the Error monad. The main reason for that is a possibity to reuse liftM2 library function to implement combine. throwError and return can be replaced by Left and Right, but the generic functions explain the purpose of your code more clearly.

module Err where

import Control.Monad (liftM2)
import Control.Monad.Error (throwError)

data BST2 a = EmptyBST2 | Node2 a (BST2 a) (BST2 a)  deriving Show

combine root = liftM2 (Node2 root)

insert2 :: (Ord a) => a -> BST2 a -> Either String (BST2 a)
insert2 elem EmptyBST2 = return $ Node2 elem EmptyBST2 EmptyBST2
insert2 elem (Node2 root left right)
  | (elem == root) = throwError "insert2 error: Element already exists."
  | (elem < root) = combine root (insert2 elem left) (return right)
  | otherwise = combine root (return left) (insert2 elem right)

Note that combine can be shorter: combine = liftM2 . Node2 or longer: combine root left right = liftM2 (Node2 root) left right. Use the style you understand best.

Also some comments regarding the errors @Andre fixed:

• insert2 was not polymorphic in error type - it always returned a String in case of failure. So he used String in the type declaration instead of b.
• Unlike lists, ordered collections cannot store any type - only types which can be compared (ordered) can be put into a tree. So he added Ord a => constraint on tree value type to indicate that < and == must be implemented for the type.
• insert2 returns Either. You tried to pass Left or Right to Node2 and Node2 root (Left foo) right fails because it expects Node2 a but Either String (Node2 a) is provided.

Finally, one more reason to use throwError and return is that the function becomes generic:

insert2 :: (Ord a, MonadError String m) => a -> BST2 a -> m (BST2 a)

and you can use it with instances of MonadError other than Either, but you need to add {-# LANGUAGE FlexibleContexts #-} pragma at the top of your source file before the module declaration.

Answer 2

Just a quick solution (not necessarily simple):

data BST2 a = EmptyBST2 | Node2 a (BST2 a) (BST2 a)  deriving Show

combine :: a -> Either b (BST2 a) -> Either b (BST2 a) -> Either b (BST2 a)
combine a (Left b) _ = Left b
combine a _ (Left b) = Left b
combine a (Right left_subtree) (Right right_subtree) = Right (Node2 a left_subtree right_subtree)

insert2 :: (Ord a) => a -> Either String (BST2 a) -> Either String (BST2 a)
insert2 elem (Right EmptyBST2) = Right (Node2 elem EmptyBST2 EmptyBST2)
insert2 elem (Right (Node2 root left right))
  | (elem == root) = Left "Error: Element already exist."
  | (elem < root) = combine root (insert2 elem (Right left)) (Right right)
  | otherwise = combine root (Right left) (insert2 elem (Right right))

-- test data
t1 = EmptyBST2
t2 = Node2 17 t1 t1
t3 = Node2 42 t2 t1
t4 = insert2 11 (Right t3)
t5 = insert2 17 (Right t3)