Greetings to all. I have two expressions that I would like to compare for tree structure. Here the tree terminal nodes are all from some set of symbols and I would like to know whether the two trees match where ideally I obtain a list of bindings that turn the first tree into the second. I tried building a wildcard pattern with different wildcards for each symbol and then invoking the match function. Unfortunately this did not work due to multiple wildcards appearing in sum terms, which the tutorial says will give ambiguous results like with a+$1+$2. For example, comparing L=Q(n,k)+Q(k,2) and Q(q,p)+Q(p,r) should give the consistent bindings (n => q, k => p, 2 => r). No such binding exists for L to Q(p,p)+Q(p,r) or Q(p,q)+Q(q,r)+Q(r,3) (different expression tree). The match Q(n+m+k,q) and Q(s+j+l, t) should go through and produce at least one binding such as (n=>s, m=>j, k=>l, q=>t). I understand that here we have permutations of the constituent terms of sums and products that need to be taken into account. Regards, Marko
BTW I ended up implementing it myself, code is available. These trees are of bounded depth and branch factor. A professional approach would make a difference here however. Regards, Marko
participants (1)
-
Marko Riedel