Mailing List Archive: 49091 messages

## [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

For those who'd like a hint about another approach,

keep

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

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

As

before,

stop

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-
```