Function Repository Resource:

LeafComplexity

Source Notebook

Compute a sum or other complexity measure over all atoms of an expression

Contributed by: Daniele Gregori

ResourceFunction["LeafComplexity"][expr]

gives the sum of all the numeric indivisible subexpressions in expr.

ResourceFunction["LeafComplexity"][expr, f]

apply a function f to each indivisible subexpression in expr and take the Total.

ResourceFunction["LeafComplexity"][expr, f, g]

apply a function f to each indivisible subexpression in expr and Apply to it recursively another unary or binary function g.

Details and Options

Any Wolfram Language expression can be broken down as a TreeForm. An expression's LeafCount gives its total number of indivisible subexpressions or leaves.

LeafComplexity directly extends LeafCount by weighing each leaf by its absolute numeric value and then taking their sum. If a leaf is non-numeric, it is counted by default as 1. Even if already atoms, expressions with Rational, Complex or Association heads are decomposed into their subparts.

ResourceFunction["LeafComplexity"] also accepts as second argument a custom Function f to be applied to all leaves before taking their Total. Even more generally, a third argument can be specified to recursively Apply to each function-of-the-leaf another unary or binary function g. Setting this to Plus recovers the other definitions UpTo two arguments.

ResourceFunction["LeafComplexity"] accepts the following options:

Heads

True

consider also the subexpression heads as leaves

ResourceFunction["LeafComplexity"] can work as a measure of complexity for algebraic expressions.

An important detail in the definition and design of ResourceFunction["LeafComplexity"] is the following. Since in the most general usage case one may sometimes want to choose as third argument Times instead of the default Plus, then in order to avoid returning identically null results, all ResourceFunction["LeafComplexity"] usage definitions are implemented as recursions starting from initial condition 1 instead of 0. This in practice induces the somewhat akward "correspondence principle" that if all leaves are equal 1 or -1, ResourceFunction["LeafComplexity"][expr]=LeafCount[expr]+1. One may desire to see complete equality with LeafCount in this special case, but a better trade-off seems to maintain the internal consistency and generality of ResourceFunction["LeafComplexity"] itself.

Examples

Basic Examples (2)

Expressions with the same LeafCount may have different total over their leaves:

In[1]:=

Out[1]=

In[2]:=

Out[2]=

Apply a function to each leaf before taking the total:

In[3]:=

Out[3]=

Scope (6)

Take the total over the leaves of a rational expression:

In[4]:=

Out[4]=

Sum over all leaves of an algebraic or complex expression:

In[5]:=

Out[5]=

In[6]:=

Out[6]=

Sum over non-integer leaves:

In[7]:=

Out[7]=

In[8]:=

Out[8]=

Sum over the leaves of any expression:

In[9]:=

Out[9]=

In[10]:=

$ResourceFunction[ "LeafComplexity"][<|a -> {2, 3}, b -> <|{0, 1} -> <|\[Gamma] -> 20, \[Delta] -> 40|>, {-1, -2} -> 50|>|>]$

Out[10]=

Apply an arbitrary function to each leaf:

In[11]:=

Out[11]=

In[12]:=

$ResourceFunction[ "LeafComplexity"][{a[2], a[E], a[4], a[8], a[E^2], a[16]}, If[Mod[#, 2] =!= 0, 0, Log2[#]] &]$

Out[12]=

Apply a custom wrapping function other than Plus to each leaf and function-of-the-leaf:

In[13]:=

Out[13]=

In[14]:=

Out[14]=

In[15]:=

Out[15]=

In[16]:=

Out[16]=

Options (2)

Heads (2)

Through the option Heads set to False, only proper leaf nodes are counted (parent nodes count 0):

In[17]:=

Out[17]=

In[18]:=

Out[18]=

Another example with 4 discarded heads:

In[19]:=

In[20]:=

Out[20]=

In[21]:=

Out[21]=

Check the FullForm:

In[22]:=

Out[22]=

Applications (3)

LeafTotal can be used as option value for ComplexityFunction to Simplify algebraic expressions:

In[23]:=

Out[23]=

In[24]:=

Out[24]=

Another example with Log:

In[25]:=

Out[25]=

In[26]:=

Out[26]=

Select the "simplest" element of a list according to a custom function applied to each leaf:

In[27]:=

Out[27]=

In[28]:=

First@MinimalBy[
list,
ResourceFunction["LeafComplexity"][#, Mean[{DigitSum[#], Length@FactorInteger[#]}] &] &]

Out[28]=

Certain functions like ResourceFunction["AlgebraicRange"] tend to overproduce complex closed forms:

In[29]:=

In[30]:=

Out[30]=

In[31]:=

Out[31]=

In[32]:=

Out[32]=

LeafTotal[expr] allows to select only the simpler ones:

In[33]:=

In[34]:=

Out[34]=

In[35]:=

Out[35]=

The resulting numeric distribution can still be nearly uniform:

In[36]:=

Out[36]=

Properties and Relations (4)

If all numeric leaves of an algebraic expression are equal to 1 or -1, LeafComplexity[expr] has the same value as LeafCount[expr]+1:

In[37]:=

Out[37]=

In[38]:=

Out[38]=

If no 0 appears in the expression, LeafComplexity[expr] is greater than LeafCount[expr]+1:

In[39]:=

Out[39]=

In[40]:=

Out[40]=

If 0s are present in the expression, LeafComplexity[expr] can be less than LeafCount[expr]+1:

In[41]:=

Out[41]=

In[42]:=

Out[42]=

If Infinity appears anywhere in the expression and does evaluate to 0, infinite is also the value of LeafComplexity:

In[43]:=

Out[43]=

In[44]:=

Out[44]=

LeafComplexity[expr] can be also computed in terms of Cases as follows:

In[45]:=

$casesLC[expr_] := 1 + Total[ Abs /@ Flatten@ Map[Cases[# //. {_Symbol?(! NumericQ[#] &) -> 1, c_Complex :> ReIm[c], r_Rational :> NumeratorDenominator[r]}, _?NumericQ, {0, Infinity}, Heads -> True] &, Cases[expr, _?(NumericQ[#] && AtomQ[#] &) | _Symbol?(! NumericQ[#] &), {0, Infinity}, Heads -> True]]]$