# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Construct and aggregate subexpressions with descending and ascending operators

Contributed by:
Ian Ford (Wolfram Research)

ResourceFunction["ExpressionTransform"][ successively applies | |

ResourceFunction["ExpressionTransform"][ applies | |

ResourceFunction["ExpressionTransform"][ applies | |

ResourceFunction["ExpressionTransform"][ applies the operators | |

ResourceFunction["ExpressionTransform"][ applies the operators |

ResourceFunction["ExpressionTransform"] can perform complex construction, filtering, reorganization, aggregation and transformation of arbitrary expressions.

ResourceFunction["ExpressionTransform"] can be seen as a generalization of Query that allows arbitrary expressions to be constructed and arbitrary operations to be applied at every level.

In ResourceFunction["ExpressionTransform"][*expr*,{*f*_{0},…},{*g*_{0},…,*g*_{-1}},…], the operators *f*_{i} and *g*_{i} are applied at successively deeper levels, but the *f*_{i} are applied while "descending" while the *g*_{i} are applied while "ascending".

A "descending" operator is applied to the expression before subsequent operators are applied at deeper levels. Descending operators can filter the parts of an expression at a given level without changing the structure of deeper levels, or they can be arbitrary operators giving arbitrary structures:

An "ascending" operator is applied to both the original expression and the result after all subsequent operators have been applied to deeper levels. Ascending operators can use values computed from prior applications of descending operators as well as the results of ascending operators from deeper levels:

In ResourceFunction["ExpressionTransform"][*expr*,*f*,*g*,*n*], *n* can be any non-negative machine integer or Infinity.

ResourceFunction["ExpressionTransform"] successively applies a descending operator *f* until the maximum level is reached or *f* returns an expression with no arguments.

In ResourceFunction["ExpressionTransform"][*expr*,*f*,*g*,*n*,*h*], *h*[*expr*] is used as the first argument of *g* rather than *expr*.

ResourceFunction["ExpressionTransform"][*expr*,{*f*_{0},*f*_{1},…},{*g*_{0},*g*_{1},…,*g*_{-1}},*n*,*h*] gives the result of applying *g*_{0} to both *h*[*expr*] and *expr*_{0}[*res*_{1},*res*_{2},…], where *f*_{0}[*expr*] gives *expr*_{0}[*expr*_{1},*expr*_{2},…] and ResourceFunction["ExpressionTransform"][*expr*_{i},{*f*_{1},…},{*g*_{1},…,*g*_{-1}},*n*-1,*h*] gives *res*_{i}.

With the option setting Heads→True, ResourceFunction["ExpressionTransform"] includes heads of expressions and their parts.

ResourceFunction["ExpressionTransform"][*expr*,*f*,{…,*g*_{-1}},*n*,*h*] gives *g*_{-1}[*h*[*expr*]] if *n* is 0 or *f*[*expr*] is atomic.

If *f*[*expr*] gives *s*[*expr*_{1},*expr*_{2},…] where *s* is a symbol that holds its arguments, then the expressions *expr*_{i} are given to the functions *f* and *h* unevaluated in ResourceFunction["ExpressionTransform"][*expr*,*f*,*g*,*n*,*h*].

ResourceFunction["ExpressionTransform"][*expr*,*f*,*g*] is equivalent to ResourceFunction["ExpressionTransform"][*expr*,*f*,*g*,1], which gives *g*[*expr*,*f*[*expr*]].

If *f*[*expr*] gives <|*key*_{1}→*expr*_{1},*key*_{2}→*expr*_{2},…|>, then ResourceFunction["ExpressionTransform"][*expr*,*f*,*g*,*n*] gives *g*[*expr*,<|*key*_{1}→*res*_{1},*key*_{2}→*res*_{2},…|>], where *res*_{i} is the result of ResourceFunction["ExpressionTransform"][*expr*_{i},*f*,*g*,*n*-1].

Nest a descending and an ascending operator twice:

In[1]:= |

Out[1]= |

Apply a descending and an ascending operator at successive levels:

In[2]:= |

Out[2]= |

Apply an ascending operator at the last level:

In[3]:= |

Out[3]= |

Construct and visualize a tree as subscripted data with highlighted leaves, adding frames around inner subtrees:

In[4]:= |

Out[4]= |

Apply descending operators to the values of an association:

In[5]:= |

Out[5]= |

Apply descending operators to the arguments of an arbitrary expression:

In[6]:= |

Out[6]= |

Apply successive operators at successive levels:

In[7]:= |

In[8]:= |

Out[8]= |

In[9]:= |

Out[9]= |

In[10]:= |

Out[10]= |

Apply a descending operator f at level 1 of an array:

In[11]:= |

Out[11]= |

Apply Total afterward as an ascending operator at level 0:

In[12]:= |

Out[12]= |

Apply Total first as a descending operator at level 0 instead:

In[13]:= |

Out[13]= |

Apply a descending operator:

In[14]:= |

Out[14]= |

Apply an ascending operator:

In[15]:= |

Out[15]= |

Apply operators at multiple levels:

In[16]:= |

Out[16]= |

Apply an ascending operator at the last level:

In[17]:= |

Out[17]= |

Apply successive operators at successive levels:

In[18]:= |

Out[18]= |

Apply ascending operators to a property of the expression:

In[19]:= |

Out[19]= |

Atomic expressions:

In[20]:= |

Out[20]= |

Normal expressions:

In[21]:= |

Out[21]= |

In[22]:= |

Out[22]= |

Specify the number of additional levels:

In[23]:= |

Out[23]= |

Repeatedly apply descending operators until no more levels are added:

In[24]:= |

Out[24]= |

Apply operators without evaluating intermediate results:

In[25]:= |

Out[25]= |

Apply subsequent operators to the values of an association:

In[26]:= |

Out[26]= |

Count the number of subtrees at each level of a tree:

In[33]:= |

In[34]:= |

In[35]:= |

Out[35]= |

Create a tree of terms in a linear recurrence:

In[36]:= |

Out[36]= |

NestList gives a list of the results of successive applications of an operator *f* to an expression:

In[37]:= |

Out[37]= |

ExpressionTransform successively applies descending operators *f* to an expression before subsequent operators are applied at deeper levels:

In[38]:= |

Out[38]= |

ExpressionTransform applies subsequent operators to each part of an expression:

In[39]:= |

Out[39]= |

Fold gives the result of successively applying a binary operator *g* to the elements of a list:

In[40]:= |

Out[40]= |

ExpressionTransform successively applies ascending binary operators *g* to an expression and the result after all subsequent operators have been applied at deeper levels:

In[41]:= |

Out[41]= |

ExpressionTransform applies subsequent operators to each part of an expression:

In[42]:= |

Out[42]= |

ExpressionTransform applies subsequent operators to each part of an expression:

In[43]:= |

Out[43]= |

In[44]:= |

Out[44]= |

NestList constructs a list by successively applying an operation *f* to an expression:

In[45]:= |

Out[45]= |

Fold successively applies a binary operation *g* to the elements of a list:

In[46]:= |

Out[46]= |

ExpressionTransform constructs an expression from the top-down by successively applying descending operators *f* and applying ascending binary operators *g* to subexpressions from the bottom-up in a single traversal:

In[47]:= |

Out[47]= |

TreeFold[*g*,NestTree[*f*,Tree[*expr*,None],*n*,*h*]] is generally equivalent to ExpressionTransform[*expr*,*f*,*g*,*n*,*h*]:

In[48]:= |

Out[48]= |

In[49]:= |

Out[49]= |

In[50]:= |

Out[50]= |

MapAll[*g*,*expr*] is generally equivalent to ExpressionTransform[*expr*,{},*g*[#2]&,*g*},Infinity]:

In[51]:= |

Out[51]= |

In[52]:= |

Out[52]= |

In[53]:= |

Out[53]= |

In ExpressionTransform, the ascending operator *g* takes the original expression as an argument for inner levels:

In[54]:= |

Out[54]= |

Apply Total as a descending operator:

In[55]:= |

Out[55]= |

Apply Total as an ascending operator:

In[56]:= |

Out[56]= |

Query applies either a descending operator or an ascending operator at each level:

In[57]:= |

In[58]:= |

Out[58]= |

This can also be done with ExpressionTransform:

In[59]:= |

Out[59]= |

ExpressionTransform applies both a descending and an ascending operator at each level:

In[60]:= |

Out[60]= |

ExpressionTransform[*expr*,*f*,*g*,0] gives *expr*:

In[61]:= |

Out[61]= |

ExpressionTransform[*expr*,*f*,{…,*g*_{-1}},0] applies the operator *g*_{-1} to *expr* instead:

In[62]:= |

Out[62]= |

ExpressionTransform[*expr*,*f*,*g*] gives *expr* if *f*[*expr*] gives an atomic expression:

In[63]:= |

Out[63]= |

ExpressionTransform[*expr*,*f*,{…,*g*_{-1}}] applies the operator *g*_{-1} to *expr* instead:

In[64]:= |

Out[64]= |

ExpressionTransform[*expr*,*f*,*g*] applies the operator *g* if *f*[*expr*] gives a normal expression:

In[65]:= |

Out[65]= |

This is true even if *f*[*expr*] gives an expression with no arguments:

In[66]:= |

Out[66]= |

ExpressionTransform successively applies a descending operator *f* until the maximum level is reached or *f* returns an expression with no arguments:

In[67]:= |

Out[67]= |

ExpressionTransform[*expr*,*f*,*g*,*n*,*h*] gives the result of applying *g* to both *h*[*expr*] and *expr*_{0}[*res*_{1},*res*_{2},…], where *f*[*expr*] gives *expr*_{0}[*expr*_{1},*expr*_{2},…] and ExpressionTransform[*expr*_{i},*f*,*g*,*n*-1,*h*] gives *res*_{i}:

In[68]:= |

In[69]:= |

Out[69]= |

In[70]:= |

Out[70]= |

ExpressionTransform[*expr*,{*f*_{0},*f*_{1},…},{*g*_{0},*g*_{1},…,*g*_{-1}},*n*,*h*] gives the result of applying *g*_{0} to both *h*[*expr*] and *expr*_{0}[*res*_{1},*res*_{2},…], where *f*_{0}[*expr*] gives *expr*_{0}[*expr*_{1},*expr*_{2},…] and ExpressionTransform[*expr*_{i},{*f*_{1},…},{*g*_{1},…,*g*_{-1}},*n*-1,*h*] gives *res*_{i}:

In[71]:= |

Out[71]= |

In[72]:= |

Out[72]= |

ExpressionTransform[*expr*,{*f*},*g*,*n*,*h*] is equivalent to ExpressionTransform[*expr*,*f*,*g*,*n*,*h*]:

In[73]:= |

Out[73]= |

In[74]:= |

Out[74]= |

ExpressionTransform[*expr*,{},*g*,*n*,*h*] is equivalent to ExpressionTransform[Identity,*g*,*n*,*h*]:

In[75]:= |

Out[75]= |

In[76]:= |

Out[76]= |

ExpressionTransform[*expr*,*f*,*g*,*n*,*h*] is equivalent to ExpressionTransform[*expr*,*f*,{*g*,Identity},*n*,*h*]:

In[77]:= |

Out[77]= |

In[78]:= |

Out[78]= |

ExpressionTransform[*expr*,*f*,{*g*},*n*,*h*] is equivalent to ExpressionTransform[*expr*,*f*,{#2&,*g*},*n*,*h*]:

In[79]:= |

Out[79]= |

In[80]:= |

Out[80]= |

ExpressionTransform[*expr*,*f*,{},*n*,*h*] is equivalent to ExpressionTransform[*expr*,*f*,{#2&,Identity},*n*,*h*]:

In[81]:= |

Out[81]= |

In[82]:= |

Out[82]= |

ExpressionTransform[*expr*,{},{},Infinity] is generally equivalent to *expr*:

In[83]:= |

Out[83]= |

Construct the 3^{rd}-step Sierpiński triangle:

In[84]:= |

Out[84]= |

Construct the 3^{rd}-step Cantor set:

In[85]:= |

Out[85]= |

Define functions to compute branches of a fractal:

In[86]:= |

In[87]:= |

In[88]:= |

Construct a graphical image of the lines connecting the constructed points in the 0^{th}- through 7^{th} steps:

In[89]:= |

Out[89]= |

In[90]:= |

Out[90]= |

- Hylomorphism (computer science) - Wikipedia
- Attribute grammar - Wikipedia
- Recursion (computer science) - Wikipedia
- Divide-and-conquer algorithm - Wikipedia

This work is licensed under a Creative Commons Attribution 4.0 International License