CITE THIS NOTEBOOK: Functional iteration for Divide-and-Conquer algorithms by Ian Ford. Wolfram Community FEB 1 2023.
ExpressionTransform is a new function in the Wolfram Function Repository that provides functional iteration for divide-and-conquer tree algorithms.
We build up five subcases: natural numbers, lists, non-empty lists, expressions, and trees.
We build up five subcases: natural numbers, lists, non-empty lists, expressions, and trees.
Numbers
Numbers
◼
Natural numbers are the results of iteratively applying a successor operator to numbers (starting with zero):
◼
number::=zero|successor(number)
Ascending
Ascending
◼
Folding a natural number iteratively applies an arbitrary successor operator, starting with an arbitrary expression:
In[]:=
numberFold[g_,x_][0]:=xnumberFold[g_,x_][n_]:=Construct[g,numberFold[g,x][n-1]]
In[]:=
numberFold[n|->n+1,0][4]
Out[]=
4
In[]:=
numberFold[g,x][4]
Out[]=
g[g[g[g[x]]]]
◼
In[]:=
Nest[g,x,4]
Out[]=
g[g[g[g[x]]]]
Descending
Descending
◼
Natural numbers are the results of iteratively applying a successor operator to numbers, starting with zero:
In[]:=
nestNumber[f_,test_][expr_]:=If[test[expr],nestNumber[f,test][f[expr]]+1,0]
In[]:=
nestNumber[n|->n-1,GreaterThan[0]][4]
Out[]=
4
In[]:=
nestNumber[Log,GreaterThan[1]][E^E^E^E]
Out[]=
4
◼
An example is iterated log:
In[]:=
ResourceFunction["IteratedLog"][E^E^E^E]
Out[]=
4
Descending and Ascending
Descending and Ascending
◼
Divide-and-conquer natural number transformations iteratively apply an arbitrary successor operator, starting with an arbitrary expression:
In[]:=
numberTransform[f_,g_,x_,test_][expr_]:=If[test[expr],Construct[g,numberTransform[f,g,x,test][f[expr]]],x]
In[]:=
numberTransform[n|->n-1,n|->n+1,0,GreaterThan[0]][4]
Out[]=
4
In[]:=
numberTransform[Log,g,x,GreaterThan[1]][E^E^E^E]
Out[]=
g[g[g[g[x]]]]
Lists
Lists
◼
Lists are the results of iteratively applying an append operator to lists (starting with the empty list) and elements (expressions):
◼
list::=empty|append(list,expr)
Ascending
Ascending
◼
Folding a list iteratively applies an arbitrary append operator, starting with an arbitrary expression:
In[]:=
listFold[g_,x_][{}]:=xlistFold[g_,x_][{most___,last_}]:=Construct[g,listFold[g,x][{most}],last]
In[]:=
listFold[{list,expr}|->Append[list,expr],{}][{1,2,3,4}]
Out[]=
{1,2,3,4}
In[]:=
listFold[g,x][{1,2,3,4}]
Out[]=
g[g[g[g[x,1],2],3],4]
◼
In[]:=
Fold[g,x,{1,2,3,4}]
Out[]=
g[g[g[g[x,1],2],3],4]
Descending
Descending
◼
Lists are the results of iteratively applying an append operator to lists, starting with the empty list:
In[]:=
nestList[f_,test_,h_][expr_]:=If[test[expr],Append[nestList[f,test,h][f[expr]],h[expr]],{}]
In[]:=
nestList[Most,Not@*MatchQ[{}],Last][{1,2,3,4}]
Out[]=
{1,2,3,4}
In[]:=
nestList[Log,GreaterThan[1],h][E^E^E^E]
Out[]=
h[],h[],h,h
◼
In[]:=
NestWhileList[Log,E^E^E^E,GreaterThan[1]]
Out[]=
,,,,1
Descending and Ascending
Descending and Ascending
◼
Divide-and-conquer list transformations iteratively apply an arbitrary append operator, starting with an arbitrary expression:
In[]:=
listTransform[f_,g_,x_,test_,h_][expr_]:=If[test[expr],Construct[g,listTransform[f,g,x,test,h][f[expr]],h[expr]],x]
In[]:=
listTransform[Most,{list,expr}|->Append[list,expr],{},Not@*MatchQ[{}],Last][{1,2,3,4}]
Out[]=
{1,2,3,4}
In[]:=
listTransform[Log,g,x,GreaterThan[1],h][E^E^E^E]
Out[]=
ggg[g[x,h[]],h[]],h,h
◼
In[]:=
NestWhileList[Log,E^E^E^E,GreaterThan[1]]
Out[]=
,,,,1
◼
Use a prepend, rather than an append, operator:
In[]:=
listTransform[Log,{list,expr}|->Prepend[list,expr],{},GreaterThan[1],h][E^E^E^E]
Out[]=
h,h,h[],h[]
Non-Empty Lists
Non-Empty Lists
◼
Non-empty lists are the results of iteratively applying an append operator to non-empty lists (starting with a singleton list) and elements (expressions):
◼
listn::=leaf(expr)|append(listn,expr)
Ascending
Ascending
◼
Folding a non-empty list iteratively applies an arbitrary append operator, starting with an arbitrary unary operator for singleton lists:
In[]:=
listnFold[g_,gl_][{last_}]:=gl[last]listnFold[g_,gl_][{most__,last_}]:=Construct[g,listnFold[g,gl][{most}],last]
In[]:=
listnFold[{list,expr}|->Append[list,expr],List][{1,2,3,4}]
Out[]=
{1,2,3,4}
In[]:=
listnFold[g,gl][{1,2,3,4}]
Out[]=
g[g[g[gl[1],2],3],4]
◼
The two-argument form of Fold gives the special case where the unary operator for singleton lists is the identity operation:
In[]:=
Fold[g,{1,2,3,4}]
Out[]=
g[g[g[1,2],3],4]
In[]:=
listnFold[g,Identity][{1,2,3,4}]
Out[]=
g[g[g[1,2],3],4]
Descending
Descending
◼
Non-empty lists are the results of iteratively applying an append operator to lists, starting with a singleton list:
In[]:=
nestListn[f_,test_,h_][expr_]:=If[test[expr],Append[nestListn[f,test,h][f[expr]],h[expr]],{h[expr]}]
In[]:=
nestListn[Most,Not@*MatchQ[{_}],Last][{1,2,3,4}]
Out[]=
{1,2,3,4}
In[]:=
nestListn[Log,GreaterThan[1],h][E^E^E^E]
Out[]=
h[1],h[],h[],h,h
◼
NestWhileList gives the special case where the append operator prepends the elements:
Descending and Ascending
Descending and Ascending
◼
Divide-and-conquer non-empty list transformations iteratively apply an arbitrary append operator, starting with an arbitrary unary operator:
◼
NestWhileList gives the special case where the append operator prepends the elements:
Expressions
Expressions
◼
Expressions are the results of iteratively applying a construct operator to non-empty sequences of expressions (starting with atoms):
Ascending
Ascending
◼
Folding an expression iteratively applies an arbitrary construct operator, starting with an arbitrary unary operator for atoms:
◼
Descending
Descending
◼
Expressions are the results of iteratively applying a construct operator to non-empty sequences of expressions, starting with atoms:
◼
Descending and Ascending
Descending and Ascending
◼
Divide-and-conquer expression transformations iteratively apply an arbitrary construct operator, starting with an arbitrary unary operator:
Trees
Trees
◼
Trees are the results of iteratively applying a tree operator to data (expressions) and children (sequences of trees, starting with leaves):
Ascending
Ascending
◼
Folding a tree iteratively applies an arbitrary tree operator, starting with an arbitrary unary operator for leaves:
◼
Descending
Descending
◼
Trees are the results of iteratively applying a tree operator to data expressions and sequences of children, starting with leaves:
◼
Descending and Ascending
Descending and Ascending
◼
Divide-and-conquer tree transformations iteratively apply an arbitrary tree operator, starting with an arbitrary unary operator:
◼
Summary
Summary
◼
Natural number transformations are special cases of list transformations:
◼
List transformations are special cases of non-empty list transformations:
◼
Natural number transformations are also special cases of expression transformations:
◼
Non-empty list and expression transformations are both special cases of tree transformations:
Neat Examples
Neat Examples
Fractals
Fractals
◼
Define functions to compute branches of a fractal:
Sorting Algorithms
Sorting Algorithms
Mergesort
Mergesort
◼
Define a function that divides a list with two or more elements into a left half and a right half:
◼
Define a function that merges two sorted lists giving a sorted list:
◼
Perform a mergesort on a random list:
Quicksort
Quicksort
◼
Define a function that divides a non-empty list into the list of elements less than or equal to a pivot element and the list of elements greater than the pivot element:
◼
Define a function that merges the results of sorting these lists:
◼
Perform a quicksort on a random list:
Further Reading
Further Reading
Natural numbers, lists, non-empty lists, expressions, and trees are all examples of algebraic data types. Each can be defined as an initial object in the category of ℱ-algebras for some endofunctor ℱ called the signature. The associated recursive algorithms that apply descending operators, ascending operators, and both descending and ascending operators are called anamorphisms, catamorphisms, and hylomorphisms, respectively.
Meijer, Fokkinga, and Paterson (1991) gives an introduction to and develops a calculus for computing lazy functional programs and proving laws for these recursion schemes. Gibbons (1991) investigates tree catamorphisms and a related notion of accumulations to derive algorithms including bracket matching, tidy tree drawing, and attribute evaluations for attribute grammars. Gibbons (1995) investigates using initial algebras to model directed acyclic graphs. Bird and de Moor (1997) shows how to calculate programs using a categorical calculus of relations. Bird and Wadler (1988) is an introductory textbook on functional programming covering topics including data types, folds, and divide-and-conquer algorithms.
I give a special thank you to José M. Martín-García for our discussions and his suggestions for the design and documentation of ExpressionTransform.
References
References
Publications
Publications
◼
Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. Erik Meijer, Maarten Fokkinga and Ross Paterson. 1991. https://maartenfokkinga.github.io/utwente/mmf91m.pdf
◼
Algebra for Tree Algorithms. Jeremy Gibbons. 1991. https://www.cs.ox.ac.uk/publications/publication2369-abstract.html
◼
An Initial-Algebra Approach to Directed Acyclic Graphs. Jeremy Gibbons. 1995. https://www.cs.ox.ac.uk/publications/publication2341-abstract.html
◼
Algebra of Programming. Richard Bird and Oege de Moor. 1997. https://www.cs.ox.ac.uk/publications/books/algebra/
◼
Introduction to Functional Programming. Richard Bird and Philip Wadler. 1988. https://www.research.ed.ac.uk/en/publications/an-introduction-to-functional-programming
Wolfram Language Documentation
Wolfram Language Documentation
◼
Functional Iteration. Wolfram Research, Inc. Accessed 2023. https://reference.wolfram.com/language/guide/FunctionalIteration.html
◼
Applying Functions Repeatedly. Wolfram Research. Accessed 2023. https://reference.wolfram.com/language/tutorial/FunctionalOperations.html#23850
◼
Query. Wolfram Research, Inc. Accessed 2023. https://reference.wolfram.com/language/ref/Query.html
◼
Nest. Wolfram Research, Inc. Accessed 2023. https://reference.wolfram.com/language/ref/Nest.html
◼
Fold. Wolfram Research, Inc. Accessed 2023. https://reference.wolfram.com/language/ref/Fold.html
◼
NestWhileList. Wolfram Research, Inc. Accessed 2023. https://reference.wolfram.com/language/ref/NestWhileList.html
◼
MapAll. Wolfram Research, Inc. Accessed 2023. https://reference.wolfram.com/language/ref/MapAll.html
◼
NestGraph. Wolfram Research, Inc. Accessed 2023. https://reference.wolfram.com/language/ref/NestGraph.html
◼
NestTree. Wolfram Research, Inc. Accessed 2023. https://reference.wolfram.com/language/ref/NestTree.html
◼
TreeFold. Wolfram Research, Inc. Accessed 2023. https://reference.wolfram.com/language/ref/TreeFold.html
Wolfram Function Repository
Wolfram Function Repository
◼
The Wolfram Function Repository: Launching an Open Platform for Extending the Wolfram Language. Stephen Wolfram. 2019. https://writings.stephenwolfram.com/2019/06/the-wolfram-function-repository-launching-an-open-platform-for-extending-the-wolfram-language/
◼
ExpressionTransform. Ian Ford, Wolfram Research. 2023. https://resources.wolframcloud.com/FunctionRepository/resources/ExpressionTransform/
◼
IteratedLog. Wolfram|Alpha Math Team. 2021. https://resources.wolframcloud.com/FunctionRepository/resources/IteratedLog/
Wikipedia
Wikipedia