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