Courses/CS 460/Fall 2005/Homework/Jeff Bailey/Oct 8

From CSWiki

Contents 1 Sort 2 Filter 3 Flatten 4 IsList 5 Member 6 Reverse 7 Some

[edit] Sort

This isnt quite working. The recursive call is failing. Perhaps I am recursing over the wrong list?

local F1 F2
   proc {MakeLists Xs ?Zs}
      case Xs of H|T then
	 Zs = [H]|{MakeLists T}
      else
	 Zs = nil
      end
   end

    proc {MergeLists Xs Ys Zs}
       case Xs#Ys
       of nil#Ys then Zs=Ys
       [] Xs#nil then Zs=Xs
       [] (X|Xr) # (Y|Yr) then 
          if X=<Y then Zr in 
             Zs = X|Zr
             {MergeLists Xr Ys Zr}
          else Zr in 
             Zs = Y|Zr
             {MergeLists Xs Yr Zr}
          end 
       end 
    end

    proc {Sort Xs ?Zs}
       if {Length Xs} == 1 then
	  Zs = Xs.1
       else
	  case Xs of H|nil then
	     Zs = {MergeLists H nil}
	  [] H|T then
	     local T1 T2 in
		T1 = {MergeLists H T.1}|{Sort T.2}
		T2 = {Sort T1}
	     end     
	  else
	     Zs = nil
	  end
       end
    end
in
   F1 = [e f c b d a]
   F2 = {MakeLists F1}
   
   {Browse {Sort F2}}
end

[edit] Filter

Demonstrated in class 10.08.2005

Returns a list that contains the elements from Xs for which the procedure P returns true

The documentation on how Procedure.apply works is almost entirely useless. Major debugging was required to figure out how to get it to work correctly.

local L1 P1
   proc {Filter Xs P ?Ys}
      local L in
	 case Xs of H|T then
	    {Procedure.apply P [H L]}
	    if L == true then
	       Ys = H|{Filter T P}
	    else
	       Ys = {Filter T P}
	    end
	 else
	    Ys = nil
	 end
      end
   end
in
   L1 = [1 2 3 4 5 6]
   P1 = proc {$ N ?R} if N > 3 then R = true else R = false end end

   {Browse {Filter L1 IsOdd}}
   {Browse {Filter L1 IsEven}}
   {Browse {Filter L1 P1}}
end

[edit] Flatten

I wanted to try something interesting so I went with Flatten. It was not nearly as easy as I anticipated.

Known Bugs:

• {Flatten [L4 L1 L3]} creates a new sublist that should not exist. I know why this occurs now, fix not yet implemented.
• Non terminated List. This is fixed by fixing sublist bug.
• Generally difficult to read, which makes debugging a chore.

local L1 L2 L3 L4 L5
   proc {Flatten Xs ?Ys}
      case Xs of H|nil then
	 Ys = {Flatten H}
      [] H|T then
	 Ys = {Flatten H}|{Flatten T}
      else
	 Ys = Xs
      end
   end
in
   L1 = [1]
   L2 = [2 3]
   L3 = [[[4]]]
   L4 = [5 L3 L2]
   L5 = [L4 L3 L2 L1]
      
   {Browse {Flatten L1}}
   {Browse {Flatten L2}}
   {Browse {Flatten L3}}
   {Browse {Flatten L4}}
   {Browse {Flatten L5}}
end

[edit] IsList

Returns true if X is a list.

local L1 L2
   proc {IsList X ?B}
      case X of H|nil then
	 B = true
      [] H|T then
	 B = {IsList T}
      else
	 B = false
      end
   end
in
   L1 = [1 2 3]
   L2 = 4
   {Browse {IsList L1}}
   {Browse {IsList L2}}
end

[edit] Member

Demonstrated in class 10.08.2005

Returns true if Ys contains an element equal to X

local L1
   proc {Member X Ys ?B}
      case Ys of H|T then
	 if X == H then
	    B = true
	 else
	    B = {Member X T}
	 end
      else
	 B = false
      end
   end
in
   L1 = [1 2 3]
   {Browse {Member 2 L1}}
   {Browse {Member 4 L1}}
end

[edit] Reverse

Returns the elements of Xs in reverse order. I had to use the Append list function to guarantee proper list construction.

local L1 
   proc {Reverse Xs ?Ys}
      case Xs of H|T then
	 Ys = {Append {Reverse T} [H]}
      else
	 Ys = Xs 
      end
   end
in
   L1 = [1 2 3 4 5]
   {Browse {Reverse L1}}
end

[edit] Some

Test whether the unary boolean function P yields true when applied to at least one item in X.

local L1 L2 P1
   proc {Some Xs P ?B}
      local L in 
	 case Xs of H|T then
	    {Procedure.apply P [H L]}
	    if L == true then
	       B = true
	    else
	       B = {Some T P}
	    end
	 else
	    B = false
	 end
      end
   end
in
   L1 = [1 3 5]
   L2 = [1 2 3 5]
	   
   {Browse {Some L1 IsEven}}
   {Browse {Some L2 IsEven}}
end