在递归函数中使用"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

@Andre只是试图为您的代码提供最小的修复.在Haskell中实现错误处理任务的惯用方法是使用Errormonad.其主要原因是可以重用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声明之前在源文件的顶部添加pragma .