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

Question

正如我已经指派我作为提高我的F#和一般功能编程知识的方式在项目中的一部分,我试图从头开始写一个字符串的模式匹配算法,而无需使用任何循环或变量(或正则表达式或字符串.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 chat-bot实现的一部分.

Answer 1

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

'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 启动一个新的字符串列表，而 longMatch 则指向当前字符串的前面。

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")