6

F# と関数型プログラミング全般の知識を向上させる方法として自分自身を割り当てたプロジェクトの一環として、ループや変数 (または正規表現、または文字列) を使用せずに、文字列パターン マッチング アルゴリズムをゼロから作成しようとしています。 .Replace とフレンズ)。これは純粋に学習プロジェクトであるため、私はそれを行うための最善の方法には興味がありません。それを行うための最善の機能的な方法だけです。

ワイルドカード文字、パターン文字列、および入力文字列をパラメーターとして受け入れる関数を作成しようとしています。パターンが入力と一致しない場合、関数は を返しますNone。パターンが入力と一致する場合、関数は、パターン文字列に存在する可能性のあるワイルドカードと一致した入力文字列の部分がSome(str)どこにあるかを返します。str

私はこれをほとんど機能させています。すぐにコードを含めます。等価性をサポートする任意の汎用リストで機能する汎用パターン マッチング関数を作成し、文字列を受け取って文字のリストを汎用関数に渡すヘルパー関数を作成しました。これはすべて機能しますが、1 つのことを除いて: パターン文字列での複数のワイルドカードのサポートはあまり良くありません。各ワイルドカードの一致を取得し、それらを連結して出力​​内の 1 つの文字列にします。

例えば：

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

それは私が修正しようとしている最後のものです。理想的には、リスト内の各要素が 1 つのワイルドカードに一致する文字列である、単一の文字列ではなく文字列のリストを返したいと考えています。それができない場合は、おそらく最初のワイルドカードの一致のみを返すバージョンで間に合わせることができます。削除する必要があるのは、両方のワイルドカードからの連結された値です。私はそれにアプローチする方法がよくわかりません。

したがって、一致したワイルドカードによって戻り値をグループ化する方法を誰かが提案できる場合は、感謝します。あなたが提案したいかもしれない私のコードへの他の改善にも興味があります.

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 チャット ボットの実装の一部です。

4

1 に答える 1

4

デザインの観点から、私は

'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")
于 2009-11-08T19:33:13.013 に答える