Mailing List Archive: 49091 messages

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