Pure eccezioni in Haskell

Question

In che modo è possibile utilizzare le eccezioni in Haskell senza passare per IO?

Ho il seguente codice per l'inserimento di un elemento in un albero di ricerca binario con confronti minimi e nessuna copia quando l'elemento è un membro dell'albero. Ho notato che either viene utilizzato come catch e Left come 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)) 

così ho provato a riscrivere usando Control.Monad.Error sperando di rendere il codice più semplice, ma ho avuto un gran casino. Eventuali suggerimenti?

Answer 1

Il pacchetto monadLib su Hackage ha un monogramma Exception (e un trasformatore monad ExceptionT) che è possibile utilizzare senza IO. Quando lo esegui, ottieni come risultato un tipo Either.

Answer 2

Dipende da cosa si desidera eccezioni.

Se si sta tentando di restituire un valore di errore da una funzione (ad esempio "chiave non trovata" o "la chiave esiste già"), si dovrebbe utilizzare qualcosa in questo senso. "Sinistra" viene tradizionalmente utilizzato per il valore dell'errore sulla base del fatto che "Destra" è il risultato giusto. La monade Error è usata nello stesso modo qui come la monade "Maybe": quando si verifica un errore, il resto del calcolo non viene eseguito, senza che tu debba concatenare un sacco di "if then else if then ...." insieme. In questo caso l'"eccezione" non è davvero eccezionale; il tuo codice deve gestirlo o passarlo al livello successivo in qualche modo.

D'altra parte si potrebbe anche voler rilevare eccezioni impreviste, come "testa []" in cui si pensava che qualcosa non potesse mai accadere ma si era sbagliato. Poiché queste eccezioni sono imprevedibili, possono essere non deterministiche e generalmente non si adattano al sistema di tipi che devono essere trattati come eventi IO. Il solito schema è di ignorare queste eccezioni tranne che per il livello più alto del tuo programma, in cui puoi provare a salvare il lavoro dell'utente e pubblicare un messaggio utile come "per favore segnala questo bug".

Lanciare quest'ultimo tipo di eccezione è semplice: basta chiamare "errore". Ma usalo solo per cose che credi davvero non possano accadere; non dovrebbe mai essere una parte normale del tuo codice.

Answer 3

Ingannevole! È un ottimo meccanismo per confrontare i valori con (==) all'ultimo momento e solo se necessario. Perché non hai commentato almeno con le informazioni sul tipo?

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) 

Perché hai utilizzato Either, se hai gettato via la custodia sinistra e ne hai utilizzato una copia? Sarebbe più efficiente se non si tenesse quella copia per sostituire un albero uguale e invece di non costruire un albero uguale. In qualche modo come questo ...

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

E poi ... se si vuole essere realmente efficace, non costruire che (forse a) il parametro solo per confrontarlo in seguito.

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

La soluzione sarebbe simile a questa:

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.L'errore è definito da questa istanza:

Error e => MonadError e (Either e) 

Ciò significa che (o una stringa) è probabilmente quello che stai cercando.

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