Haskell - Maybe and Recursion

Question

I want to take a string and turn into into a list of Direction. For example, "UDDUD" should return [U,D,D,U,D], whereas any string that does not contain a U or D returns Nothing (e.g. "UDYD" returns Nothing).

data Direction = U | D
    deriving (Show, Eq)
-- where U is Up and D is Down

findDirection :: [Char] -> Maybe [Direction]
findDirection [] = Nothing
findDirection ['U'] = Just [U]
findDirection ['D'] = Just [D]
findDirection (x:xs)
    | x == 'U' = Just (U : findDirection xs)
    | x == 'D' = Just (D : findDirection xs)
    | otherwise = Nothing

I get the following error:

Couldn't match expected type ‘[Direction]’
                with actual type ‘Maybe [Direction]’
    In the second argument of ‘(:)’, namely ‘findDirection xs’
    In the first argument of ‘Just’, namely
      ‘(U : findDirection xs)’

Test_findDirection.hs:8:32:
    Couldn't match expected type ‘[Direction]’
                with actual type ‘Maybe [Direction]’
    In the second argument of ‘(:)’, namely ‘findDirection xs’
    In the first argument of ‘Just’, namely
      ‘(D : findDirection xs)’

As I understand it, Just (D : findDirection xs) and Just (U : findDirection xs) are of type [Direction]? Why is this the case? What am I doing wrong, here?

Answer 1

Just (D : findDirection xs) and Just (U : findDirection xs) are of type [Direction]? Why is this the case? What am I doing wrong, here?

No, Just (D : findDirection xs) is actually ill-typed. Let's dissect this error message:

Couldn't match expected type ‘[Direction]’
                with actual type ‘Maybe [Direction]’

We're using Maybe [Direction] at a point where we should actually use [Direction].

In the second argument of ‘(:)’, namely ‘findDirection xs’

Aha. We're using (:) :: a -> [a] -> [a] wrong. After all, findDirection will return a Maybe [Direction], not a [Direction]. We need something like this:

consOnMaybe :: a -> Maybe [a] -> Maybe [a]
consOnMaybe _ Nothing   = Nothing
consOnMaybe x (Just xs) = Just (x : xs)

Now your function can be written as

findDirection (x:xs)
    | x == 'U' = consOnMaybe U (findDirection xs)
    | x == 'D' = consOnMaybe D (findDirection xs)
    | otherwise = Nothing

Alternatively, we could have used consOnMaybe x = fmap (x:). As an additional bonus, here is a variant that uses pre-defined functions and no explicit recursion (exercise: understand how it works)

findDirection :: [Char] -> Maybe [Direction]
findDirection [] = Nothing
findDirection xs = traverse toDirection xs

toDirection :: Char -> Maybe Direction
toDirection 'U' = Just U
toDirection 'D' = Just D
toDirection  _  = Nothing