Строковое сопоставление с образцом F# с подстановочными знаками
Как часть проекта я назначил меня способом улучшить мое знание F# и функционального программирования в целом, я пытаюсь записать строковый алгоритм сопоставления с образцом с нуля, не используя циклов или переменных (или регулярные выражения или Строка. Замена и друзья). Поскольку это - просто проект изучения, мне не интересно самым лучшим способом сделать это, просто лучший функциональный способ сделать это.
Я пытаюсь записать функцию, которая принимает подстановочный символ, строку образца и входную строку как параметры. Если шаблон не соответствует входу, функциональным возвратам 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#.
1 ответ
From a design point of view, I like the idea of returning an
'a list option
where e.g.
None // it did not match
Some[] // matched, input had 0 wildcards
Some["foo";"bar"] // matched, input has 2 wildcards, "foo" matched 1st, "bar" 2nd
That is, just guarantee that when 'Some' is returned, the length of the list equals the number of wildcards, and the elements of the list are the matches in order. This seems to me to be straightforward to implement as well as reasonable for client code to use/consume.
(I am unclear if there is any deeper question in your long post.)
Looks like fun stuff!
EDIT
Here's some updated code. My gut tells me it's not all correct, but it at least works on your examples. The key is to use
'a list list option
since 'a is a character, an 'a list is like a string, and we want a list of strings. singleMatch starts a new list of strings, whereas longerMatch is consing onto the front of the current string.
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")