GIML: Lesson Eight
Some useful programming techniques
Accumulating parameters
The examples of recursion we have seen so far are tail recursive. An accumulating parameter is another common form of recursive programming.
As with the examples so far we usually have a base case - this returns the accumulating parameter. In the recursive case we perform some function to the accumulating parameter and pass it on. The accumulating parameter "builds up" its value during recursive calls, rather than while the recursion is "unwinding" as in the tail recursive case.
An example is called for.
To sum a list using an accumulating parameter:
<![CDATA[fun suma(nil, acc) = acc
| suma(h::t,acc) = suma(t,h+acc);
]]>To find the sum we must supply the initial value for the accumulating parameter - in this case zero.
<![CDATA[fun sum l = suma(l,0);
]]>Consider the execution of an expression such as sum [2,5,3]
<![CDATA[
sum [2,5,3]= suma(2::5::3::nil, 0)
{h is 2, t is 5::3::nil, acc is 0}
= suma(5::3::nil,2+0)
{h is 5, t is 3::nil, acc is 2}
= suma(3::nil,5+2)
= suma(nil,3+7)
= 10
]]>This technique should normally be shunned as it smacks of "efficiencyism" - the functionally correct programmer should at all times avoid discriminating on the grounds of execution efficiency. The best way to achieve this state of grace is to avoid consideration of execution at all, while it is relatively easy to suspend ones awareness of execution for a normally recursive function it is difficult to maintain the required aloofness when it comes to accumulating parameters, one finds oneself uncomfortably close to the machine oriented thinking of a C programmer.
Mutually recursive functions
These may be defined using "and"...
<![CDATA[fun foo 0 = "toff"
| foo n = bar(n-1)
and bar 0 = "berut"
| bar n = foo(n-1);
]]>Nested definitions
We can define values or functions within other expressions using the "let .. in .. end" structure. Items declared are naturally local.
<![CDATA[fun sort nil = nil : int list
| sort(h::t) = let
fun insert(i,nil) = [i]
| insert(i,h::t) = if i>h then i::h::t else
h::insert(i,t)
in insert(h, sort t) end;
fun rev l = let
fun reva(nil,acc) = acc
| reva(h::t,acc) = reva(t,h::acc)
in reva(l,nil) end;
fun power(x,0) = 1
| power(x,n) = let
fun even n = (n mod 2) = 0
val s = power(x, n div 2)
in if even x then s*s else x*s*s end;
]]>It may be useful to return two values from a function. The following returns both the minimum and the maximum in one "pass"
<![CDATA[fun minmax [x] = (x, x)
| minmax(h::t) = let
val (mn, mx) = minmax t
in (min(h,mn),max(h,mx)) end;
]]>