[REBOL] Re: More on expressions
From: joel:neely:fedex at: 2-Feb-2003 8:19
Many thanks to all who've participated in this thread. Anyone who
wants to keep playing, skip reading this email until you've had
your fun!
For those who'd like a hint about another approach,
keep
reading
this
email
below.
.
.
.
.
.
.
.
.
.
.
.
Joel Neely wrote:
> Inspired by the discussions of ANY and ALL, I thought I'd share this
> little puzzle, prefaced with a tad of background.
>
Gabriele took that hint in an interesting way I hadn't thought of.
(Thanks, Gabriele, for the new food for thought!)
Let me give a nudge in the direction I was thinking. We've discussed
how ANY and ALL implicitly provide a way to implement chains of tests.
I intended to reinforce that hint at the end of the email.
> The trick, of course, is to find an expression that eliminates the
> need for any explicit "decision" or "selection" activity.
>
Are there any other words that provide implicit tests?
Stop here if you want to take some time for thought.
For
more
along
this
line,
keep
reading.
Gabriele got "dangerously" close to the strategy I was pondering, with
his alternate suggestion:
> a + b + c - (min a min b c) - max a max b c
>
and rightfully so, since I am the one who specified that the values
would be numeric.
Second nudge: suppose that A, B, and C were not numeric (so we can't
use addition and subtraction).
As
before,
stop
reading
unless
you
want
more
hints
(
which
will
come
faster
as
we
get
closer
to
the
end
).
Think about the relationship between decisions and sorting. What can
can we say is accomplished by each iteration of something like the
classic BubbleSort?
We can "unwrap" BubbleSort for three values into the following
sequence of operations:
1) compare A and B, swapping their values if out of order
2) compare B and C, swapping their values if out of order
3) compare A and B, swapping their values if out of order
(and there are some combinations of values that require all three of
these steps).
We can diagram this using the notion of "sort networks", as presented
by Knuth, in this way:
A ---+-------+--- A'
| |
B ---+---+---+--- B'
|
C -------+------- C'
where the diagram is read left-to-right, with each vertical bar as an
instance of "compare and swap if out of order" using the two values at
either end. At the right-hand-end, A', B', and C' contain the sorted
values from A, B, and C.
This is an ENORMOUS hint, if we think about how to implement the
compare and swap if out of order
without using IF.
One
last
chance
to
play
with
these
hints
on
your
own
before
I
spoil
the
secret.
We could do the "compare and swap if out of order" with MIN and MAX,
as follows:
set [a b] reduce [a min b a max b]
set [b c] reduce [b min c b max c]
set [a b] reduce [a min b a max c]
which provides a literal transcription of the sort network diagram if
read from left to right. However, we didn't ask for the sorted list,
but just the median, so let's skip the SET operations, and just use
the expressions. Substituting the expression for the modified B into
the second line above gives us
set [b c] reduce [(a max b) min c (a max b) max c]
Then we can substitute *that* expression for B (and the one for the
new value of A) into the third line:
set [a b] reduce [
(a min b) min ((a max b) min c)
(a min b) max ((a max b) min c)
]
and then we recall that we only wanted the median, which means we only
wanted the ultimate value for B, giving us our final answer:
(a min b) max ((a max b) min c)
which will work for any datatype (number pair char money date time
tuple series) that MIN and MAX handle.
There's actually a practical (well, at least if you think "philosophy
of programming" is practical ;-) point to this little puzzle.
We programmers are biased to think operationally. It's very easy to
approach a p[roblem by thinking, "If I were solving this, I'd first
do blah, and then do blah-blah, and then if yadda-yadda I'd do ..."
Most experienced programmers could see an expression in a problem
specification such as
a * b + a * c + a * d + ... + a * z
and would almost instinctivly
1) know that it could be written as
a * (b + c + c + ... + z)
because we've been trained to know the properties of * and + as
operators, and how they interact.
2) probably desire to rewrite it as shown above, becase we've been
trained to think about saving compute time.
However, we typically aren't trained to think of other parts of our
language (such as MIN, MAX, or the inspiring ANY, ALL, EITHER, etc.)
in the same way. It makes me wonder how often we miss opportunities
to do simplifications just as valid as the above arithmetic example
because don't think about our operators enough...
Thanks for playing!
-jn-
