TITLE: Programming Fun: Implementing Pairs Using Sets
AUTHOR: Eugene Wallingford
DATE: April 13, 2022  2:27 PM
DESC: 
-----
BODY:

 Yesterday's session of my course was a quiz preceded by a fun little
 introduction to data abstraction.  As part of that, I use a common
 exercise.  First, I define a simple API for ordered pairs:
 <tt>(<b>make-pair</b> a b)</tt>, <tt>(<b>first</b> p)</tt>, and
 <tt>(<b>second</b> p)</tt>.  Then I ask students to brainstorm all
 the ways that they could implement the API in Racket.

 They usually have no trouble thinking of the data structures they've
 been using all semester.  Pairs, sure.  Lists, yes.  Does Racket have
 a hash type?  Yes.  I remind my students about vectors, which we have
 not used much this semester.  Most of them haven't programmed in a
 language with records yet, so I tell them about structs in C and show
 them Racket's struct type.  This example has the added benefit of
 seeing that Racket generates constructor and accessor functions that
 do the work for us.

 The big payoff, of course, comes when I ask them about using a Racket
 function -- the data type we have used most this semester -- to
 implement a pair.  I demonstrate three possibilities: a selector
 function (which also uses booleans), message passaging (which also
 uses symbols), and pure functions.  Most students look on these
 solutions, especially the one using pure functions, with amazement.
 I could see a couple of them actively puzzling through the code.
 That is one measure of success for the session.

 This year, one student asked if we could use sets to implement a pair.
 Yes, of course, but I had never tried that...  Challenge accepted!

 While the students took their quiz, I set myself a problem.

 The first question is how to represent the pair.
 <tt>(make-pair a b)</tt> could return {a, b}, but with no order we
 can't know which is first and which is second.  My students and I had
 just looked at a selector function, <tt>(if arg a b)</tt>, which can
 distinguish between the first item and the second.  Maybe my
 pair-as-set could know which item is first, and we could figure out
 the second is the other.

 So my next idea was
 <tt>(make-pair a b)</tt> &rarr; <tt>{{a, b}, a}</tt>.
 Now the pair knows both items, as well as which comes first, but I
 have a type problem.  I can't apply set operations to all members
 of the set and will have to test the type of every item I pull
 from the set.  This led me to try
 <tt>(make-pair a b)</tt> &rarr; <tt>{{a}, {a, b}}</tt>.
 What now?

 My first attempt at writing <tt>(first p)</tt> and
 <tt>(second p)</tt> started to blow up into a lot of code.  Our set
 implementation provides a way to iterate over the members of a set
 using accessors named <tt>set-elem</tt> and <tt>set-rest</tt>.  In
 fine imperative fashion, I used them to start whacking out a solution.
 But the growing complexity of the code made clear to me that I was
 programming <em>around</em> sets, but not <em>with</em> sets.

 When teaching functional programming style this semester, I have been
 trying a new tactic.  Whenever we face a problem, I ask the students,
 "What function can help us here?"  I decided to practice what I was
 preaching.

 Given p = <tt>{{a}, {a, b}}</tt>, what function can help me compute
 the first member of the pair, <tt>a</tt>?  Intersection!  I just need
 to retrieve the singleton member of <b>&cap; p</b>:
<pre>
    (first p) = (set-elem (apply set-intersect p))
</pre>

 What function can help me compute the second member of the pair,
 <tt>b</tt>?  This is a bit trickier...  I can use set subtraction,
 <tt>{a, b} - {a}</tt>, but I don't know which element in my set is
 <tt>{a, b}</tt> and which is <tt>{a}</tt>.  Serendipitously, I just
 solved the latter subproblem with intersection.

 Which function can help me compute <tt>{a, b}</tt> from p?  Union!
 Now I have a clear path forward: <b>(&cup; p) &ndash; (&cap; p)</b>:
<pre>
    (second p) = (set-elem
                   (set-minus (apply set-union p)
                              (apply set-intersect p)))
</pre>

 I implemented these three functions, ran the tests I'd been using
 for my other implementations... and they passed.  I'm not a set
 theorist, so I was not prepared to prove my solution correct, but
 the tests going all green gave me confidence in my new implementation.

 Last night, I glanced at the web to see what other programmers had
 done for this problem.  I didn't run across any code, but I did find
<a href="https://math.stackexchange.com/questions/62908/how-can-an-ordered-pair-be-ex">
   a question and answer</a>
 on the mathematics StackExchange that discusses the set theory behind
 the problem.  The answer refers to something called "the Kuratowski
 definition", which resembles my solution.  Actually, I should say
 that my solution resembles this definition, which is an established
 part of set theory.  From the StackExchange page, I learned that
 there are other ways to express a pair as a set, though the
 alternatives look much more complex.  I didn't know the set theory
 but stumbled onto something that works.

 My solution is short and elegant.  Admittedly, I stumbled into it,
 but at least I was using the tools and thinking patterns that I've
 been encouraging my students to use.

 I'll admit that I am a little proud of myself.  Please indulge me!
 Department heads don't get to solve interesting problems like this
 during most of the workday.  Besides, in administration, "elegant"
 and "clever" solutions usually backfire.

 I'm guessing that most of my students will be unimpressed, though
 they can enjoy my pleasure vicariously.  Perhaps the ones who were
 actively puzzling through the pure-function code will appreciate
 this solution, too.  And I hope that all of my students can at
 least see that the tools and skills they are learning will serve
 them well when they run into a problem that looks daunting.
-----