Haskell - Возможно и рекурсия

Question

Я хочу взять строку и превратить в список Direction, Например, "UDDUD" должен вернуться [U,D,D,U,D]тогда как любая строка, которая не содержит U или же D возвращается Nothing (например, "UDYD" возвращает 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

Я получаю следующую ошибку:

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

Как я понимаю, Just (D : findDirection xs) а также Just (U : findDirection xs) имеют тип [Direction]? Почему это так? Что я делаю не так, здесь?

Answer 1

Just (D : findDirection xs) а также Just (U : findDirection xs) имеют тип [Направление]? Почему это так? Что я делаю не так, здесь?

Нет, Just (D : findDirection xs) на самом деле плохо напечатан. Давайте разберем это сообщение об ошибке:

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

Мы используем Maybe [Direction] в точке, где мы должны использовать [Direction],

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

Ага. Мы используем (:) :: a -> [a] -> [a] неправильно. В конце концов, findDirection вернет Maybe [Direction]не [Direction], Нам нужно что-то вроде этого:

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

Теперь ваша функция может быть записана как

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

В качестве альтернативы, мы могли бы использовать consOnMaybe x = fmap (x:), В качестве дополнительного бонуса, вот вариант, который использует предопределенные функции и не имеет явной рекурсии (упражнение: понять, как это работает)

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

Answer 2

  data Direction = U | D
    deriving (Show, Eq)

  findDirection :: String -> Maybe [Direction]
  findDirection [] = Nothing
  findDirection dirs = sequence $ findDirection' dirs
    where
      findDirection' :: String -> [Maybe Direction]
      findDirection' (x:xs) =
        let x' = toDirection x in
          x' : case x' of
                Just _ -> findDirection' xs
                _ -> []
      findDirection' _ = []

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

------------------------ OR ------------------------

findDirection :: String -> Maybe [Direction]
  findDirection [] = Nothing
  findDirection dirs = traverse toDirection dirs
    where
      toDirection :: Char -> Maybe Direction
      toDirection 'U' = Just U
      toDirection 'D' = Just D
      toDirection _ = Nothing

> findDirection "UDDUD"
< Just [U,D,D,U,D]

> findDirection "UDYD"
< Nothing