有没有办法在这个算法中不使用显式递归？

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.实际的算法很简单.地图包含已匹配的模式.最后是[a - >"red",b - >"blue"].如果下一个模式是我们之前看到过的模式,那么只需尝试匹配它,如果可以的话就重新下传.否则失败并返回false.

如果下一个模式是新的,只需尝试将新模式映射到字符串中的每个前缀并递归.

Answer 1

这与解析问题非常相似,所以让我们从解析器monad中获取提示:

• match 应返回解析的所有可能延续的列表
• 如果匹配失败,则应返回空列表
• 当前的分配集将是必须通过计算进行的状态

为了了解我们的目标,让我们假设我们有这个神奇的单子.尝试将"abba"与字符串匹配将如下所示:

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

test = runMatch matchAbba "redbluebluered"

事实证明,这个monad是List Monad上的State monad.List monad提供回溯,State monad包含当前的赋值和输入.

这是代码:

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")]]

另一件需要指出的是,将像"abba"这样的字符串转换为monadic值do var'a'; var'b'; var 'b'; var 'a'的代码就是:

sequence $ map var "abba"

更新:正如@Sassa NF指出的那样,要匹配您要定义的输入结束:

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

然后将其插入monad:

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