Esiste un modo per non utilizzare la ricorsione esplicita in questo algoritmo?

Question

Quindi il problema sto lavorando per far corrispondere un modello a un elenco, come questo: match "abba" "redbluebluered" -> True o match "abba" "redblueblue" -> False, ecc. Ho scritto un algoritmo che funziona, e penso che sia ragionevole, ma non sono sicuro se c'è un modo migliore per farlo senza ricorrere esplicitamente alla ricorsione.

import Data.HashMap.Strict as M 
match :: (Eq a, Eq k, Hashable k) => [k] -> [a] -> HashMap k [a] -> Bool 
match []  [] _ = True 
match []  _ _ = False 
match _  [] _ = False 
match (p:ps) s m = 
    case M.lookup p m of 
    Just v -> 
     case stripPrefix v s of 
     Just post -> match ps post m 
     Nothing -> False 
    Nothing -> any f . tail . splits $ s 
     where f (pre, post) = match ps post $ M.insert p pre m 
      splits xs = zip (inits xs) (tails xs) 

Lo definirei come match "abba" "redbluebluered" empty. L'algoritmo attuale è semplice. La mappa contiene gli schemi già abbinati. Alla fine è [a -> "rosso", b -> "blu"]. Se il modello successivo è quello che abbiamo visto prima, prova ad abbinarlo e ricorri se possibile. Altrimenti fallire e restituire false.

Se il modello successivo è nuovo, provare a mappare il nuovo modello su ogni singolo prefisso nella stringa e ricorsivamente verso il basso.

Answer 1

Questo è molto simile a un problema di analisi, così diamo un suggerimento dalla monade parser:

• match dovrebbe restituire un elenco di tutte le possibili continuazioni della parse
• se corrispondente fallisce essa deve restituire l'elenco vuoto
• gli attuali assegnazioni sarà stato che deve effettuata attraverso il calcolo

per vedere dove siamo diretti, di lasciare su Pensa che abbiamo questa monade magica. Il tentativo di abbinare "abba" contro una stringa sarà simile:

matchAbba = do 
    var 'a' 
    var 'b' 
    var 'b' 
    var 'a' 
    return() -- or whatever you want to return 

test = runMatch matchAbba "redbluebluered" 

Si scopre questo monade è la monade Stato sulla lista monade. La lista monad prevede il backtracking e la monade di stato trasporta i compiti correnti e l'input in giro.

Ecco il codice:

import Data.List 
import Control.Monad 
import Control.Monad.State 
import Control.Monad.Trans 
import Data.Maybe 
import qualified Data.Map as M 
import Data.Monoid 

type Assigns = M.Map Char String 

splits xs = tail $ zip (inits xs) (tails xs) 

var p = do 
    (assigns,input) <- get 
    guard $ (not . null) input 
    case M.lookup p assigns of 
    Nothing -> do (a,b) <- lift $ splits input 
        let assigns' = M.insert p a assigns 
        put (assigns', b) 
        return a 
    Just t -> do guard $ isPrefixOf t input 
        let inp' = drop (length t) input 
        put (assigns, inp') 
        return t 

matchAbba :: StateT (Assigns, String) [] Assigns 
matchAbba = do 
    var 'a' 
    var 'b' 
    var 'b' 
    var 'a' 
    (assigns,_) <- get 
    return assigns 

test1 = evalStateT matchAbba (M.empty, "xyyx") 
test2 = evalStateT matchAbba (M.empty, "xyy") 
test3 = evalStateT matchAbba (M.empty, "redbluebluered") 

matches :: String -> String -> [Assigns] 
matches pattern input = evalStateT monad (M.empty,input) 
    where monad :: StateT (Assigns, String) [] Assigns 
     monad = do sequence $ map var pattern 
        (assigns,_) <- get 
        return assigns 

prova, per esempio:

matches "ab" "xyz" 
-- [fromList [('a',"x"),('b',"y")],fromList [('a',"x"),('b',"yz")],fromList [('a',"xy"),('b',"z")]] 

Un'altra cosa da sottolineare è che il codice che trasforma una stringa come "abba" al valore monadico do var'a'; var'b'; var 'b'; var 'a' è semplicemente :

sequence $ map var "abba" 

Aggiornamento: Come @Sassa NF fa notare, per abbinare alla fine di in Mettere si vorrà definire:

matchEnd :: StateT (Assigns,String) []() 
matchEnd = do 
    (assigns,input) <- get 
    guard $ null input 

e poi inserirla in monade:

 monad = do sequence $ map var pattern 
        matchEnd 
        (assigns,_) <- get 
        return assigns 

Answer 2

Desidero modificare la firma e restituire più di Bool. La soluzione diventa allora:

match :: (Eq a, Ord k) => [k] -> [a] -> Maybe (M.Map k [a]) 
match = m M.empty where 
    m kvs (k:ks) vs@(v:_) = let splits xs = zip (inits xs) (tails xs) 
          f (pre, post) t = 
           case m (M.insert k pre kvs) ks post of 
           Nothing -> t 
           x  -> x 
          in case M.lookup k kvs of 
           Nothing -> foldr f Nothing . tail . splits $ vs 
           Just p -> stripPrefix p vs >>= m kvs ks 
    m kvs [] [] = Just kvs 
    m _ _ _ = Nothing 

Utilizzando il trucco noto di piegare per la produzione di una funzione che possiamo ottenere:

match ks vs = foldr f end ks M.empty vs where 
    end m [] = Just m 
    end _ _ = Nothing 
    splits xs = zip (inits xs) (tails xs) 
    f k g kvs vs = let h (pre, post) = (g (M.insert k pre kvs) post <|>) 
       in case M.lookup k kvs of 
        Nothing -> foldr h Nothing $ tail $ splits vs 
        Just p -> stripPrefix p vs >>= g kvs 

Qui match è la funzione di piegatura tutte le chiavi per la produzione di una funzione di prendere una Map e un stringa di a, che restituisce un Map di corrispondenze delle chiavi alle sottostringhe. La condizione per la corrispondenza della stringa di a nella sua interezza è tracciata dall'ultima funzione applicata da foldr - end. Se end viene fornito con una mappa e una stringa vuota di a, la corrispondenza ha esito positivo.

L'elenco di chiavi viene ripiegato utilizzando funzione f, che è dato quattro argomenti: la chiave corrente, la funzione g corrispondente al resto della lista delle chiavi (cioè o f piegata o end), la mappa di tasti già abbinato e il resto della stringa di a. Se la chiave è già stata trovata nella mappa, basta togliere il prefisso e alimentare la mappa e il resto a g. Altrimenti, prova ad alimentare la mappa modificata e il resto di a s per diverse combinazioni di split. Le combinazioni vengono tentate pigramente finché g produce Nothing in h.

Answer 3

Ecco un'altra soluzione, più leggibile, penso, e inefficiente come altre soluzioni:

L'idea è semplice: invece di avere uno Map, archiviare entrambi i modelli e le sottostringhe corrispondenti in un elenco. Quindi, quando incontriamo un pattern (Left p), sostituiamo tutte le occorrenze di questo pattern con una sottostringa e chiamiamo match' in modo ricorsivo con questa sottostringa in striping e ripetiamola per ciascuna sottostringa, che appartiene a inits di una stringa elaborata. Se incontriamo una sottostringa già abbinata (Right s), proviamo semplicemente a rimuovere questa sottostringa e chiamiamo match' in modo ricorsivo su un tentativo successivo o restituiamo False in caso contrario.