<div dir="ltr"><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">As someone who comes into contact with Haskell only once a year when I teach an introductory Haskell course, I'm not familiar with whether the following is of any general interest. </font></font></font><div>
<font class="Apple-style-span" color="#003333" face="'trebuchet ms', sans-serif"><br></font></div><div><font size="2"></font><font class="Apple-style-span" color="#003333" face="'trebuchet ms', sans-serif">It struck me that one can decompose recursive functions into their pieces which can then be plugged into a recursion engine. Define a recursion engine as follows.</font></div>
<div><font class="Apple-style-span" color="#003333" face="'trebuchet ms', sans-serif"><br></font></div><div><font class="Apple-style-span" color="#003333" face="'trebuchet ms', sans-serif"><div><font class="Apple-style-span" face="'courier new', monospace">recursionEngine termCond termFn reduceFn mapFn wayAheadFn = </font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> recursiveFn </font></div><div><font class="Apple-style-span" face="'courier new', monospace"> </font><b><font class="Apple-style-span" face="'courier new', monospace">where </font></b><font class="Apple-style-span" face="'courier new', monospace">recursiveFn y</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> | termCond y = termFn y</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> | <b>otherwise </b>= reduceFn (mapFn y) (recursiveFn (wayAheadFn y))</font></div>
<div><br></div><div>Then one can define, for example, factorial as follows.</div><div><br></div><div><font class="Apple-style-span" face="'courier new', monospace">factorial = </font></div><div><font class="Apple-style-span" face="'courier new', monospace"> recursionEngine</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> (==0) -- <b>termCond</b>. Stop when we reach 0</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> (\_ -> 1) -- <b>termFn</b>. At 0, return 1.</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> (*) -- <b>reduceFn</b>. After the recursive call multiply n * factorial (n-1).</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> id -- <b>mapFn</b>. This is what's saved for the reduce function.</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> (+ (-1)) -- <b>wayAheadFn</b>. The recursive call is made on n-1.</font></div></font><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br>
</font></font></font></div><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">What I like about this is that it abstracts out the recursive process and allows one to plug functions into it to achieve what one wants. This is similar in spirit to map, foldr, and similar higher order functions. </font></font></font></div>
<div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif"><br></font></font></font></div><div><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">I'm writing because I like this and wanted to share it. Also, t</font></font></font><font color="#003333"><font size="2"><font face="trebuchet ms,sans-serif">he standard higher order functions are, or course, widely used. My question is whether this has been pushed further to generate widely used libraries of other higher order functions </font></font></font><span class="Apple-style-span" style="font-family: 'trebuchet ms', sans-serif; color: rgb(0, 51, 51); ">and if so whether there is a discussion of them somewhere. In other words, what other algorithmic frameworks have been abstracted in this way? (I wouldn't count, for example, sort and zip since only one function is plugged into their abstract versions; changing that function doesn't significantly change the <i>kind </i>of computation being done.) </span><span class="Apple-style-span" style="font-family: 'trebuchet ms', sans-serif; color: rgb(0, 51, 51); ">Although it's hard to tell, I didn't see anything that looked similar in either the libraries that come with the standard Haskell download or on <a href="http://hackage.haskell.org/packages/archive/pkg-list.html">hackage</a>.</span></div>
<div><span class="Apple-style-span" style="font-family: 'trebuchet ms', sans-serif; color: rgb(0, 51, 51); "><br></span></div><div><span class="Apple-style-span" style="font-family: 'trebuchet ms', sans-serif; color: rgb(0, 51, 51); "><a href="http://cs.calstatela.edu/wiki/index.php/Courses/CS_332F/Recursion_engines">This wiki page</a> is my presentation of this. Besides a recursionEngine it also includes a tailRecursionEngine (for tail recursion, naturally) and an extendedRecursionEngine. The extendedRecursionEngine supports functions that require multiple recursive calls in the body such as mergesort or quicksort.</span></div>
<div><span class="Apple-style-span" style="font-family: 'trebuchet ms', sans-serif; color: rgb(0, 51, 51); "><br></span></div><div><span class="Apple-style-span" style="font-family: 'trebuchet ms', sans-serif; color: rgb(0, 51, 51); ">Thanks.</span></div>
<div><div dir="ltr"><font><font face="'trebuchet ms', sans-serif"><i><font color="#003333"><br>-- Russ Abbott<br><span style="font-style:normal"><i>_____________________________________________</i></span></font></i></font></font><div>
<font><font face="'trebuchet ms', sans-serif"><i><span style="font-style:normal"><font color="#003333"><i></i></font></span><font color="#003333"> Professor, Computer Science<br> California State University, Los Angeles<br>
<br> Google voice: 424-<span style="border-collapse:collapse">235-5752</span> (424-cell-rja)<br> blog: <a href="http://russabbott.blogspot.com/" target="_blank">http://russabbott.blogspot.com/</a><font><br> vita: </font><a href="http://sites.google.com/site/russabbott/" target="_blank">http://sites.google.com/site/russabbott/</a><br>
_____________________________________________</font></i></font><br></font></div></div><br>
</div></div></div>