Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

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