Urban Hafner

CTM: Exercises of Chapter 1 (Exercise 6)

Posted by urban Sat, 02 Apr 2005 11:41:00 GMT

The problem

Higher order programming. Section 1.9 explains how to use higher-order programming to calculate variations of Pascal’s triangle. The purpose of this exercise is to explore these variations.

(a) Calculate individual rows using subtraction, multiplication, and other operations. Why does using multiplication give a triangle with all zeros? Try the following kind of multiplication instead:

What does the 10th row look like when calculated with Mul1?

(b) The following loop instruction will calculate and display 10 rows at a time:

Use this loop instruction to make it easier to explore the variations.

My solution

(a) I’ll just list the code here. Most of it is just copied from the book.

declare GenericPascal OpList ShiftLeft ShiftRight in
fun {GenericPascal Op N}
   if N==1 then [1]
   else L in
      L={GenericPascal Op N-1}
      {OpList Op {ShiftLeft L} {ShiftRight L}}
   end
end

fun {OpList Op L1 L2}
   case L1 of H1|T1 then
      case L2 of H2|T2 then
     {Op H1 H2}|{OpList Op T1 T2}
      end
   else nil end
end

fun {ShiftLeft L}
   case L of H|T then
      H|{ShiftLeft T}
   else [0] end
end

fun {ShiftRight L} 0|L end

declare Sub1 Sub2 Mul Mul1 in
fun {Sub1 X Y} X-Y end
fun {Sub2 X Y} Y-X end
fun {Mul  X Y} X*Y end
fun {Mul1 X Y} (X+1)*(Y+1) end

(b) You have to be careful not to use fun here. Internally fun is converted into a proc with an additional return argument. But this is not what we want here, as EasyBrowse doesn’t have a meaningful return value.

declare
proc {EasyBrowse Op}
   for I in 1..10 do {Browse {GenericPascal Op I}} end
end