haskell - 在递归函数内使用 '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 中实现错误处理任务的惯用方法是使用 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 #-} pragma 位于源文件顶部 module 之前声明。