F # String Pattern-Matching with Wildcards

Question

Como parte de un proyecto que me he asignado como una forma de mejorar mi conocimiento de F # y la programación funcional en general, intento escribir un algoritmo de coincidencia de patrones de cuerdas desde cero sin usar ningún bucles o variables (o expresiones regulares, o String.Replace y amigos). Como se trata de un proyecto puramente de aprendizaje, no estoy interesado en la mejor manera posible de hacerlo, solo la mejor manera funcional de hacerlo.

Estoy tratando de escribir una función que acepte un carácter comodín, una cadena de patrón y una cadena de entrada como parámetros. Si el patrón no coincide con la entrada, la función devuelve None. Si el patrón coincide con la entrada, la función devuelve Some(str) donde str es cualquier parte de la cadena de entrada que coincida con cualquier comodín que pueda haber estado presente en la cadena del patrón.

Tengo esto principalmente funcionando, e incluiré el código en un momento. He escrito una función de coincidencia de patrones genérica que funciona en cualquier lista genérica de cualquier cosa que admita igualdad, y luego una función auxiliar que toma cadenas y pasa listas de caracteres a la función genérica. Todo esto funciona, excepto por una cosa: el soporte para múltiples comodines en la cadena de patrones no es muy bueno: toma las coincidencias para cada comodín y las concatena en una sola cadena en la salida.

Por ejemplo:

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

Es el último que estoy tratando de arreglar. Idealmente, me gustaría devolver una lista de cadenas en lugar de una sola cadena, con cada elemento de la lista como la cadena que coincide con un comodín. De lo contrario, probablemente me las arreglaré con una versión que solo devuelve la coincidencia para el primer comodín: son los valores concatenados de ambos comodines de los que debo deshacerme. No estoy muy seguro de cómo abordarlo.

Así que si alguien puede sugerir cómo puedo agrupar mis valores devueltos por qué comodín concuerdan, lo agradecería. También me interesan otras mejoras a mi código que pueda sugerir.

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

probablemente has adivinado, pero esto es parte de una implementación chat-bot Eliza en F #.

Answer 1

Desde el punto de vista del diseño, me gusta la idea de retornar un

'a list option 

donde, por ejemplo,

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

Eso es, simplemente garantizar que cuando se devuelve 'Algunas', la longitud de la lista es igual al número de comodines, y los elementos de la lista son los partidos de promoción. Esto me parece sencillo de implementar y razonable para que el código del cliente use/consuma.

(no tengo muy claro si hay alguna pregunta más profunda en su puesto de largo.)

Parece que la materia de diversión!

EDIT

Aquí hay algunos códigos actualizados. Mi instinto me dice que no todo es correcto, pero al menos funciona con tus ejemplos.La clave es usar

'a list list option 

ya que 'a es un personaje, una' una lista es como una cadena, y queremos una lista de cadenas. singleMatch comienza una nueva lista de cadenas, mientras que longerMatch está consiguiendo en el frente de la cadena actual.

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