Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 CombinatorEvolveList

Source Notebook

Show evolution of a combinator expression for a certain number of steps based on defined rules and an evaluation scheme

Contributed by: Wolfram Research

ResourceFunction["CombinatorEvolveList"][cmb,t]

shows evolution of the combinator expression cmb using S and K combinator transformation rules and single leftmost-outermost updating order across t steps.

ResourceFunction["CombinatorEvolveList"][cmb,t, scheme]

shows evolution of cmb using S and K combinator transformation rules in matches found by scheme.

ResourceFunction["CombinatorEvolveList"][rules, cmb,t, scheme]

shows evolution cmb using rules in matches found by scheme.

Details and Options

The input cmb must be given as a combinator expression in nested bracket form.
If scheme is specified, direction ("Leftmost", "Rightmost"), depth order ("Outermost", "Innermost") and number of matches (integer number or Infinity) must be specified, in order of their priority as sorting criteria.
The combinator transformations of interest should be given as a list of Rule or RuleDelayed elements in rules.
The number of steps t should be an integer number.
ResourceFunction["CombinatorEvolveList"] has the following options:
"FixedPointFailure"Falsewhether to return Failure when fixed point is reached
"MaxSize"Infinitymaximum leaf count allowed for evolution of cmb
"SKGlyphs"{CombinatorS,CombinatorK}symbols used to specify default transformation rules

Examples

Basic Examples (2) 

Show the evolution of a combinator expression for five steps using the default S and K combinator transformation rules in the single-match leftmost-outermost updating scheme:

In[1]:=
ResourceFunction["CombinatorEvolveList"][ s[x][s[x][y][z]][y[k[x][y][k[x][y]]]], 5, "SKGlyphs" -> {s, k}]
Out[1]=

Show the evolution of a combinator expression for five steps, specifying that only the S combinator rule should be used in an all-match innermost-rightmost updating scheme:

In[2]:=
ResourceFunction[ "CombinatorEvolveList"][{s[x_][y_][z_] :> x[z][y[z]]}, s[x][s[x][y][z]][y[k[x][y][k[x][y]]]], 5, {"Innermost", "Rightmost", Infinity}]
Out[2]=

Possible Issues (2) 

The evolution stops after the "MaxSize" is surpassed:

In[3]:=
LeafCount /@ ResourceFunction["CombinatorEvolveList"][s[s][s][s[s]][s][s], 200, "MaxSize" -> 100, "SKGlyphs" -> {s, k}]
Out[3]=

When "FixedPointFailure" is set to True, an exception is thrown to indicate that the proposed evolution surpasses its fixed point:

In[4]:=
ResourceFunction["CombinatorEvolveList"][ s[x][s[x][y][z]][y[k[x][y][k[x][y]]]], 20, "FixedPointFailure" -> True, "SKGlyphs" -> {s, k}]
Out[4]=

Version History

  • 1.0.3 – 05 December 2020
  • 1.0.2 – 05 December 2020
  • 1.0.1 – 05 December 2020
  • 1.0.0 – 04 December 2020

Related Resources

License Information