Wolfram Research

Function Repository Resource:

TraversalOrderSelect

Source Notebook

Choose positions of an expression by certain traversal-ordering criteria

Contributed by: Wolfram Research

ResourceFunction["TraversalOrderSelect"][list,scheme]

sorts elements from list according to a specified traversal scheme.

Details and Options

The input list is typically a list of lists. This function was created to generate different evaluation schemes for combinators, and therefore is intended to sort positions at which updates could occur in a combinator expression.
In scheme, both direction ("Leftmost" or "Rightmost") and depth order ("Outermost" or "Innermost") must be specified, in order of their priority as sorting criteria.
The scheme, which is a list, can include an optional third element, specified as an integer number or Infinity, that indicates how many elements from the sorted list should be given.

Examples

Basic Examples (4) 

Sort a list of positions in leftmost outermost order:

In[1]:=
ResourceFunction[
 "TraversalOrderSelect"][{{0}, {0, 0, 0, 1}, {0, 0, 0, 1, 1}, {1, 0}}, {"Leftmost", "Outermost", Infinity}]
Out[1]=

Note that the order of criteria given in the scheme matters for sorting:

In[2]:=
ResourceFunction[
 "TraversalOrderSelect"][{{0}, {0, 0, 0, 1}, {0, 0, 0, 1, 1}, {1, 0}}, {"Outermost", "Leftmost", Infinity}]
Out[2]=

Return only the first position from the list sorted by rightmost innermost order:

In[3]:=
ResourceFunction[
 "TraversalOrderSelect"][{{0}, {0, 0, 0, 1}, {0, 0, 0, 1, 1}, {1, 0}}, {"Rightmost", "Innermost"}]
Out[3]=

Specify that two positions should be taken from the list sorted by innermost rightmost order:

In[4]:=
ResourceFunction[
 "TraversalOrderSelect"][{{0}, {0, 0, 0, 1}, {0, 0, 0, 1, 1}, {1, 0}}, {"Innermost", "Rightmost", 2}]
Out[4]=

Scope (2) 

If the third element of scheme is greater than the length of list, the fully sorted list is given:

In[5]:=
ResourceFunction[
 "TraversalOrderSelect"][{{0}, {0, 0, 0, 1}, {0, 0, 0, 1, 1}, {1, 0}}, {"Leftmost", "Outermost", 5}]
Out[5]=

Select the third position from the leftmost outermost sorting order:

In[6]:=
ResourceFunction[
  "TraversalOrderSelect"][{{0}, {0, 0, 0, 1}, {0, 0, 0, 1, 1}, {1, 0}}, {"Leftmost", "Outermost", Infinity}][[3]]
Out[6]=

Possible Issues (1) 

While this function was created to sort a list of lists, it can handle list elements with any arbitrary Head. In this example, the different heads are lexicographically ordered while the parts remain sorted by direction and depth order:

In[7]:=
ResourceFunction[
 "TraversalOrderSelect"][{f[0, 0, 0, 1, 0], {0, 0, 0, 1}, f[0, 0, 0, 1, 1], {1, 0}}, {"Leftmost", "Outermost", Infinity}]
Out[7]=
In[8]:=
ResourceFunction[
 "TraversalOrderSelect"][{f[0, 0, 0, 1, 0], {0, 0, 0, 1}, f[0, 0, 0, 1, 1], {1, 0}}, {"Rightmost", "Innermost", Infinity}]
Out[8]=

Resource History

Related Resources

License Information