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

From CSWiki

Contents 1 Permute 2 IsPrefix 3 Reverse 4 Last 5 ForAll

[edit] Permute

Demonstrated in class on 10.15.2005

local
   proc {Permute In Out}
      proc {Select Xs X Xr}
	 H T
      in
	 Xs = H | T
	 choice
	    H = X
	    Xr = T
	 [] T2 in
	    Xr = H | T2
	    {Select T X T2}    
	 end
      end  
   in
      choice
	 In = nil
	 Out = nil
      [] Element Rest Perms in
	 Rest = {Select In Element}
	 Perms = {Permute Rest}
	 Out = Element | Perms
      end
   end
in
   {Browse {SearchAll proc {$ Perm} {Permute [a b c d] Perm} end}}
end

[edit] IsPrefix

I think I am starting to get this choice stuff. Rather than return a Boolean as the standard IsPrefix does, I have modified mine so that it returns the remainder of the list instead.

local
   proc {IsPrefix Xs Ys Zs}
      Hx Tx Hy Ty in
      Xs = Hx | Tx
      Ys = Hy | Ty
      choice
	 Tx = nil
	 Hx = Hy
	 Zs = Ty
      []
	 Hx = Hy
	 {IsPrefix Tx Ty Zs}
      end
   end
in
   {Browse {SearchAll proc {$ Res} {IsPrefix [1 2 3] [1 2 3 4 5 6] Res} end}}
   {Browse {SearchAll proc {$ Res} {IsPrefix Res [1 2 3 4 5 6] [4 5 6]} end}}
   {Browse {SearchAll proc {$ Res} {IsPrefix [1 2 3] Res [4 5 6]} end}}
end

[edit] Reverse

Reverses a list. Works both ways. For some reason the call to {Reverse Xs [3 2 1]} takes about double the time as {Reverse [1 2 3] Ys}. Possibly has something to do with my use of Append?

local
   proc {Reverse Xs Ys}
      choice
	 Xs = nil
	 Ys = nil
      []Hx Tx in
	 Xs = Hx | Tx
	 Ys = {Append {Reverse Tx} [Hx]}
      end
   end
in
   {Browse {SearchAll proc{$ Res} {Reverse Res [3 2 1]} end}}
   {Browse {SearchAll proc{$ Res} {Reverse [1 2 3] Res} end}}
end

[edit] Last

Returns last element of a list.

local
   proc {Last Xs X}
      H T in
      Xs = H | T
      choice
	 T = nil
	 X = H
      []
	 {Last T X}
      end
   end
in
   {Browse {SearchAll proc{$ Res} {Last [1 2 3] Res} end}}
   {Browse {SearchAll proc{$ Res} {Last [1] Res} end}}
end

[edit] ForAll

A slightly different version of ForAll. It isnt working and I am pretty close to giving up on this choice stuff out of frustration! Argh! Posting this now in case I don't come back to it later.

local
   proc {ForAll Xs P0 Ys}
      Hx Tx X
   in
      Xs = Hx | Tx
      choice
	 Xs = nil
	 Ys = nil
      [] X in
	 X = {PO Hx}
	 Ys = X | {ForAll Tx P0}
      end
   end
in
   {Browse {SearchAll proc{$ Res} {ForAll [1 2 3] IsEven Res} end}}
end