Pascal triangle example.


declare Pascal AddList ShiftLeft ShiftRight

fun {Pascal N}
   if N==1 then [1]
   else
      {AddList {ShiftLeft {Pascal N-1}} {ShiftRight {Pascal N-1}}}
   end
end

%%%% Shifting left means recursively walking all the way to the end of the list
%%%% and adding a [0] once you reach nil at the end
fun {ShiftLeft L}
   case L of H|T then
      H | {ShiftLeft T}
   else [0] end
end

%%%% Shifting right just adds a 0 at the beginning
fun {ShiftRight L}
   0|L
end

%%%% Adding two lists.
fun {AddList L1 L2}
   case L1 of H1|T1 then
      case L2 of H2|T2 then
	 H1+H2 | {AddList T1 T2}
      end
   else nil end
end

{Browse {Pascal 5}}

%%% Faster Pascal using a local variable declaration to avoid recomputing
%%% the recursive call
declare
fun {FastPascal N}
   if N==1 then [1]
   else L in
      L = {FastPascal N-1} 
      {AddList {ShiftLeft L} {ShiftRight L}}
   end
end

%%%% Compare difference in time:
%%{Browse {Pascal 25}}
%%{Browse {FastPascal 25}}

%%%%%%%% NOTE: some functional languages would optimize this
%%%%%%%% by default since in a purely functional language
%%%%%%%% two calls to the same fucntion with the same parameters
%%%%%%%% always return the same result

%%%%%%% Higher-order programming:
declare GenericPascal CombineList

fun {GenericPascal Combine N}
   if N==1 then [1]
   else L in
      L = {GenericPascal Combine N-1}
      {CombineList Combine {ShiftLeft L} {ShiftRight L}}
   end
end

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

declare
fun {Add X Y} X+Y end

{Browse {GenericPascal Add 20}}
   
declare
fun {Xor X Y} if X==Y then 0 else 1 end end

{Browse {GenericPascal Xor 10}}

CSci 4651 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.