is it possible to do wildcard search structure using match

# is it possible to do wildcard search structure using match

• Thursday, April 26, 2012 7:24 AM

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

### All Replies

• Thursday, April 26, 2012 8:33 AM

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

• Marked As Answer by Thursday, April 26, 2012 10:30 AM
•
• Thursday, April 26, 2012 9:53 AM

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

• Thursday, April 26, 2012 9:56 AM

You miss Prop discriminator handling in ExactMatch, and in SearchPattern
• Edited by Thursday, April 26, 2012 9:57 AM
•
• Thursday, April 26, 2012 10:10 AM

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

• Thursday, April 26, 2012 10:14 AM

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?

• Thursday, April 26, 2012 10:23 AM

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

• Edited by Thursday, April 26, 2012 10:26 AM
•
• Thursday, April 26, 2012 10:28 AM

Now just search (or exact match) Disj(Neg(Wildcard), Wildcard) depending on what you need.
• Marked As Answer by Thursday, April 26, 2012 10:30 AM
•
• Thursday, April 26, 2012 10:31 AM

very useful trick

The will of planet