Courses/CS 460/Fall 2005/Homework/Xuong Tsan/Oct 15

From CSWiki

October 15th homework solutions

Contents 1 Homework Page 2 Question 3 Solutions

[edit] Homework Page

Homework page is: | http://cs.calstatela.edu/~wiki/index.php/Courses/CS_460/Fall_2005/Homework/Xuong_Tsan

[edit] Question

Write 5 list procedures or functions (like last week) but use only choice. Don't use case or if-then-else.

Here is a version of Delete/3. It is like IsMember/2 except that it returns in its 3rd parameter position the list that's left after the first parameter is deleted from the second.

   proc {Delete X Xs XRest}
      Head Tail in
      Xs = Head | Tail
      choice
	 Head = X
	 XRest = Tail
      [] NewTail in
	 XRest = Head | NewTail
	 {Delete X Tail NewTail}
      end
   end 

You can think of this also as a select procedure. It selects an element from Xs, which it assigns to X. The XRest become the remaining elements of Xs.

Include Permute/2 as one of the five procedures that you write. The following line should generate all permutations of [a b c d].

  {Browse {SearchAll proc {$ Perm} {Permute [a b c d] Perm} end}}
Hint: Permute is not long. One version of it has the following form. 

  proc {Permute In Out}
     % variable declarations
     in
     choice
        % choice 1 is two statements. 
        % It deals with the case when In is nil.
     [] % choice 2 is three statements 
        % 1. Select an element from In.
        % 2. Permute the remaining elements.
        % 3. Put the selected element at the front of the result.
     end
  end

[edit] Solutions

V.1 Non-Testing

local
   proc {Permute In Out}
      H Tail in
      In = H | Tail
      choice
	 In = nil
	 Out=In
      []
	 In = H|Tail
	 Out={Permute Tail Out}|H
      end
   end
   {Browse {SearchAll proc {$ Perm} {Permute [a b c d] Perm} end}}
end