需要帮助解决haskell regex操作函数

Question

定义

firsts :: RE sym -> [sym]
firsts = undefined

稀土数据

data RE sym -- sym is type of alphabet symbols
    = RSym sym  -- match single symbol
    | REps  -- match empty string
    | RZero  -- match nothing
    | RStar (RE sym)  -- choice
    | RPlus (RE sym)  -- concatenation
    | RAlt (RE sym) (RE sym) -- 0+ repetition
    | RSeq (RE sym) (RE sym) -- 1+ repetition
    deriving (Show)

正则表达式中的字母表

data Alphabet = A | B | C deriving (Show, Eq)

firsts re返回一个列表，其中包含在re语言中的某个字符串中首先出现的每个符号。例如，如果re表示“A(C_在这种情况下，第一次re可能返回A，B。

注意，类型签名不包括Eq sym或Ord sym。这意味着您的代码将无法对其返回的符号列表中的重复项进行排序或删除。您的代码必须满足的要求如下：

返回的列表必须是有限的(即使列表中的语言是infinite!)

• every符号，对于语言中的每个字符串，列表中的某个字符串中的第一个符号必须是

• 中的第一个符号，其第一个符号必须出现在列表中，单个符号可以以任何顺序出现，并且可以重复任何有限的次数。)

Answer 1

其思想是分析正则表达式，而不是为该正则表达式生成所有可能的字符串。例如，RSym sym显然将sym作为第一个(也是唯一的)字符，而REps则没有开始字符。

因此，这意味着您应该定义一个旨在查找初始字符的函数。因此，您可以实现这样的功能：

firsts :: RE sym -> [sym]
firsts (RSym sym) = [sym]
firsts REps = []
firsts RZero = …
firsts (RStar sub) = …
firsts (RPlus sub) = …
firsts (RAlt sub1 sub2) = …
firsts (RSeq sub1 sub2) = …

其中sub、sub1和sub2是子规则。因此，有些正则表达式必须进行递归调用，才能找到subregex(es)的第一个字符。

对于(RSeq sub1 sub2)，您需要创建一个助手函数matchEmpty :: RE sym -> Bool，以检查正则表达式是否与空字符串匹配。如果是这样，那么sub2的第一个字符可以是正则表达式的第一个字符，而如果sub1与空字符串不匹配，那么这是不可能的。