字符串的复杂模式匹配

Question

我有一个字符串列表，如下所示：

xs = ["xabbaua", "bbbaacv", "ggfeehhaa", "uyyttaccaa", "ibbatb"]

我只想在列表中找到这样的字符串:和vocel后面跟两个b，后面跟任何字符，后面跟一个元音。像这样的简单匹配是如何在Haskell中完成的。有比正则表达式更好的解决方案吗？有人能帮我举个例子吗？谢谢。

Answer 1

您可以只将经典的过滤器函数与任何regexp库结合使用。您的模式非常简单，可以与任何regexp库一起使用：

filter (=~ "bb.[aeiuy]") xs

Haskell中regexp令人困惑的部分是，有一个非常强大的通用API (在regex-base中)，可以以相同的方式将它们用于所有特定的库和您希望的多结果类型(Bool，String，Int...)。对于基本用法，它应该主要按照您的意思工作(tm)。对于您的特定需求，regex-posix应该足够了(并且是随haskell平台一起提供的，因此不需要正常安装)。所以别忘了导入它：

import Text.Regex.Posix

如果你有其他需求，这个tutorial应该会向你展示regex API的基础知识，它现在有点过时了，但基本原理保持不变，只有regex-base的细节发生了变化。

Answer 2

一种方法是构建一种小型模式匹配语言，并将其嵌入Haskell中。

在您的示例中，模式基本上是字符规范的列表。让我们定义一种抽象字符，它的值将用作这样的规范，

data AbsChar  =  Exactly Char | Vowel | Any

再加上一个“解释器”，它会告诉我们一个字符是否与规范匹配：

(=?)  ::  AbsChar -> Char -> Bool
Exactly c' =? c  =  c == c'
Vowel      =? c  =  c `elem` "aeiou"
Any        =? c  =  True

例如，Vowel =? 'x'将生成False，而Vowel =? 'a'将生成True。

那么，一个模式实际上就是一个抽象字符的列表：

type Pattern  =  [AbsChar]

接下来，我们编写一个函数来测试字符串的前缀是否与给定的模式匹配：

matchesPrefix  ::  Pattern -> String -> Bool
matchesPrefix []       _         =  True
matchesPrefix (a : as) (c : cs)  =  a =? c && matchesPrefix as cs
matchesPrefix _        _         =  False

例如：

> matchesPrefix [Vowel, Exactly 'v'] "eva"
True
> matchesPrefix [Vowel, Exactly 'v'] "era"
False

因为我们不想将自己限制在匹配前缀，而是匹配单词中的任何位置，所以我们的下一个函数匹配字符串的每个结束段的前缀：

containsMatch  ::  Pattern -> String -> Bool
containsMatch pat  =  any (matchesPrefix pat) . tails

它使用可以在模块Data.List中找到的函数tails，但我们可以使用该函数来使此解释自包含，也可以轻松地定义我们自己：

tails  ::  [a] -> [[a]]
tails []          =  [[]]
tails l@(_ : xs)  =  l : tails xs

例如：

> tails "xabbaua"
["xabbaua","abbaua","bbaua","baua","aua","ua","a",""]

现在，最后，您要寻找的函数，从包含匹配片段的列表中选择所有字符串，简单地写成：

select  ::  Pattern -> [String] -> [String]
select  =  filter . containsMatch

让我们在您的示例中进行测试：

> let pat = [Vowel, Exactly 'b', Exactly 'b', Any, Vowel]
> select pat ["xabbaua", "bbbaacv", "ggfeehhaa", "uyyttaccaa", "ibbatb"]
["xabbaua"]

Answer 3

你可以试试这个函数，尽管这可能不是最好的方法：

elem' :: String -> String -> Bool
elem' p xs = any (p==) $ map (take $ length p) $ tails xs

用法：

filter (elem' "bb") ["xxbbaua", "bbbaacv", "ggfeehhaa", "uyyttaccaa", "bbbaab"]

或

bbFilter = filter (elem' "bb")