F#字符串模式匹配与通配符

Question

F#字符串模式匹配与通配符

6

作为一个项目的一部分，我给自己分配了一个任务来提高我的F#和函数式编程的知识，我正在尝试编写一个字符串模式匹配算法，而不使用任何循环或变量（也不使用正则表达式、String.Replace等）。由于这只是一个学习项目，我对如何最好地完成它不感兴趣，只关心最佳的函数式方法。

我正在尝试编写一个函数，它接受通配符字符、模式字符串和输入字符串作为参数。如果模式与输入不匹配，则函数返回None。如果模式与输入匹配，则函数返回Some(str)，其中str是匹配模式中可能存在的任何通配符的输入字符串的一部分。

我已经基本实现了这个功能，并将在下面附上代码。我编写了一个通用的模式匹配函数，它适用于任何支持相等性的任何泛型列表，然后是一个帮助函数，它接受字符串并将字符列表传递给通用函数。这一切都可以工作，除了一个问题：模式字符串中多个通配符的支持不是很好——它将每个通配符的匹配结果连接到一起形成单个字符串输出。

例如：

> strMatch '*' "foo" "bar";;
val it : string option = None

> strMatch '*' "test" "test";;
val it : string option = Some ""

> strMatch '*' "functional programming is *" "functional programming is fun";;
val it : string option = Some "fun"

> strMatch '*' "* and *" "you and me";;
val it : string option = Some "youme"

我正在努力解决最后一个问题。理想情况下，我想返回一个字符串列表，而不是单个字符串，列表中的每个元素都是匹配一个通配符的字符串。如果无法实现这一点，我可能只能返回第一个通配符的匹配结果 - 我需要摆脱的是来自两个通配符的连接值。我只是不太确定如何解决它。

因此，如果有人能建议我如何根据它们匹配的通配符对我的返回值进行分组，我将不胜感激。我还对您可能想要建议的代码改进感兴趣。

let rec doMatch (wildcard:'a) (pat:'a list) (input:'a list) : 'a list option =
    let singleMatch p i =
        match (p, i) with
        | phd :: ptl, ihd :: itl ->
            if phd = wildcard then
                match doMatch wildcard ptl itl with
                | None -> None
                | Some x -> Some(ihd :: x)
            else None
        | _ -> None

    let longerMatch p i =
        match (p, i) with
        | phd :: ptl, ihd :: itl ->
            if phd = wildcard then
                match doMatch wildcard p itl with
                | None -> None
                | Some x -> Some(ihd :: x)
            else None
        | _ -> None

    match (pat, input) with
    | [], [] -> Some([])
    | [], _::_ -> None
    | _::_, [] -> None
    | phd :: ptl, ihd :: itl ->
        if phd <> wildcard then
            if phd = ihd then doMatch wildcard ptl itl
            else None
        else
            match singleMatch pat input with
            | Some x -> Some(x)
            | None -> longerMatch pat input

let strMatch (wildcard:char) (pat:string) (input:string) =
    match doMatch wildcard (List.ofSeq pat) (List.ofSeq input) with
    | None -> None
    | Some x -> Some(new string(Array.ofList x))

你可能已经猜到了，但这是F#中Eliza聊天机器人实现的一部分。

- Joel Mueller

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Brian · Accepted Answer

从设计角度来看，我喜欢返回一个

'a list option

例如，在哪里。

None              // it did not match
Some[]            // matched, input had 0 wildcards
Some["foo";"bar"] // matched, input has 2 wildcards, "foo" matched 1st, "bar" 2nd

也就是说，只要确保返回'Some'时列表的长度等于通配符的数量，并且列表的元素按顺序与匹配项相同即可。这对我来说很容易实现，对客户端代码使用/消耗也很合理。

（我不确定你的长篇帖子中是否有任何更深入的问题。）

看起来很有趣！

编辑

以下是更新后的代码。我的直觉告诉我它并不全正确，但它至少在您的示例上有效。关键是使用

。

'a list list option

由于'a是一个字符，'a列表类似于字符串，我们需要一个字符串列表。singleMatch开始一个新的字符串列表，而longerMatch则将其添加到当前字符串的前面。

let rec doMatch (wildcard:'a) (pat:'a list) (input:'a list) 
           : 'a list list option =
    let singleMatch p i =
        match (p, i) with
        | phd :: ptl, ihd :: itl ->
            if phd = wildcard then
                match doMatch wildcard ptl itl with
                | None -> None
                | Some xs -> Some([ihd]::xs)
            else None
        | _ -> None

    let longerMatch p i =
        match (p, i) with
        | phd :: ptl, ihd :: itl ->
            if phd = wildcard then
                match doMatch wildcard p itl with
                | None -> None
                | Some ([]) -> Some([[ihd]])
                | Some (x::xs) -> Some((ihd :: x)::xs)
            else None
        | _ -> None

    match (pat, input) with
    | [], [] -> Some([])
    | [], _::_ -> None
    | _::_, [] -> None
    | phd :: ptl, ihd :: itl ->
        if phd <> wildcard then
            if phd = ihd then doMatch wildcard ptl itl
            else None
        else
            match singleMatch pat input with
            | Some x -> Some(x)
            | None -> longerMatch pat input

let strMatch (wildcard:char) (pat:string) (input:string) =
    match doMatch wildcard (List.ofSeq pat) (List.ofSeq input) with
    | None -> None
    | Some x -> Some(x|>List.map (fun chList -> new string(Array.ofList chList)))

printfn "%A" (strMatch '*' "foo" "bar")
printfn "%A" (strMatch '*' "test" "test")
printfn "%A" (strMatch '*' "functional programming is *" 
                           "functional programming is fun")
printfn "%A" (strMatch '*' "* and *" "you and me")