[REBOL] Re: On ordinal and cardinal numbers...
From: larry:ecotope at: 8-Jul-2001 18:45
Hi Joel
> Nice variation on the theme!
Thanks
> Ah, you sneaky fellow! ;-)
;-))
> Absent tail-recursion elimination, I'd always use the iterative
> version myself (but that's just a personal opinion, and certainly
> not something I'd force on anyone else).
Good point. Actually this recursion is tail recursive, If a function just
calls itself there is no problem with the recursion stack, that only happens
if there is a delayed expression evaluation, which there is not in this case
because the args s and b carry the state. I can illustrate this in more
detail if you are interested. But here is a practical example which shows
that it is not a problem. It also shows we can generally afford to burn
these cycles, REBOL series current index manipulations are quite fast. And I
doubt there are many cases where one is interested in a very large skip on a
small series. Still.. see below.
>> b: make block! 10000
== []
>> repeat j 10000 [append b j]
== [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...
>> t: now/time/precise ring-skip b 10001 now/time/precise - t
== 0:00
>> t: now/time/precise ring-skip2 b 10001 now/time/precise - t
== 0:00:00.06
So the recursion is slightly slower as anticipated. The REBOL internal stack
for delayed operations is about 1500 deep, so the example shows that it is
does not come into play.
> 1) There is a peculiar "singularity" that occurs if the series
> argument is positioned at the tail, but not at the head.
>
> >> b: "abcde" == "abcde"
> >> ring-skip b 5 == "abcde"
> >> c: tail b == ""
> >> ring-skip c 0 == ""
> >> ring-skip c 5 == "e"
> >> ring-skip c -1 == "e"
>
> This could be guarded for at the beginning of either function.
Yes, I knew that and originally had some code to deal with it, but I removed
it and unfortunately forgot to mention in my post "just don't do that". :-(
BTW ring is also not too happy with series at the tail.
>> r: make ring []
>> r/data tail [1 2 3]
** Math Error: Attempt to divide by zero
** Where: skip
** Near: pick _data _pos: _pos -
> 3) The last example you gave
>
> >> ring-skip2 b 344
> == [5]
>
> shows that it's possible to burn lots of cycles with a large
> enough second argument.
True but see above.
> Combining all of these ideas, we could have the following at the
> beginning of either the iterative or recursive version:
>
> if tail? s [s: head s]
> if any [0 = length? s 0 = n: n // length? s] [return s]
>
> after which the function will never make needless "round trips".
I think I would prefer to just return an empty series for both the case of
an actually empty series (i.e., empty? head s returns true) which is already
handled and for the case where the current index is at the tail. This
signals a problem to the user in an unobtrusive way. The n = 0 case only
takes one cycle for the iterative version because LOOP falls through (i.e.,
the code block does not execute).
So I would prefer using just the following as the first line of each of my
functions:
if any [0 = length? s 0 = n: n // length? s] [return s]
Thanks for the suggestions.
Cheers
-Larry