I adapted these functions from exercises in David Wagner's superb book,

The first four are examples of an axiom of primitive and general recursive functions, projection (see Gray, p. 411), but also of

Note the piecewise definitions and use of recursion for Map, Nest, and Fold, which work so elegantly. Before seeing Wagner's solutions I thought these functions must use a procedural-type of iteration and list decomposition.

Here are Map, Nest, and Fold using a "pure" rule-based approach, meaning using only rules and patterns. Wagner notes that it turns out that Map is the most difficult of them to implement this way.

*Power Programming in Mathematica,*now out of print, recommended by*MathGroup*.The first four are examples of an axiom of primitive and general recursive functions, projection (see Gray, p. 411), but also of

*selectors*, functions used in a*data structure*to access data in a controlled way without altering the data itself (see Maeder).**myFirst@head_[first_,last___] := first**

**myLast@head_[most___,last_] := last**

**myMost@{most___, last_} := {most}****myMost@head_[most___,last_] := {most}**

**myRest@head_[first_,rest___] := {rest}****Here is how Apply works:**

**myApply[f_, head_@anything___] := f@anything****myApply[f_, anything_] := f@anything**### Recursive Definitions for Map, Nest, Fold

Note the piecewise definitions and use of recursion for Map, Nest, and Fold, which work so elegantly. Before seeing Wagner's solutions I thought these functions must use a procedural-type of iteration and list decomposition.

**myMap[f_,{a_,b___}]:= Join[{f@a},myMap[f,{b}] ]****myMap[f_,{}]:={} (* base case *)**

**myNest[f_,x_,n_Integer?Positive]:= myNest[f,f@x,n-1]****myNest[f_,x_,0]:= x (* base case *)**

**myFold[f_,x_,{a_,b___}]:= myFold[f,f[x,a],{b}]****myFold[f_,x_,{}]:= x (* base case *)**### Recursive, Rule-Based Definitions for Map, Nest, Fold

Here are Map, Nest, and Fold using a "pure" rule-based approach, meaning using only rules and patterns. Wagner notes that it turns out that Map is the most difficult of them to implement this way.

**Clear[myNest,myFold,myMap];**

**myNest[f_,x_,n_Integer]:= {x,n}//.{{a_,0}:>a,{a_,b_}:>{f@a,b-1}}**

**myFold[f_,x_,s_List]:= {x,s}//.{{a_,{}}:>a,{a_,{b_,c___}}:>{f[a,b],{c}}}**

**myMap[f_,s_List]:= Module[{r},{s,{}}//.{{{},r_}:>r, {{a_,b___},r_}:>{{b},Append[r,f@a]}}]**
## No comments:

## Post a Comment