Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 SKCombinatorLeftmostOutermostLeafCounts

Source Notebook

Compute successive leaf counts during leftmost-outermost evolution of an SK combinator expression

Contributed by: Wolfram Research

ResourceFunction["SKCombinatorLeftmostOutermostLeafCounts"][cmb, t]

computes leaf counts of successive expressions during leftmost-outermost evolution of cmb over t steps.

Details and Options

The argument cmb should be given as a combinator expression in nested bracket form and the argument t should be an integer.
ResourceFunction["SKCombinatorLeftmostOutermostLeafCounts"] has the option "SKGlyphs":
"SKGlyphs"{CombinatorS,CombinatorK}symbols used to specify S, K combinator transformation rules

Examples

Basic Examples (2) 

Compute leaf counts associated with states of a leftmost-outermost SK combinator evolution:

In[1]:=
ResourceFunction["SKCombinatorLeftmostOutermostLeafCounts"][ CombinatorS[CombinatorK][CombinatorK][ CombinatorK[CombinatorK][CombinatorK]], 3]
Out[1]=

Compare the previous result with the leaf counts found by explicitly generating the combinator evolution:

In[2]:=
ResourceFunction["CombinatorEvolveList"][ CombinatorS[CombinatorK][CombinatorK][ CombinatorK[CombinatorK][CombinatorK]], 3]
Out[2]=
In[3]:=
LeafCount /@ %
Out[3]=

The function does not return leaf counts for time steps after the fixed point of the evolution (at which point the combinator will no longer change):

In[4]:=
ResourceFunction["CombinatorFixedPointList"][ CombinatorS[CombinatorK][CombinatorK][ CombinatorK[CombinatorK][CombinatorK]]]
Out[4]=
In[5]:=
ResourceFunction["SKCombinatorLeftmostOutermostLeafCounts"][ CombinatorS[CombinatorK][CombinatorK][ CombinatorK[CombinatorK][CombinatorK]], 10]
Out[5]=

Scope (1) 

Compare the time efficiency of SKCombinatorLeftmostOutermostLeafCounts to that of taking the leaf counts from the explicit evolution generated by CombinatorEvolveList:

In[6]:=
First[Timing[ LeafCount /@ ResourceFunction["CombinatorEvolveList"][ CombinatorS[CombinatorS][CombinatorS][CombinatorS[CombinatorS]][ CombinatorS][CombinatorS], 200]]]
Out[6]=
In[7]:=
First[Timing[ ResourceFunction["SKCombinatorLeftmostOutermostLeafCounts"][ CombinatorS[CombinatorS][CombinatorS][CombinatorS[CombinatorS]][ CombinatorS][CombinatorS], 200]]]
Out[7]=

Options (1) 

Specify the S and K combinator glyphs used in the argument cmb:

In[8]:=
ResourceFunction["SKCombinatorLeftmostOutermostLeafCounts"][ s[k][k][k[k][k]], 3, "SKGlyphs" -> {s, k}]
Out[8]=

Applications (1) 

Plot the time evolution of a combinator expression by leaf count:

In[9]:=
ListPlot[ResourceFunction["SKCombinatorLeftmostOutermostLeafCounts"][ CombinatorS[CombinatorS][CombinatorS][CombinatorS[CombinatorS]][ CombinatorS][CombinatorS], 200]]
Out[9]=

Version History

  • 1.0.0 – 01 March 2021

Related Resources

License Information