क्या इस एल्गोरिदम में स्पष्ट रिकर्सन का उपयोग करने का कोई तरीका नहीं है?

Question

तो समस्या यह है कि मैं किसी सूची में पैटर्न से मेल खाने पर काम कर रहा हूं, जैसे: match "abba" "redbluebluered" -> True या match "abba" "redblueblue" -> False, आदि। मैंने एक एल्गोरिदम लिखा जो काम करता है, और मुझे लगता है कि यह उचित समझ में आता है, लेकिन मुझे यकीन नहीं है अगर स्पष्ट रिकर्सन के बिना ऐसा करने का बेहतर तरीका है।

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) 

मैं इसे match "abba" "redbluebluered" empty की तरह कॉल करूंगा। वास्तविक एल्गोरिदम सरल है। मानचित्र में पहले से मेल खाने वाले पैटर्न शामिल हैं। अंत में यह [ए -> "लाल", बी -> "नीला"] है। यदि अगला पैटर्न एक है जिसे हमने पहले देखा है, तो बस इसे मिलान करने का प्रयास करें और अगर हम कर सकते हैं तो रिकर्स करें। अन्यथा असफल हो जाते हैं और झूठी वापसी करते हैं।

यदि अगला पैटर्न नया है, तो स्ट्रिंग में प्रत्येक एकल उपसर्ग के लिए नए पैटर्न को मैप करने का प्रयास करें और रिकर्सिंग करें।

Answer 1

यह बहुत एक पार्स समस्या के समान है, तो चलो पार्सर इकाई से एक संकेत करते हैं:

• match
• यदि मेल खाने वाला यह विफल पार्स के संभावित निरंतरता के सभी की एक सूची प्रदान करना चाहिए खाली सूची वापस आ जाएगी
• कार्य की वर्तमान सेट राज्य गणना के माध्यम से किया गया है कि हो जाएगा

देखने के लिए जहां हम बढ़ रहे हैं, के सु जाने मान लीजिए कि हमारे पास यह जादू मोनड है। एक स्ट्रिंग के खिलाफ "अब्बा" मिलान करने के प्रयास दिखेगा की तरह:

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

test = runMatch matchAbba "redbluebluered" 

यह पता चला इस इकाई सूची इकाई से अधिक राज्य इकाई है। सूची मोनैड बैकट्रैकिंग के लिए प्रदान करता है और राज्य मोनड में वर्तमान असाइनमेंट और इनपुट होता है।

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 

प्रयास करें, उदाहरण के लिए:

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

का कहना है के लिए एक और बात यह है कि कोड है जो monadic मान "अब्बा" जैसी एक स्ट्रिंग बदल देती है do var'a'; var'b'; var 'b'; var 'a' बस है

कोड यह :

sequence $ map var "abba" 

अपडेट: जैसा कि @ ससा एनएफ बताता है, के अंत में मिलान करने के लिए

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

और फिर इकाई में डालने: आपके द्वारा निर्धारित चाहता हूँ रख

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

Answer 2

मैं आपके हस्ताक्षर को संशोधित करना चाहता हूं और Bool से अधिक वापस करना चाहता हूं। आपका समाधान तो हो जाता है:

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 

एक समारोह का निर्माण करने के तह के ज्ञात चाल का उपयोग हम प्राप्त कर सकते हैं:

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 

यहाँ match है समारोह सभी कुंजियों तह एक समारोह एक Map और एक लेने के निर्माण करने के लिए a की स्ट्रिंग, जो सबस्ट्रिंग्स के लिए कुंजी के मैचों के Map लौटाती है। a की स्ट्रिंग से मेल खाने की स्थिति पूरी तरह से foldr - end द्वारा लागू अंतिम फ़ंक्शन द्वारा ट्रैक की जाती है। यदि end मानचित्र के साथ और a की एक खाली स्ट्रिंग प्रदान की जाती है, तो मैच सफल होता है।

कुंजी की सूची समारोह f का उपयोग कर मोड़ा जाता है, जो चार तर्क दिया जाता है: वर्तमान कुंजी, समारोह g (यानी या तो f मुड़ा हुआ, या end) कुंजी की सूची, पहले से ही कुंजी के नक्शे के शेष मिलान मिलान किया गया, और a की स्ट्रिंग का शेष। यदि कुंजी पहले से ही मानचित्र में पाई गई है, तो बस उपसर्ग को पट्टी करें और मानचित्र को फ़ीड करें और शेष को g पर रखें। अन्यथा, विभिन्न विभाजन संयोजनों के लिए संशोधित मानचित्र और a एस शेष को खिलाने का प्रयास करें। gNothingh में Nothing उत्पन्न करता है जब संयोजनों को आलसी ढंग से आज़माया जाता है।

Answer 3

यहाँ एक और समाधान, अन्य समाधान के रूप में अधिक पठनीय, मुझे लगता है, और के रूप में अक्षम है:

import Data.Either 
import Data.List 
import Data.Maybe 
import Data.Functor 

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

subst :: Char -> String -> Either Char String -> Either Char String 
subst p xs (Left q) | p == q = Right xs 
subst p xs  q   = q 

match' :: [Either Char String] -> String -> Bool 
match'   [] [] = True 
match' (Left p : ps) xs = or [ match' (map (subst p ixs) ps) txs 
           | (ixs, txs) <- tail $ splits xs] 
match' (Right s : ps) xs = fromMaybe False $ match' ps <$> stripPrefix s xs 
match'   _ _ = False 

match = match' . map Left 

main = mapM_ (print . uncurry match) 
    [ ("abba" , "redbluebluered"     ) -- True 
    , ("abba" , "redblueblue"      ) -- False 
    , ("abb"  , "redblueblue"      ) -- True 
    , ("aab"  , "redblueblue"      ) -- False 
    , ("cbccadbd", "greenredgreengreenwhiteblueredblue") -- True 
    ] 

विचार सरल है: Map रखने के बजाय, एक सूची में दोनों पैटर्न और मिलान किए गए सबस्ट्रिंग स्टोर करें। तो जब हम एक पैटर्न (Left p) का सामना करते हैं, तो हम इस सबस्ट्रिंग के साथ इस पैटर्न की सभी घटनाओं को प्रतिस्थापित करते हैं और इस सबस्ट्रिंग के साथ match' को दोबारा दबाते हैं, और प्रत्येक सबस्ट्रिंग के लिए इसे दोहराते हैं, जो एक संसाधित स्ट्रिंग के inits से संबंधित है। यदि हम पहले से मिलान किए गए सबस्ट्रिंग (Right s) का सामना करते हैं, तो हम केवल इस सबस्ट्रिंग को स्ट्रिप करने का प्रयास करते हैं, और लगातार प्रयास पर match' पर कॉल करें या अन्यथा False लौटाएं।