Come mappare (O String (a -> b)) a (O String [(a -> b)])

Question

cerco di trovare una soluzione su un esercizio di mio, con i seguenti requisiti:

• Abbiamo bisogno di spostare un oggetto contro una determinata sequenza.
• Una sequenza è composta da azioni.

Qui sono possibili azioni: F, L, R

• F: spostare in avanti
• L: ruotare di 90 ° a sinistra
• R: ruotare di 90 ° a destra

una sequenza è quindi rappresentato da una stringa, come questo:

"FFLRLFF"

voglio analizzare la sequenza sopra (e gestire gli errori) e quindi associare ogni azione a una funzione, come questo:

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 

Ora quello che voglio è qualcosa con la seguente firma:

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

Voglio analizzare una sequenza completa utilizzando più volte la funzione parseAction e non riesce quando restituisce A sinistra. Sono bloccato su come posso implementare questa funzione.

Avete qualche idea?

Answer 1

Questo appare come

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

dove

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

Quindi un'implementazione è semplicemente:

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

Per inciso, si noti che il vostro parseAction non vuole davvero essere utilizzando il tipo (a -> a), che deve funzionare per qualsiasi tipo a, scelto dalla persona che chiama la funzione. Si preferisce invece utilizzare il tipo (Location -> Location), dove Posizione è il tipo che si sta utilizzando per rappresentare la posizione dell'oggetto che si sta spostando.

Equivalentemente a mapM, è possibile (come suggerito da duplode) utilizzare invece la traversa, che è leggermente più generale. Nelle versioni recenti della traversata di GHC è in Preludio; nelle versioni precedenti potrebbe essere necessario importarlo da Data.Traversable per usarlo.

Answer 2

Se si esegue il mapping di parseAction sulla stringa di origine, si ottiene una parte del percorso.In GHCi:

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

Così ora si può piegare questo in un unico valore O

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" 

Tuttavia questo ha un caso fastidioso "errore". Quindi, per sbarazzarsi di quella:

import Data.Either 

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

Answer 3

Nota: Per chiarezza in più, ho intenzione di utilizzare Thing -> Thing piuttosto che a -> a.

È necessario traverse:

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

Nel tuo caso, è t[], e così, t Char è String. traverse parseAction attraverserà il numero String, generando un'azione per ogni Char e raccogliendo i risultati. traverse utilizza l'istanza Applicative di Either per gestire Left se Right s, fermandosi al primo Left.

P.S .: mapM nella risposta di amalloy è, in questo caso, equivalente a traverse. L'unica differenza tra loro è che traverse è più generale, in quanto richiede solo Applicative (anziché Monad) dal funtore che si usa mentre si attraversa.