Courses/CS 460/Fall 2005/Homework/Kelly Breed/Oct 8

From CSWiki

My main homework page

Contents 1 HW 2 1.1 Non-recursive merge 1.2 List Reverse 1.3 List Member 1.4 List Drop 1.5 List Map 1.6 List Partition

[edit] HW 2

[edit] Non-recursive merge

% Non-recursive merge sort.  Non-recursive?
local  L = [e f c b d a]
   
   proc {SortList L O}
      S in
      S = {Singles L}
      O = {MSort S}
   end
	 
   proc {MSort ListIn ?ListOut}
      case ListIn of
	 A|B|T then ListOut = {MSort {MergeLists A B}|T}
      []A|B then ListOut = {MergeLists A B}
      [] A then ListOut = A
	 end
   end

   fun {Singles I}
      local L in
	 case I of
	    H|T then
	    L = [H]|{Singles T}
	 else nil end
      end
   end

   proc {MergeLists A B ?Out}
      case A#B of
	 (H1|T1)#(H2|T2) then
	 if H1 < H2 then Out = H1|{MergeLists T1 B} else Out = H2|{MergeLists A T2} end
      [] nil#_ then Out = B 
      [] _#nil then Out = A
      else skip
      end
   end
   
in
   {Browse {SortList L}}
end

[edit] List Reverse

Still working on figuring out how to get rid of passing nil into the proc.

% implementation of list.reverse

local L = [1 2 3 4 5 6 7 8 9]
   proc {Reverse L R Out}
      local S in
      case L of
	 H|T then S=H|R
	 {Reverse T S Out}
      else R=Out end
      end
   end

 
in
   {Browse {Reverse L nil}}
end

[edit] List Member

% implementation of List.member

local L = [a b c d e f g]

   fun {Member L M}
      local S in
	 case L of
	    H|T then S=H
	    if S==M then true else {Member T M} end
	 else false end
      end
   end

in
   {Browse {Member L c}}
   {Browse {Member L h}}
end

[edit] List Drop

% implementation of List.drop

local L = [1 2 3 4 5 6 7 8 9]
   proc {Drop L I ?Out}
      local S in
	 case L of
	 H|T then S = T
	 if I > 0 then {Drop S I-1 Out} else Out=L end
      else skip
      end
      end
   end

in
   {Browse {Drop L 3}}
   {Browse {Drop L 10}}
end

[edit] List Map

Presented in class Oct. 8.

% implementation of List.map

local
   fun {Map Xs P}
      case Xs of
	 H|T then {P H}|{Map T P}
	 else nil end
   end
in
   {Browse {Map [1 2 3 4] IntToFloat}}
end

[edit] List Partition

% implementation of List.partition.  Sort of.
local O E
   proc {Partition Xs P ?Ys ?Zs}
      {Partition2 Xs P nil nil Ys Zs}
   end
   
   proc {Partition2 Xs P L R ?Ys ?Zs}
      local A B  in
      case Xs of
	 H|T then A=H B=T
	 if {P A}==true then {Partition2 B P A|L R Ys Zs}
	 else  {Partition2 B P L A|R Ys Zs} end
      else
	 L=Ys
	 R=Zs
      end
      end
   end

in
      {Partition [1 2 3 4 5 6] IsOdd O E}
      {Browse O}
      {Browse E}
end

My user page.