再帰関数内で 'どちらか'を使用したエラー処理

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

この問題はヘルパー関数を使用して解決するために簡単です：代わりにEither String (BST2 a)、あなたはエラーにHaskell's many other approachesのいずれかを使用することができ、また

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 

：

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を必要としています。

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モナドを使用することです。その主な理由は、combineを実装するためにライブラリ関数liftM2を再利用する可能性です。 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を返しました。そこで、bではなく、型宣言でStringを使用しました。
• リストとは異なり、順序付けられたコレクションはどのタイプも格納できません。比較（順序付け）できるタイプのみをツリーに入れることができます。そこで、<と==が型に実装されなければならないことを示すために、木の値の型に制約Ord a =>を追加しました。
• insert2Eitherを返します。 Node2 aではなくEither String (Node2 a)が指定されているため、LeftまたはRightをNode2およびNode2 root (Left foo) rightに渡そうとしましたが失敗しました。

最後に、throwErrorとreturnを使用するもう一つの理由は、機能が汎用的になることである：

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

、あなたはEither以外のMonadErrorのインスタンスで使用することができますが、{-# LANGUAGE FlexibleContexts #-}プラグマを追加する必要がありますソースファイルの先頭にあるmodule宣言の前に。