Courses/CS 460/Fall 2005/Homework/Jay Donnell/Oct 8

From CSWiki

Main Homework Page

[edit] Homework 2

Presented in class

% non recursive merge sort

local Length Single Merge MergeSort ListIn ListOut T1 T2 in

   ListIn = [1 3 6 4 2 5]

    proc {Length Xs B?}
        local I in
            case Xs of Head|Tail then
                if Tail == nil then
                    B = 1
                else
                    {Length Tail I}
                    B = 1 + I
                end
             end
	end
    end
	 
    proc {Single In ?Out}
        local L in
	    case In of Head|Tail then
	        if Tail == nil then
		    Out = [[Head]]
		    %{Browse 'end'}
		    %{Browse ListOut}
                else
		    {Single Tail L}
		    %{Browse 'L'}
		    %{Browse L}
  		    Out = [Head]|L
		    %{Browse 'ListOut'}
		    %{Browse ListOut}
	        end
	    end
         end
    end

    proc {Merge A B ?C}
        local Tmp in
	    if A == nil then
	        C = B  
	    elseif B == nil then
	        C = A
	    else
                case A of HA|T1 then
	            case B of HB|T2 then
		        %{Browse HA}
		        %{Browse HB}
		        if HA < HB then
		            {Merge T1 B Tmp}  
	                    C = HA|Tmp
		        else
		            {Merge A T2 Tmp}
	                    C = HB|Tmp
		        end
		        %{Browse 'C'}
			%{Browse C}
		    end
	        end
            end
	end
    end

    %T1 = [1 3 5]
    %T2 = [2 4 6]
    %{Merge T1 T2 ListOut} {Browse ListOut}
    
    proc {MergeSort ListIn ?ListOut}
        local L J S R in
	    {Length ListIn L}
	    %{Browse 'L'}
	    %{Browse L}
	    if L == 1 then
	        ListOut = ListIn
	    else   
	        case ListIn of A|Tmp then
	            case Tmp of B|Tail then
		        {Merge A B J}
		        %{Browse 'J'}
		        %{Browse J}
		        
		        {Append Tail [J] S}
		        {MergeSort S ListOut}
		       
		    end  
		end
	    end
	    %ListOut = L
	end
    end

    %local T2 in {Append [1 2] [[3 3]] T2} {Browse T2} end
    
    {Single ListIn T1}
    {MergeSort T1 ListOut} {Browse ListOut}
    %{Single ListIn ListOut}
    %{Single ListOut T1}
    %{Browse T1}
    {Browse '-------------------------------'}   
end

%{Browse [4]#[5]}

% Member functio
local Member ListIn Out in

    ListIn = [1 2 3]
   
    proc {Member X Ys ?B}
        case Ys of Head|Tail then
	    {Browse 'Head'} {Browse Head}
	    {Browse 'Tail'} {Browse Tail}
	    if Head == nil then
	        B = false
	        {Browse B}
            elseif Head == X then
                B = true
	    else
	        if Tail == nil then
		    B = false
		else   
		    {Member X Tail B}
		end
            end
        end
    end
    
    {Member 5 ListIn Out} {Browse Out}

end

% Length Proc
local Length ListIn Out in
   ListIn = [1 2 3]
   proc {Length Xs B?}
      local I in
         case Xs of Head|Tail then
	    if Tail == nil then
	       B = 1
	    else
	       {Length Tail I}
	       B = 1 + I
	    end
	 end
      end
   end

   {Length ListIn Out} {Browse Out}
end

% Nth Proc
local Nth ListIn Out in
   ListIn = [1 2 3]
   proc {Nth Xs I B?}
      local J in
	 if Xs == nil then
	    B = nil
	 else
   	    case Xs of Head|Tail then
	       if Head == nil then
	          B = nil
	       elseif I == 1 then
	          B = Head
	       else
	          J = I - 1
	          {Nth Tail J B}
	       end
	    end
	 end
      end
   end

   {Nth ListIn 2 Out} {Browse Out}
   %{Nth nil 2 Out} {Browse Out}
end

% Map Proc
local Map ListIn Out Callback in
   ListIn = [1 2 3]
   proc {Map Xs P B?}
      local X Y in
	 if Xs == nil then
	    B = nil
	 else
            case Xs of Head|Tail then
	          {P Head X}
	          {Map Tail P Y}
	          B = X|Y
	    end
	 end
      end
   end

   Callback = proc {$ A C?}
		 C = A + 1
	      end
   
   {Map ListIn Callback Out} {Browse Out}
end

% Filter Proc
local Filter ListIn Out Callback in
   ListIn = [1 2 3 4 5]
   proc {Filter Xs P B?}
      local X Y in
	 if Xs == nil then
	    B = nil
	 else
            case Xs of Head|Tail then
	          {Filter Tail P Y}
	          {P Head X}
	          if X then
		     B = Head|Y
		  else
		     B = Y
		  end
	    end
	 end
      end
   end

   Callback = proc {$ A C?}
		 if A < 4 then
		    C = true
		 else
		    C = false
		 end
	      end
   
   {Filter ListIn Callback Out} {Browse Out}
end