F # String Pattern-Matching with Wildcards

Question

Как часть проекта, я назначил себя как способ улучшить свои знания о 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)) 

Вы, наверное, догадались, но это часть реализации чата-робота Eliza в F #.

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 

То есть, просто гарантировать, что когда «Некоторые» возвращается, длина списка равна числу групповых символов, а также элементы списка являются матчи в порядке. Мне кажется, что это просто реализовать, а также разумно использовать клиентский код для использования/потребления.

(я неясно, есть ли более глубокий вопрос в вашем длинном посте.)

Похож позабавятся!

EDIT

Вот обновленный код. Моя кишка говорит мне, что это не совсем правильно, но по крайней мере работает на ваших примерах.Ключ должен использовать

'a list list option 

поскольку «а есть герой,» список, как строка, и мы хотим, чтобы список строк. 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")