Haskell正则表达式check函数Sing与(:.:)分支补全及技术咨询

我有多年C/C++编程经验，但现在被一项Haskell作业难住了——完全无从下手。作业要求补全check函数里Sing和(:.:)这两个分支的定义，可我对Regex类型、Maybe String的含义一头雾水，大量Haskell语法也看不懂，查了视频资料还是没搞明白。我已经会编译代码并在GHCI里运行，但不知道怎么测试这个函数。

先贴一下相关代码：

Regex类型定义 #

data Regex = Epsilon -- empty string
           | Sing Char -- single character
           | (:.:) Regex Regex -- concatenation
           | (:|:) Regex Regex -- alternation
           | Plus Regex -- repetition (one or more)

未完成的check函数 #

check :: Regex -> String -> Maybe String
check Epsilon cs = Just cs
check (Sing c) (c':cs) = c' + cs  -- 这里是我瞎写的，完全不对
check (r1 :.: r2) cs = r1 + r2    -- 这个也编译不过，不知道怎么写
check (r1 :|: r2) cs = case check r1 cs of
    Just cs' -> Just cs'
    Nothing -> check r2 cs
check (Plus r) cs = case check r cs of
    Just cs' -> case check (Plus r) cs' of
        Just cs'' -> Just cs''
        Nothing -> Just cs'
    Nothing -> Nothing
check _ _ = Nothing

先帮你理清几个核心概念（用C/C++类比） #

• Maybe String：这玩意儿相当于C++里的std::optional<std::string>。Just "abc"就像optional<string>{"abc"}，表示匹配成功，返回剩余的字符串；Nothing就像nullopt，表示匹配失败。
• Haskell的字符串：本质是[Char]，也就是字符的链表，和C++里的std::list<char>逻辑类似，c':cs是拆分字符串——第一个字符是c'，剩下的字符序列是cs。

正确的Sing分支写法 #

Sing c代表匹配单个字符c，逻辑应该是：

1. 如果输入字符串能拆成c':cs（也就是不为空），判断c和c'是否相等
2. 相等的话，匹配成功，返回剩余的字符串cs（包装成Just cs）
3. 不相等或者输入字符串为空的话，返回Nothing

代码应该改成：

check (Sing c) (c':cs) | c == c' = Just cs
check (Sing _) _ = Nothing

类比C++的伪代码：

optional<string> check(Sing c, string cs) {
    if (!cs.empty() && cs[0] == c.val) {
        return optional<string>(cs.substr(1));
    } else {
        return nullopt;
    }
}

正确的(:.:)分支写法 #

(:.:)是正则的连接操作（比如a连接b就是匹配ab），逻辑是：

1. 先用第一个正则r1匹配输入字符串cs
2. 如果r1匹配成功，得到剩余字符串cs'，再用第二个正则r2匹配cs'，返回这个结果
3. 如果r1匹配失败（返回Nothing），直接返回Nothing

代码应该改成：

check (r1 :.: r2) cs = case check r1 cs of
    Just cs' -> check r2 cs'
    Nothing -> Nothing

类比C++的伪代码：

optional<string> check(Concat r1, r2, string cs) {
    auto res1 = check(r1, cs);
    if (res1.has_value()) {
        return check(r2, res1.value());
    } else {
        return nullopt;
    }
}

怎么在GHCI里测试？ #

加载你的代码文件（假设叫Regex.hs）：

:load Regex.hs

然后就可以直接调用check函数测试各种情况：

• 测试Sing：check (Sing 'a') "abc" 应该返回Just "bc"；check (Sing 'a') "def" 返回Nothing
• 测试连接：check (Sing 'a' :.: Sing 'b') "abc" 返回Just "c"；check (Sing 'a' :.: Sing 'b') "acb" 返回Nothing
• 测试其他分支：比如check Epsilon "hello" 返回Just "hello"；check (Sing 'a' :|: Sing 'b') "bcd" 返回Just "cd"

内容的提问来源于stack exchange，提问作者Programmer