Обработка ошибок с использованием '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

@ Андре только что попытался обеспечить минимальное исправление для вашего кода.Идиоматический способ реализовать вашу задачу обработки ошибок в Haskell - это использовать монаду Error.Основной причиной этого является возможность повторного использования библиотечной функции 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.

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

Эту проблему проще решить с помощью вспомогательных функций:

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 к ошибкам.