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

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 .实际算法很简单。该 map 包含已匹配的模式。最后是 [a -> "red", b -> "blue"]。如果下一个模式是我们以前见过的模式，只需尝试匹配它并尽可能递归。否则失败并返回 false。

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

Answer 1

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

match应该返回解析的所有可能延续的列表

如果匹配失败，它应该返回空列表

当前的分配集将是必须通过计算进行的状态

为了看看我们要去哪里，让我们假设我们有这个神奇的单子(monad)。尝试将 "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”这样的字符串转换为一元值 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