在遞歸函數中使用'Either'的錯誤處理

Question

假設一個二叉搜索樹，我想在我們試圖插入一個已經存在的元素的情況下返回一個錯誤。有沒有辦法做到這一點？

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

注意：我是Haskell的新手。

Answer 1

這個問題是簡單的使用輔助功能來解決：

insert2 :: (Ord a) => a -> BST2 a -> Either String (BST2 a) 
insert2 newVal tree 
    | contains newVal tree = Left "Error: element already in tree" 
    | otherwise = Right $ insert newVal tree 

現在你需要contains和insert：

contains :: (Ord a) => a -> BST2 a -> Bool 
contains .... implementation .... -- checks whether a BST2 contains an element 

insert :: (Ord a) => a -> BST2 a -> BST2 a 
insert .... implementation .... -- inserts an element if not already there, 
           -- otherwise returns original tree 

或者，不是Either String (BST2 a)，你可以使用的Haskell's many other approaches一個錯誤。

Answer 2

只是一個快速的解決方案（不一定是簡單）：

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) 

Answer 3

@Andre只是想爲您的代碼提供了一個最小的修復。在Haskell中實現錯誤處理任務的慣用方法是使用Error monad。主要原因是可以重用liftM2庫函數來實現combine。 throwError和return可以替換爲Left和Right，但通用函數更清楚地解釋了代碼的用途。

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) 

注意combine可以短：combine = liftM2 . Node2或更長：combine root left right = liftM2 (Node2 root) left right。使用你最瞭解的風格。

而且有關錯誤的一些意見@Andre固定：

• insert2不是錯誤的類型多態的 - 它總是以失敗的情況下返回String。所以他在類型聲明中使用String而不是b。
• 與列表不同，有序集合不能存儲任何類型 - 只能將可比較（有序）的類型放入樹中。因此，他在樹值類型上添加了Ord a =>約束，以指示<和==必須針對該類型實施。
• insert2返回Either。您試圖通過Left或Right至Node2和Node2 root (Left foo) right失敗，因爲它預計Node2 a但提供Either String (Node2 a)。

最後一個理由使用throwError和return是函數變成通用：

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

，您可以與其他MonadError比Either情況下使用它，但你需要添加{-# LANGUAGE FlexibleContexts #-}編譯在module聲明前的源文件頂部。