Recursion on a haskell function with an Either return type-CodePudding

I am trying to build a string based on the lookup result from a Map in Haskell. This is my code so far:

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

This obviously won't work as you cannot prepend Char to Either Char String in the line of code Right (rnaCode : toRNA xs). How can you recursively call this function to build the correct string? For example: toRNA "GCT" should return Right "CGA"

The Left case here is my error case which returns the value of the first instance of a non-existent key in my rnaMap. For example: toRNA "CXL" should return Left "X"

CodePudding user response：

If you define getRna to use Either right away, toRNA becomes much simpler.

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 acts much like map: it applies getRna to each value in the string. If that application ever produces a Left value, it immediately returns that Left value. Otherwise, it takes the resulting list of Right values and turns it into a single string wrapped by Right, i.e., [Right 'C', Right 'G'] becomes Right ['C', 'G'] == Right "CG".

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

(In fact, traverse is just the composition of map and sequenceA, the function that "inverts" the list of Either Char Char values to an Either Char String value:

toRna = sequenceA . map getRna

toRna s = sequenceA (map getRna s)

)

You can also keep your original getRna and simply adapt it in the definition of toRNA:

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

If you like point-free definitions, you may get a kick out of

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

since

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)

CodePudding user response：

I'd suggest using the fact that Either is an functor:

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

(<$> is an infix synonym of fmap)

CodePudding user response：

Questions asking "how do I do this thing elegantly" seem to draw people in :) Here's yet another option, which doesn't redefine getRna and uses the Applicative rather than (merely) the Functor instance for Either String:

import Data.Maybe (maybe)

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

I think chepner's way is best, honestly, but I spent a minute working this out and figured I might as well post it; this f <$> a <*> b thing (which is essentially f a b, except everything involved is wrapped in an Applicative) shows up fairly often, especially when using parser combinators, and I find it neat.