对返回类型为Either的haskell函数进行递归

Question

我试图建立一个字符串基于查找结果从地图在Haskell。这是我到目前为止的代码:

import qualified Data.Map as Map
toRNA :: String -> Either Char String
toRNA [] = Right ""
toRNA (x:xs) = case getRna x of
Nothing -> Left x
Just rnaCode -> Right (rnaCode : toRNA xs)
getRna :: Char -> Maybe Char
getRna c = Map.lookup c rnaMap
rnaMap :: Map.Map Char Char
rnaMap =
Map.fromList
[ ('G', 'C')
, ('C', 'G')
, ('T', 'A')
, ('A', 'U')
]

这显然不起作用，因为您不能在代码Right (rnaCode : toRNA xs)的行中将Char添加到Either Char String。如何递归地调用这个函数来构建正确的字符串?例如:toRNA "GCT"应该返回Right "CGA"

左边的情况是我的错误情况，它返回我的rnaMap中不存在的键的第一个实例的值。例如:toRNA "CXL"应该返回Left "X"

Answer 1

如果您将getRna定义为立即使用Either，那么toRNA就会变得简单得多。

getRna :: Char -> Either Char Char
getRna c = case Map.lookup c rnaMap of
Nothing -> Left c
Just base -> Right base
-- getRna c = maybe (Left c) Right (Map.lookup c rnaMap),
-- using maybe :: b -> (a -> b) -> Maybe a -> b to abstract
-- away the case expression.

traverse的行为与map非常相似:它将getRna应用于字符串中的每个值。如果该应用程序产生Left值，它将立即返回该Left值。否则，它将获取Right值的结果列表，并将其转换为由Right包装的单个字符串，即[Right 'C', Right 'G']变为Right ['C', 'G'] == Right "CG"。

toRNA :: String -> Either Char String
toRNA = traverse getRna

(实际上，traverse只是map和sequenceA的组合，即"反转"的函数)Either Char Char值到Either Char String值的列表:

toRna = sequenceA . map getRna

或

toRna s = sequenceA (map getRna s)

)

---

您也可以保留原来的getRna，并简单地在toRNA的定义中进行调整:

toRNA :: String -> Either Char Sting
toRNA = traverse getRna'
where getRna' c = maybe (Left c) Right (getRna c)

如果你喜欢无点的定义，你可能会从

中得到乐趣。

toRNA = traverse (flip maybe Right . Left <*> getRna)

以来

flip maybe Right . Left <*> getRna
-- f <*> g  == x -> f x (g x)
== c -> (flip maybe Right . Left) c (getRna c)
== c -> (flip maybe Right (Left c)) (getRna c)
== c -> (maybe (Left c) Right) (getRna c)

Answer 2

我建议使用Either是函子的事实:

toRNA :: String -> Either Char String
toRNA [] = Right ""
toRNA (x:xs) = case getRna x of
Nothing -> Left x
Just rnaCode -> (rnaCode:) <$> toRNA xs

(<$>是fmap的中缀同义词)

Answer 3

询问"如何优雅地做这件事"的问题;这里还有另一个选项，它不重新定义getRna并使用Applicative而不是(仅仅)Functor实例用于Either String:

import Data.Maybe (maybe)
toRNA :: String -> Either Char String
toRNA [] = Right ""
toRNA (x:xs) = (:) <$> maybe (Left x) Right (getRna x) <*> toRNA xs

老实说，我认为chepner的方式是最好的，但我花了一分钟来解决这个问题，并认为我不妨发布它;这个f <$> a <*> b的东西(本质上是f a b，除了涉及的所有内容都被包装在Applicative中)经常出现，特别是在使用解析器组合子时，我发现它很整洁。