I adapted a general algorithm to perform structural matching on list-based
trees (like our trees). My code is here
https://github.com/mrocklin/unify
It works on any trees where each node can be described as a type (like our
Add, Mul) and a list of children (like our args). It also handles
associative operations well. For example if you want to match
Add(a, b, c)
Add(x, y)
It will rearrange the first expression so that the number of args match. In
this case it will test each of the two options.
Add(a, Add(b, c))
Add(Add(a, b), c)
As a result this code returns many possible matches. It does this lazily
using generators.
Standard SymPy method
In [1]: p, q = map(Wild, 'pq')
In [2]: (x+y+z).match(p+q)
Out[2]: {p: y + z, q: x}
Structural Unification
In [5]: from unify_sympy import unify
In [6]: unify(x+y+z, p+q, {})
Out[6]: <generator object unify at 0x54b8640>
In [7]: list(_)
Out[7]: [{p: y, q: x + z}, {p: y + z, q: x}]
Note that this doesn't yet handle commutativity. For example the case {p:
x+y, q: z} is not represented. The ordering in this example is made
slightly more confusing because Add is rearranging the args (x, y, z).
The commutativity problem can be solved if this stackoverflow problem can
be solved
http://stackoverflow.com/questions/13131491/partition-n-items-into-k-bins-in-python-lazily
On Fri, Oct 26, 2012 at 1:49 PM, Matthew Rocklin <[email protected]> wrote:
> I've asked this question on StackOverflow. It has a clear example of what
> I want.
>
>
> http://stackoverflow.com/questions/13092092/algorithms-for-unification-of-list-based-trees
>
> Can anyone here point us to standard solutions to this problem?
>
>
> On Fri, Oct 26, 2012 at 4:13 AM, Sergiu Ivanov
> <[email protected]>wrote:
>
>> On Thu, Oct 25, 2012 at 07:02:29PM -0700, Matthew Rocklin wrote:
>> >
>> > Regarding combinatorial explosion yes, that's an issue. There are a few
>> > ways to get past this, the first is to do this whole experiment with
>> lazy
>> > generators. Get one match quickly, ask for another if you don't like
>> it, if
>> > you want all of them you have that option. I believe that Prolog works
>> this
>> > way. You might also be able to do some sort of guided search. Ideally we
>> > find a way to separate the search mechanism from the matching.
>>
>> I'm fully supportive of applying the lazy approach by means of
>> generators. In my GSoC-2012 work I relied on generators a great deal
>> and I haven't yet had an occasion to regret this.
>>
>> Sergiu
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "sympy" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/sympy?hl=en.
>>
>>
>
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sympy?hl=en.
