is it possible to do wildcard search structure using match

Question

for example

search Disj(Neg(*), *)

let rec SearchPattern(source : expr, pattern : expr, found : bool byref) =
    match source with
    | pattern -> found <- true;
    | Neg(A) -> SearchPattern(A, pattern, &found); 
    | Conj(A,B) -> SearchPattern(A, pattern, &found); SearchPattern(B, pattern, &found); 
    | Disj(A,B) -> SearchPattern(A, pattern, &found); SearchPattern(B, pattern, &found);

let test1 = Conj(Disj(Neg(Conj(Prop("A"),Prop("D"))), Disj(Prop("B"),Prop("E"))), Prop("C"))
let mutable f = false
SearchPattern(test1, Disj(Neg(Prop("BC")), Prop("CB")) , &f)

Answer 1

Your code is actually wrong since in "| pattern -> found <- true" pattern does not refer to the function parameter, but rather is a new value, copy of source.

As of your question, you need to add special cases to expr type that would describe wildcard like this:

type expr =
  | Neg of expr
  | Conj of expr * expr
  | Disj of expr * expr
  | Wildcard

Then you need a function, that checks if some expr exactly matches some pattern like this:

let rec ExactMatch source pattern =
  match source, pattern with
  | _, Wildcard -> true
  | Neg(s), Neg(p) -> ExactMatch s p
  | ...
  | _, _ -> false

And finally:

if ExactMatch source pattern then
  found <- true
else
  match source with
  | Neg(... the rest of your match code
  | Wildcard -> failwith "source must not contain wildcards"

Answer 2

after tried , search is false, is the following code correct?

let rec ExactMatch(source : expr, pattern : expr) =
    match source, pattern with
    | _, Wildcard -> true
    | Neg(s), Neg(p) -> ExactMatch(s, p); 
    | Conj(A,B), Conj(C,D) -> ExactMatch(A, C); ExactMatch(B, D); 
    | Disj(A,B), Disj(C,D) -> ExactMatch(A, C); ExactMatch(B, D);
    | _, _ -> false
    
//let test1 = Conj(Disj(Neg(Conj(Prop("A"),Prop("D"))), Disj(Prop("B"),Prop("E"))), Prop("C"))
let test1 = Conj(Disj(Neg(Prop("A")),Prop("D")), Disj(Prop("B"),Prop("E")))
let mutable f = false
let rec SearchPattern(source : expr, pattern : expr, found : bool byref) =
    if ExactMatch(source, pattern) = true then
        found <- true
    else
        match source with
        | Neg(A) -> SearchPattern(A, pattern, &found); 
        | Conj(A,B) -> SearchPattern(A, pattern, &found); SearchPattern(B, pattern, &found); 
        | Disj(A,B) -> SearchPattern(A, pattern, &found); SearchPattern(B, pattern, &found);
        | _ -> Console.Write("") 
SearchPattern(test1, Disj(Neg(Prop("A")), Prop("D")), &f)
Console.WriteLine(f.ToString())

---

The will of planet

Answer 3

You miss Prop discriminator handling in ExactMatch, and in SearchPattern

Answer 4

if wildcard, Prop can be anything, is it the following handling correct?

let rec ExactMatch(source : expr, pattern : expr) =
    match source, pattern with
    | _, Wildcard -> true
    | Neg(s), Neg(p) -> ExactMatch(s, p); 
    | Conj(A,B), Conj(C,D) -> ExactMatch(A, C); ExactMatch(B, D); 
    | Disj(A,B), Disj(C,D) -> ExactMatch(A, C); ExactMatch(B, D);
    | Prop(A), Prop(B) -> false
    | _, _ -> false
    
//let test1 = Conj(Disj(Neg(Conj(Prop("A"),Prop("D"))), Disj(Prop("B"),Prop("E"))), Prop("C"))
let test1 = Conj(Disj(Neg(Prop("A")),Prop("D")), Disj(Prop("B"),Prop("E")))
let mutable f = false
let rec SearchPattern(source : expr, pattern : expr, found : bool byref) =
    if ExactMatch(source, pattern) = true then
        found <- true
    else
        match source with
        | Neg(A) -> SearchPattern(A, pattern, &found); 
        | Conj(A,B) -> SearchPattern(A, pattern, &found); SearchPattern(B, pattern, &found); 
        | Disj(A,B) -> SearchPattern(A, pattern, &found); SearchPattern(B, pattern, &found);
        | Prop(A) -> Console.Write("")
        | _ -> Console.Write("") 
SearchPattern(test1, Disj(Neg(Prop("A")), Prop("D")), &f)
Console.WriteLine(f.ToString())

---

The will of planet

Answer 5

Wildcard case in ExactMatch is handled by the first line. Props match each other when their strings match each other?

Do you understand what are you trying to do?

Answer 6

half understand

after edit, it can search true, however, string in Prop must also be matched, is it possible to test whether match

Disj(Neg(*), *)  where * can be anything i.e. any type expr

in fact

i write SearchPattern(test1, Disj(Neg(Prop("A")), Prop("D")), &f) not totally correct,

as i can not use something to represent wildcard so i use Prop("A") and Prop("D")

actually they can be Conj, Disj or any other expr type

let rec ExactMatch(source : expr, pattern : expr) =
    match source, pattern with
    | _, Wildcard -> true
    | Neg(s), Neg(p) -> ExactMatch(s, p); 
    | Conj(A,B), Conj(C,D) -> ExactMatch(A, C); ExactMatch(B, D); 
    | Disj(A,B), Disj(C,D) -> ExactMatch(A, C); ExactMatch(B, D);
    | Prop(A), Prop(B) -> if A <> B then 
                            false
                          else
                            true
    | _, _ -> false
    
//let test1 = Conj(Disj(Neg(Conj(Prop("A"),Prop("D"))), Disj(Prop("B"),Prop("E"))), Prop("C"))
let test1 = Conj(Disj(Neg(Prop("A")),Prop("D")), Disj(Prop("B"),Prop("E")))
let mutable f = false
let rec SearchPattern(source : expr, pattern : expr, found : bool byref) =
    if ExactMatch(source, pattern) = true then
        found <- true
    else
        match source with
        | Neg(A) -> SearchPattern(A, pattern, &found); 
        | Conj(A,B) -> SearchPattern(A, pattern, &found); SearchPattern(B, pattern, &found); 
        | Disj(A,B) -> SearchPattern(A, pattern, &found); SearchPattern(B, pattern, &found);
        | Prop(A) -> Console.Write("")
        | _ -> Console.Write("") 
SearchPattern(test1, Disj(Neg(Prop("A")), Prop("D")), &f)
Console.WriteLine(f.ToString())

---

The will of planet

Answer 7

Now just search (or exact match) Disj(Neg(Wildcard), Wildcard) depending on what you need.

Answer 8

very useful trick

---

The will of planet