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

Who is that grouch? -or- Fun with functions!

 [1/16] from: joel::neely::fedex::com at: 4-Oct-2000 22:35


I fear that anyone reading my last few posts may conclude that I'm a real grouch. (Of course, it's not necessary to read my emails to draw that conclusion! ;-) In the interest of Suitable Doses of Levity, let's have fun with functions in REBOL! First, let's define an oldie from APL:
>> iota: function [n [integer!]] [r i] [
[ r: copy [] [ i: 0 [ while [i < n] [append r i: i + 1] [ r [ ]
>> iota 20
== [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]
>> iota 100
== [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 4... ...so that iota n returns a block containing the first n positive integers. Now let's do another oldie, this time from Lisp and Perl:
>> map: function [[catch] b [block!] f [function!] /all] [r v] [
[ r: copy [] [ foreach c b [ [ if any [found? v: do [f c] all] [append/only r v] [ ] [ r [ ] ...so that map some-block some-single-arg-function returns a block containing the results of applying the function to each element of the argument block. (Results of none are suppressed unless the /all refinement is supplied with the call.) Thus we have...
>> map iota 20 func [n] [n + n - 1]
== [1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39] ...the first twenty odd positive integers. Now let's get creative, and define:
>> nondiv: func [d] [func [n] [either n // d = 0 [none] [n]]]
...so that nondiv n returns a function that transforms anything divisible by n to none and leaves all other values alone. (Yes, I know I forgot the type specs... It's close to bedtime!) With this new toy, we can compute:
>> map iota 20 nondiv 3
== [1 2 4 5 7 8 10 11 13 14 16 17 19 20] ...all integers between 1 and 20 that aren't divisible by 3. By:
>> map/all iota 20 nondiv 3
== [1 2 none 4 5 none 7 8 none 10 11 none 13 14 none 16 17 none 19 20] ...we see that the /all refinement is doing its job. STOP! Have you guessed where this is heading yet? An all-around trivial-but-handy numeric function is:
>> square: func [n [number!]] [n * n]
...which does Just What You Think It Does. With all of these nice toys in hand, we are now in a position to define:
>> plist: function [n [integer!]] [p c d] [
[ p: copy [] [ c: next iota n [ while [0 < length? c] [ [ append p d: first c [ c: map c nondiv d [ ] [ p [ ] ...so that we can say things like:
>> plist 50
== [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47] In case you were wondering why we defined square (other than to drop another subtle hint...), it was so that we could do the obvious optimization, with an even more obvious name:
>> primes: function [n [integer!]] [p c d] [
[ p: copy [] [ c: next iota n [ while [all [0 < length? c (square d: first c) <= last c]] [ [ append p d [ c: map c nondiv d [ ] [ append p c [ ]
>> primes 50
== [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47]
>> primes 65
== [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61] and
>> print primes 1000
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 3 67 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 46 1 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 7 87 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 88 7 907 911 919 929 937 941 947 953 967 971 977 983 991 997 Enjoy playing with maps! -jn-

 [2/16] from: allen:rebolforces at: 5-Oct-2000 15:54


----- Original Message ----- From: <[joel--neely--fedex--com]> To: <[list--rebol--com]> Sent: Thursday, October 05, 2000 1:35 PM Subject: [REBOL] Who is that grouch? -or- Fun with functions!
> I fear that anyone reading my last few posts may conclude that I'm > a real grouch. (Of course, it's not necessary to read my emails to
<<quoted lines omitted: 8>>
> [ r > [ ]
Hi Grouchy ;) iota: function [n [integer!]][r i][ r: copy [] repeat i n [append r i] ] Using the 'repeat native is quicker. (by about 1 sec per 1000 iterations on my machine). Thanks for the fun.. Allen K

 [3/16] from: joel:neely:fedex at: 5-Oct-2000 8:56


Hi, Allen, Thanks for the help! (Any suggestions for speeding up map?) [allen--rebolforces--com] wrote:
> > > > >> iota: function [n [integer!]] [r i] [
<<quoted lines omitted: 9>>
> Using the 'repeat native is quicker. (by about 1 sec per 1000 > iterations on my machine).
Motivated by your comment, I ran a quick benchmark test:
>> bloop/run 50000
repeat: 8 1 loop: 25 3.125 while: 26 3.25 for: 30 3.75 where the second column is raw times (on a slow box) and the third column is times relative to the repeat version. I'd guess that the performance hit for loop and while is in the high-level handling of the counter; a quick look at the source for for explains its 4th place showing -- he's a busy little beaver! -jn- PS: The QAD benchmark code is below, if anyone's interested: REBOL [] bloop: make object! [ t0: t1: t2: t3: t4: now/time dsec: func [b [time!] e [time!]] [ e: e - b e/hour * 60 + e/minute * 60 + e/second ] run: func [n [integer!] /local b i] [ t0: now/time b: copy [] repeat i n [append b i: i + 1] t1: now/time b: copy [] i: 0 loop n [append b i: i + 1] t2: now/time b: copy [] i: 0 while [i < n] [append b i: i + 1] t3: now/time b: copy [] for i 1 n 1 [append b i] t4: now/time print [ "repeat: " t0: dsec t0 t1 tab t0 / t0 newline " loop: " t1: dsec t1 t2 tab t1 / t0 newline " while: " t2: dsec t2 t3 tab t2 / t0 newline " for: " t3: dsec t3 t4 tab t3 / t0 ] ] ]

 [4/16] from: joel:neely:fedex at: 5-Oct-2000 12:00


Thanks to Allen (again!) for making me think... -jn- [joel--neely--fedex--com] wrote:
> [allen--rebolforces--com] wrote: > >
<<quoted lines omitted: 9>>
> where the second column is raw times (on a slow box) and the > third column is times relative to the repeat version...
I've rerun the benchmark a few times (on a faster box) with the -- somewhat interesting -- results aggregated into a table... loops --> 50000 100000 200000 repeat: 3 1.00 13 1.00 51 1.00 loop: 12 4.00 50 3.85 200 3.92 while: 14 4.67 53 4.08 203 3.98 for: 14 4.67 53 4.08 207 4.06 ...from which two observations: 1) The relative times appear to stabilize as the elapsed times get long enough to overcome round-off error. 2) This is clearly a non-linear process! Hmmm... Could the fact that we're doing append on a non-pre-allocated block have anything to do with it? Let's see! Changing the little benchmark to preallocate the (known in advance, due to the nature of the result!) necessary number of slots in the result block (code given at the end of this note), gives us the following performance on the same box as above: loops --> 200000 500000 1000000 2000000 repeat: 4 1.00 7 1.00 14 1.00 35 1.00 loop: 6 1.50 15 2.14 32 2.29 66 1.89 while: 7 1.75 18 2.57 35 2.50 74 2.11 for: 12 3.00 29 4.14 60 4.29 135 3.86 Notice that the loop count in this table STARTS where the other one ended! Now I have to figure out how to stand in a circle and kick myself. I should have known better! Duuuhhh... -jn- REBOL [] bloop: make object! [ t0: t1: t2: t3: t4: now/time dsec: func [b [time!] e [time!]] [ e: e - b e/hour * 60 + e/minute * 60 + e/second ] run: func [n [integer!] /local b i] [ t0: now/time b: make block! n repeat i n [append b i: i + 1] t1: now/time b: make block! n i: 0 loop n [append b i: i + 1] t2: now/time b: make block! n i: 0 while [i < n] [append b i: i + 1] t3: now/time b: make block! n for i 1 n 1 [append b i] t4: now/time print [ "repeat: " t0: dsec t0 t1 tab t0 / t0 newline " loop: " t1: dsec t1 t2 tab t1 / t0 newline " while: " t2: dsec t2 t3 tab t2 / t0 newline " for: " t3: dsec t3 t4 tab t3 / t0 ] ] ]

 [5/16] from: joel:neely:fedex at: 5-Oct-2000 12:34


Just to bring this little exercise to closure (groan...), I'm passing on the latest version of the functions in the post that started this thread. Both iota and map have been modified to take advantage of the ideas communicated/inspired by Allen's comments. The whole thing is dramatically faster as a result. OBTW, this thread is not really about prime numbers (even though I've embedded this copy of map in a prime seiving object)! I've found functions such as map highly useful in a variety of tasks in the past, and hope it will be of some use to someone else. It just happens that sieving for primes is a cute way to demo what map does.
>> do %primes.r >> length? foo: primes/sieve 1000
== 168
>> print foo
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 -jn- REBOL [] primes: make object! [ iota: function [n [integer!]] [r i] [ r: make block! n repeat i n [append r i] ] map: function [[catch] b [block!] f [function!] /all] [r v] [ r: make block! length? b foreach c b [ if any [found? v: do [f c] all] [append/only r v] ] r ] nondiv: func [d] [func [n] [either n // d = 0 [none] [n]]] square: func [n [number!]] [n * n] sieve: function [n [integer!]] [p c d] [ p: copy [] c: next iota n while [all [0 < length? c (square d: first c) <= last c]] [ append p d c: map c nondiv d ] append p c ] ]

 [6/16] from: al:bri:xtra at: 5-Oct-2000 12:45


jn wrote:
> nondiv: func [d] [func [n] [either n // d = 0 [none] [n]]]
This could be quicker as: nondiv: func [d] [func [n] [if n // d <> 0 [n]]] as 'if returns 'none when the condition is false. Also, this:
> map: function [[catch] b [block!] f [function!] /all]
is better as: map: function [[catch] b [block!] f [any-function!] /all] so you can use native! functions as well. jn, is there a name for a generic function like: something: function [B [block!] F [any-function!]] [Arg1] [ Arg1: first B B: next B foreach Arg2 B [ Arg1: F Arg1 Arg2 ] Arg1 ] something [1 2 3 4 5] :+
>> something: function [B [block!] F [any-function!]] [Arg1] [
[ Arg1: first B [ B: next B [ foreach Arg2 B [ [ Arg1: F Arg1 Arg2 [ ] [ Arg1 [ ]
>> >> something [1 2 3 4 5] :+
== 15 For a sum function? And if you're Grouchy, who's Sneezy, Happy, Doc,... ? :-) Andrew Martin ICQ: 26227169 http://members.nbci.com/AndrewMartin/

 [7/16] from: joel:neely:fedex at: 5-Oct-2000 16:02


Hi, Andrew, I love peer review! Open source works! [Al--Bri--xtra--co--nz] wrote:
> > nondiv: func [d] [func [n] [either n // d = 0 [none] [n]]] > This could be quicker as:
<<quoted lines omitted: 5>>
> map: function [[catch] b [block!] f [any-function!] /all] > so you can use native! functions as well.
I've changed my copy to reflect these suggestions. Thanks! (I *did* say it was the "latest" version, not the "last" version...)
> jn, is there a name for a generic function like: > >> something: function [B [block!] F [any-function!]] [Arg1] [
<<quoted lines omitted: 8>>
> >> something [1 2 3 4 5] :+ > == 15
Well, APL called it "reduce", but that name is already taken! ;-) The next most common name I can recall for that kind of thing is accumulate , but I'm too lazy to type that all the way out. I suggest one slight change: supplying the initial value of the accumulator lets it function correctly even with an empty block of values. Normally one would use a left identity appropriate for the f in use (e.g., 0 for addition, 1 for multiplication, etc.). With this change in hand, we get: accumulate: func [a [any-type!] b [block!] f [any-function!]] [ foreach c b [a: f a c] a ] which allows us to say
>> accumulate 0 iota 20 :+
== 210 or
>> accumulate 1 iota 10 :*
== 3628800 Since the accumulation function need not be symmetric, we can also say
>> accumulate "" iota 10 :append
== "12345678910" Of course, some functions don't have a left identity (theoretically or practically), so it's up to the user to choose a reasonable stand-in:
>> accumulate 9999999 iota 20 :min
== 1
>> accumulate -9999999 iota 20 :max
== 20 Incidentally, there's a whole family of such so-called higher-order functions that can be quite interesting. The next one (I can't recall if there's a common name for it) can be used for statistics and other fun things: pair-wise: function [ b1 [block!] b2 [block!] f [any-function!] ][ r ][ r: make block! min length? b1 length? b2 loop min length? b1 length? b2 [ append r f first b1 first b2 b1: next b1 b2: next b2 ] r ] ...such as...
>> my-scores: [4 7 16 2 12 13]
== [4 7 16 2 12 13]
>> your-scores: [9 5 15 1 15 15]
== [9 5 15 1 15 15]
>> winning-scores: pair-wise my-scores your-scores :max
== [9 7 16 2 15 15]
>> losing-scores: pair-wise my-scores your-scores :min
== [4 5 15 1 12 13]
>> spreads: pair-wise winning-scores losing-scores :subtract
== [5 2 1 1 3 2] Then (hold on to your Funk-and-Wagnall's) a function named after the mathematical operation known as "convolution" can be defined as convolve: func [ a [any-type!] b1 [block!] b2 [block!] fa [any-function!] fb [any-function!] ][ accumulate a pair-wise b1 b2 :fb :fa ] ...which can do tricks such as...
>> worst-winning-score: convolve 9999 my-scores your-scores :min :max
== 2
>> best-losing-score: convolve -9999 my-scores your-scores :max :min
== 15
>> season-grand-score: convolve 0 my-scores your-scores :+ :max
== 64 ...as well as the more mathematical...
>> inner-product: convolve 0 my-scores your-scores :+ :*
== 688
> And if you're Grouchy, who's Sneezy, Happy, Doc,... ? :-) >
Well, after all the interesting and useful suggestions from the list, I guess I'm Happy! (Although overlooking the quadratic time complexity of my earlier versions of iota and map made me feel Dopey!) -jn- -- ; Joel Neely [joel--neely--fedex--com] 901-263-4460 38017/HKA/9677 REBOL [] print to-string debase decompress #{ 789C0BCE0BAB4A7176CA48CAB53448740FABF474F3720BCC B6F4F574CFC888342AC949CE74B50500E1710C0C24000000}

 [8/16] from: al:bri:xtra at: 5-Oct-2000 14:42


> The next most common name I can recall for that kind of thing is
accumulate , but I'm too lazy to type that all the way out. How about: "cumulate"? It's shorter! :-) Or what about: "apply", as in applying the function to a block or blocks? As 'pair-wise can be extended to three (or more) arguments functions as well. Andrew Martin Taking notes... ICQ: 26227169 http://members.nbci.com/AndrewMartin/

 [9/16] from: chris:double:tab at: 6-Oct-2000 10:05


> >> something [1 2 3 4 5] :+
== 15
> For a sum function?
Such a function is commonly called 'reduce'. For the Lisp reference of the function see: http://www.xanalys.com/software_tools/reference/HyperSpec/Body/fun_reduce.html Chris. -- http://www.double.co.nz/cl http://www.double.co.nz/dylan

 [10/16] from: al:bri:xtra at: 5-Oct-2000 15:45


Andrew wrote:
> As 'pair-wise can be extended to three (or more) arguments functions as
well. Much like this:
>> Apply: function [Blocks [block!] F [any-function!]] [Results F-Block] [
[ Results: none [ if equal? length? Blocks length? first :F [ [ Results: make block! length? first blocks [ repeat i length? first Blocks [ [ F-Block: copy [] [ append F-Block :F [ foreach Block Blocks [ [ append/only F-Block Block/:i [ ] [ append/only Results do F-Block [ ] [ ] [ Results [ ]
>> apply [[1.0 3.3]] :form
== ["1" "3.3"]
>> apply [[1.0 3.3] [2.3 99.0]] :+
== [3.3 102.3]
>> apply [[true false true] [["I'm true!"] ["not not"] [1]] [["I'm true!"]
["not"] [0]]] :either == ["I'm true!" "not" 1] Andrew Martin ICQ: 26227169 http://members.nbci.com/AndrewMartin/

 [11/16] from: allen:rebolforces at: 6-Oct-2000 9:19


Happy, Grouchy, and Dopey ;-) I don't think this has been mentioned in this thread yet. Ladislav created a number of the high level functions. Not sure how they stack up in light of the recent benchmarks. But they are worth a look. A set of higher order functions: Accum, Apply, Curry, Composition, Enum, Filter, Map, Mapper, Nargs, Refined http://www.rebol.org/advanced/highfun.r Cheers, Allen K Lazy.. --Snow White Carl, and REBOL dwarves, playing to peer review in a suburb near you!--

 [12/16] from: lmecir:geocities at: 6-Oct-2000 9:51


Hi, I am prepared to incorporate enhancements you suggest to http://www.rebol.org/advanced/highfun.r Cheers Ladislav BTW, an RT (Referentially Transparent) version of: object/function/refinement1/.../refinementN arg1 ...argN call can be written (using Refined from above URL) as follows: do refined get in object 'function reduce [ 'refinement1 ...'refinementN ] arg1 ...argN (ugly), or, more efficiently (using RT function defined below): rt: function [block [block!]] [blk] [ do head change/only copy block to path! reduce first block ] as: rt [['object 'function 'refinement1 ... 'refinementN] arg1 ... argN] (MUCH more sexy).

 [13/16] from: joel:neely:fedex at: 6-Oct-2000 6:57


Hello, [lmecir--geocities--com] wrote:
> Hi, > > I am prepared to incorporate enhancements you suggest to > http://www.rebol.org/advanced/highfun.r >
Thanks, to you for providing that library and to Allen for pointing out its existence! I haven't had a chance yet, but I'm looking forward to studying them.
> Cheers > Ladislav
<<quoted lines omitted: 11>>
> rt [['object 'function 'refinement1 ... 'refinementN] arg1 ... argN] > (MUCH more sexy).
I may have some questions after I play with this...
> > I don't think this has been mentioned in this thread yet. > > Ladislav created a number of the high level functions. Not sure how they
<<quoted lines omitted: 5>>
> > http://www.rebol.org/advanced/highfun.r > >
Well, actually, I do have one question (esp. to Ladislav and/or Allen) regarding style. I've noticed both of you using capital letters (e.g., in the list of HOFs above), but haven't figured out the convention by which one decides what is capitalized. Just curious... -jn-

 [14/16] from: lmecir:geocities at: 6-Oct-2000 14:54


Hi Joel,
> > > A set of higher order functions: > > > Accum, Apply, Curry, Composition, Enum, Filter, Map, Mapper, Nargs,
<<quoted lines omitted: 8>>
> Just curious... > -jn-
that is my "convention", that nobody else uses AFAIK, Allen just (as that lazy... suggests) copied a part of the file IMHO. I do it when speaking about Rebol values to distinguish them and the normal text. Example: a: either b= 1[5] [6] When refering to the code above I am trying to (as consistently as possible) use A as a name for the Rebol integer value stored in the Rebol word 'A (whether it is 5 or 6) as opposed to 'A, which denotes the Rebol word as such. That is why I speak about Refined (Rebol function) and 'Refined (Rebol word). My "convention" differs dramatically from Elan's, (maybe others use that too), because what I call A he usually denotes 'a and what I call 'A he usually denotes a (or A). I think, that from the above description is clear, that either mine, or his "convention" looks as being "inside out" or "upside down". When I wrote a HTML version of my http://www.geocities.com/lmecir.geo/contexts.html, I used a different convention : I simply used a different font (Courier) for the same purpose instead of initial capital letters, which may be even more readable (I hope). Cheers Ladislav

 [15/16] from: allen:rebolforces at: 6-Oct-2000 23:32


----- Original Message ----- From: <[lmecir--geocities--com]> To: <[list--rebol--com]> Sent: Friday, October 06, 2000 10:54 PM Subject: [REBOL] Who is that grouch? -or- Fun with functions! Re:(12)
> Hi Joel, > > > > A set of higher order functions:
<<quoted lines omitted: 14>>
> that is my "convention", that nobody else uses AFAIK, Allen just (as that > lazy... suggests) copied a part of the file IMHO.
Yes as Ladislav guessed, I copied the description of the functions from the script header. So that is his convention that you see there. I'm just avoiding "Chinese Whispers" Normally I use the 'tick to indicate a REBOL word / function, but I notice that HELP and feedback use full capitalisation instead. Maybe we should adopt that? Cheers, Allen K

 [16/16] from: joel:neely:fedex at: 6-Oct-2000 10:24


Yes, Allen (and Ladislav)... [allen--rebolforces--com] wrote:
> Normally I use the 'tick to indicate a REBOL word / function, but I notice > that HELP and feedback use full capitalisation instead. Maybe we should > adopt that? >
...I think we're all struggling to overcome the typographic limitations of plain text email (and, please, nobody offer html-ized email as the answer!) to clarify our REBOL fragments, snippets, and quotations. I'll be quite happy to try to abide by a common convention in the interest of readability. Do you think that the HELP convention, as in:
>> help append
USAGE: APPEND series value /only DESCRIPTION: Appends a value to the tail of a series and returns the series head. APPEND is a function value. ARGUMENTS: series -- (Type: series port) value -- (Type: any) REFINEMENTS: /only -- Appends a block value as a block is sufficient, or do we need a bit more decoration? E.g., in the USAGE: section, APPEND indicates the name, but in the DESCRIPTION section APPEND clearly is describing the (standard global) value bound to that name. In addition, in the REFINEMENTS: section, "/only" is uncaptialized. Of course, I dislike red tape as much as the next person! Maybe we could start with a minimum of convention, and only add features as needed for clarification? -jn- -- ; Joel Neely [joel--neely--fedex--com] 901-263-4460 38017/HKA/9677 REBOL [] print to-string debase decompress #{ 789C0BCE0BAB4A7176CA48CAB53448740FABF474F3720BCC B6F4F574CFC888342AC949CE74B50500E1710C0C24000000}

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted