F # String Pattern-Matching con caratteri jolly

Question

Come parte di un progetto mi sono assegnato come un modo per migliorare la mia conoscenza di F # e programmazione funzionale in generale, sto tentando di scrivere un algoritmo di corrispondenza di stringhe da zero senza utilizzare alcun cicli o variabili (o espressioni regolari, o String.Replace e amici). Poiché questo è puramente un progetto di apprendimento, non mi interessa nel miglior modo possibile per farlo, solo il modo migliore per farlo funzionale.

che sto cercando di scrivere una funzione che accetta un carattere jolly, una stringa modello, e una stringa di input come parametri. Se il modello non corrisponde all'ingresso, la funzione restituisce None. Se il modello non corrisponde l'ingresso, la funzione restituisce Some(str) dove str è qualunque parte della stringa di input soddisfi qualche jolly che avrebbero potuto essere presenti nella stringa modello.

ho questo per lo più a lavorare, e io includere il codice in un attimo. Ho scritto una funzione generica pattern-matching che funziona su qualsiasi elenco generico di tutto ciò che sostiene l'uguaglianza, e quindi una funzione di supporto che prende le stringhe e passa liste di personaggi alla funzione generica. Tutto questo funziona, tranne che per una cosa: il supporto per più caratteri jolly nella stringa del pattern non è molto buono - prende le corrispondenze per ogni carattere jolly e le concatena in un'unica stringa nell'output.

Ad esempio:

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

E 'l'ultima che sto cercando di risolvere. Idealmente mi piacerebbe per restituire un elenco di stringhe, piuttosto che una singola stringa, con ogni elemento della lista è la stringa che corrisponde un jolly. In caso contrario, posso probabilmente accontentarmi di una versione che restituisce solo la corrispondenza per il primo carattere jolly: sono i valori concatenati di entrambi i caratteri jolly di cui ho bisogno per sbarazzarmi. Non sono abbastanza sicuro di come affrontarlo.

Quindi, se qualcuno può suggerire come posso raggruppare i miei valori di ritorno con i caratteri jolly corrispondenti, sarei grato. Sono anche interessato a qualsiasi altro miglioramento del mio codice che potresti suggerire.

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

Probabilmente avete indovinato, ma questo fa parte di un'implementazione di chat-bot di Eliza in F #.

Answer 1

Da un punto di vista progettuale, mi piace l'idea di tornare un

'a list option 

dove esempio

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

Cioè, solo garantisce che, quando 'Alcune' viene restituito, la lunghezza della lista è uguale al numero di caratteri jolly, e gli elementi della lista sono le partite in ordine. Questo mi sembra sia semplice da implementare oltre che ragionevole da usare/consumare dal codice client.

(io sono chiaro se c'è qualche problema più profondo nel vostro lungo post.)

Sembra roba di divertimento!

EDIT

Ecco un codice aggiornato. Il mio istinto mi dice che non è tutto corretto, ma almeno funziona sui tuoi esempi.La chiave è quella di utilizzare

'a list list option 

poiche 'un è un personaggio, un' una lista è come una corda, e vogliamo una lista di stringhe. singleMatch avvia una nuova lista di stringhe, mentre longMatch si trova sul lato anteriore della stringa corrente.

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