Как карта (либо String (а -> б)) к (или String [(а -> б)])

Question

Я пытаюсь найти решение в порядке осуществления моей, с учетом следующих требований:

• Нам нужно переместить объект против данной последовательности.
• Последовательность состоит из действий.

Вот возможные действия: F, L, R

• F: двигаться вперед
• L: поворот на 90 ° влево
• R: поворот на 90 ° вправо

последовательность затем представляется строкой, например:

"FFLRLFF"

Я хочу, чтобы разобрать вышеуказанную последовательность (и обработка ошибок), а затем связать каждое действие на функцию, например:

parseAction :: Char -> Either String (a -> a) 
parseAction 'F' = Right moveForward 
parseAction 'L' = Right turnLeft 
parseAction 'R' = Right turnRight 
parseAction s = Left ("Unkown action : " ++ [s]) 

-- Implementation omitted 
moveForward :: a -> a 
turnLeft :: a -> a 
turnRight :: a -> a 

Теперь то, что я хочу что-то со следующей подписью:

parseSequence :: String -> Either String [(a -> a)] 

Я хочу разобрать полную последовательность, используя много раз parseAction, и не работает, когда тот возвращается влево. Я зациклился на том, как я могу реализовать эту функцию.

Есть ли у вас идеи?

Answer 1

Это выглядит как

mapM :: Monad m => (a -> m b) -> [a] -> m [b] 

где

a ~ Char 
b ~ (a -> a) 
m ~ (Either String) 

Так реализация просто:

parseSequence :: String -> Either String [a -> a] 
parseSequence = mapM parseAction 

Как и в сторону, обратите внимание, что ваш parseAction действительно не хочет быть используя тип (a -> a), который должен работать для любой тип a, выбранный лицом, вызывающим функцию. Вместо этого вы хотите, чтобы он использовал тип (Location -> Location), где Location - это тип, который вы используете для представления местоположения объекта, который вы перемещаете.

Эквивалентно mapM, вы можете (как предложено duplode) вместо этого использовать траверс, который немного более общий. В последних версиях трассы GHC в Prelude; в более старых версиях вам, возможно, придется импортировать его из Data.Traversable, чтобы использовать его.

Answer 2

Если вы сопоставляете parseAction с исходной строкой, вы получаете часть пути.В GHCi:

> :type map parseAction "FFRRF" 
[Either String (a->a)] 

Итак, теперь вы можете сложить это в одно значение Либо

validActions = foldr f (Right []) 
    where 
     f (Left str) _ = Left str 
     f (Right x) (Right xs) = Right (x:xs) 
     f (Right x) (Left str) = error "Can't happen" 

Однако это имеет раздражающую «ошибка» случай. Таким образом, чтобы избавиться от этого:

import Data.Either 

validActions vs = if null ls then Right rs else Left $ head ls 
    where (ls, rs) = partitionEithers vs 

Answer 3

Примечание: Для дополнительной ясности, я собираюсь использовать Thing -> Thing, а не a -> a.

Вам нужно traverse:

traverse parseAction 
    :: Traversable t => t Char -> Either String (t (Thing -> Thing)) 

В вашем случае, t является [], и так, t Char является String. traverse parseAction будет проходить через String, генерируя одно действие для каждого Char и собирая результаты. traverse использует Applicative экземпляр Either для обработки Left s и Right s, останавливаясь при первом Left.

P.S .: mapM в ответе амаллоя, в данном случае эквивалентно traverse. Единственная разница между ними заключается в том, что traverse является более общим, так как требуется только Applicative (а не Monad) от функтора, который вы используете во время прохождения.