sympy/sympy — pull request #1886 by mrocklin (2013-03-12 19:30:21+00:00)
Title: tree traversals take functional inputs

The traversal functions in sympy.strategies.traverse use `Basic.__new__` to recreate nodes in a SymPy tree. This has two issues:

1. It skips canonicalization required by some classes at construction time
2. It is specific to SymPy

This pull request adds a keyword parameter to these functions that completely parametrizes the inspection and creation of trees. This makes it very easy to use traversals in an Expr friendly way. It also more cleanly separates this module from SymPy and makes it generally applicable to other projects.

I'm mostly interested in the latter point (I'm about to split this off into its own repository) but the fact that this solves the former point about Exprs is also relevant.

```Python
In [2]: from sympy.strategies.traverse import bottom_up, expr_fns, basic_fns
In [4]: add_one = lambda x: x+1

In [5]: add_one_everywhere = bottom_up(add_one, expr_fns)
In [6]: expr = x**2 + y*3
In [7]: add_one_everywhere(expr)
Out[7]:
3
4⋅y + (x + 1) + 7
```

`basic_fns` and `expr_fns` look like the following

```Python
basic_fns = {'op': type,
'new': Basic.__new__,
'leaf': lambda x: not isinstance(x, Basic) or x.is_Atom,
'children': lambda x: x.args}

expr_fns = assoc(basic_fns, 'new', lambda op, *args: op(*args))
```

I welcome better names for `expr/basic_fns`

These functions define how to manipulate terms

new(op, *args) -> make a new term
children(term) -> list of args
op(term) -> type of term (e.g. Add, Mul)
leaf(term) -> boolean if the term is a leaf