재귀 함수 내에서 '모두'를 사용하여 오류 처리

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

참고 : 하스켈을 처음 사용합니다. (반드시 간단한)

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은 당신의 코드에 대한 최소한의 수정 프로그램을 제공하기 위해 노력. 하스켈에서 오류 처리 작업을 구현하는 관용적 인 방법은 Error 모나드를 사용하는 것입니다. 주된 이유는 combine을 구현하기 위해 liftM2 라이브러리 함수를 재사용 할 수 있기 때문입니다. throwError 및 return은 Left 및 Right으로 바꿀 수 있지만 일반 함수는 코드의 목적을보다 명확하게 설명합니다. combine root left right = liftM2 (Node2 root) left right : combine = liftM2 . Node2 이상 : combine이 짧아 질 수 있다는

는

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) 

참고. 가장 잘 이해하는 스타일을 사용하십시오. 오류에 관한 또한

일부 의견은 고정 @Andre :

• insert2는 오류 유형의 다형성이 아니었다 - 항상 실패의 경우에 String를 반환했습니다. 그래서 대신 형식 선언에 String을 사용했습니다.
• 목록과 달리 정렬 된 컬렉션에는 형식을 저장할 수 없으며 비교할 수있는 형식 만 트리에 넣을 수 있습니다. 따라서 < 및 ==이 유형에 대해 구현되어야 함을 나타 내기 위해 트리 값 유형에 Ord a => 제약 조건을 추가했습니다.
• insert2은 Either을 반환합니다. 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 선언 전에.