2

我有一个看起来像这样的字符串列表：

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

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

4

4 回答 4

3

一种方法是构建一种小型模式匹配语言并将其嵌入到 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

由于我们不想限制自己匹配前缀，而是匹配单词中的任何位置，所以我们的 next 函数匹配字符串每个结尾段的前缀：

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

它使用了tails可以在模块中找到的功能Data.List，但是我们可以使这个解释自成一体，也可以轻松地定义自己：

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"]
于 2012-07-12T10:01:05.903 回答
3

您可以将经典过滤器功能与任何正则表达式库结合使用。您的模式很简单，可以与任何正则表达式库一起使用：

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

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

import Text.Regex.Posix

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

于 2012-07-12T12:47:49.083 回答
1

好吧，你可以试试这个功能，虽然这可能不是最好的方法：

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")
于 2012-07-12T01:16:07.870 回答
1

好吧，如果你绝对反对使用正则表达式，你可以只使用模式匹配和递归来做到这一点，尽管它很难看。

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

vowel = "aeiou"

filter' strs = filter matches strs

matches [] = False
matches str@(x:'b':'b':_:y:xs)
     | x `elem` vowel && y `elem` vowel = True
     | otherwise = matches $ tail str
matches (x:xs) = matches xs

调用filter' xs将返回["xabbaua"]，我认为这是所需的结果。

于 2012-07-12T02:42:55.713 回答