Haskell中的递归令牌器

Question

我在Haskell做作业，准备考试。当前任务要求在以下公式之后标记字符串:当运行"tokenize分离删除“时，它应该输出一个字符串列表。出现在字符串“分离”中的"str“中的每个字符都应该是一个字符的字符串。出现在字符串"remove“中的"str”中的每个字符都应该删除。没有出现在单独或移除中的字符应该捆绑在一起。

算例表明

tokenize "a + b* 12-def"   "+-*"   " "

应输出

["a", "+", "b", "*", "12", "-", "def"]

我下面的代码

tokenize :: String -> String -> String -> [String]
tokenize [] _ _  = []
tokenize [x] _ _ = [[x]]
tokenize (x:xs) a b     | x `elem` a = [x] : tokenize xs a b
                        | x `elem` b = tokenize xs a b
                        | otherwise = (x:head rest) : tail rest
                                where
                                        rest = tokenize xs a b

它在某种程度上起作用，问题是示例中的操作符与前面的字母捆绑在一起。

像这样

["a+","b*","12-","def"]

尽管操作符位于单独的字符串中。

Answer 1

首先，tokenize [x] _ _可能不是您想要的，因为tokenize "a" "" "a"最终成为了["a"]，而它可能应该是[]。第二，不要调用分隔符和删除列表Strings。它们只是[Char]s。下面没有区别，因为type String = [Char]，但是同义词的意义在于使语义更清晰，而且您并不真正将Strings用作Strings，因此您的函数不值得使用。此外，您应该将参数洗牌到tokenize seps rems str，因为这使得运行更容易。最后，您可能希望使用Data.Set而不是[Char]，但我不会在这里使用它来更接近这个问题。

问题本身是| otherwise = (x:head rest) : tail rest，它将任何非特殊字符插入到下一个令牌上，即使该标记被认为是分隔符。在您的例子中，head rest = "+"和x = 'a'就是其中的一个例子，您可以将它们连接起来，这样就有了"a+"。你需要更多的守卫。

(另外:您的缩进是混乱的：where子句绑定到整个等式，因此它在所有守卫中都是可见的。它应该缩进，这样就清楚了。)

tokenize :: [Char] -> [Char] -> String -> [String]
tokenize _ _ "" = []
tokenize seps rems (x:xs)
  | x `elem` rems                      = rest
  | x `elem` seps                      = [x]:rest
  -- Pattern guard: if rest has a single-char token on top and that token is a sep...
  | ([sep]:_) <- rest, sep `elem` seps = [x]:rest
  -- Otherwise, if rest has a token on top (which isn't a sep), grow it
  | (growing:rest') <- rest            = (x:growing):rest'
  -- Or else make a new token (when rest = [])
  | otherwise                          = [x]:rest
  where rest = tokenize seps rems xs

您也可以使用filter

tokenize seps rems = tokenize' . filter (not . flip elem rems)
  where tokenize' "" = []
        tokenize' (x:xs)
          | x `elem` seps                      = [x]:rest
          | ([sep]:_) <- rest, sep `elem` seps = [x]:rest
          | (growing:rest') <- rest            = (x:growing):rest'
          | otherwise                          = [x]:rest
          where rest = tokenize' xs