[REBOL] Re: On ordinal and cardinal numbers...
From: joel:neely:fedex at: 8-Jul-2001 19:04
Hi, Larry,
Nice variation on the theme!
Larry Palmiter wrote:
> Here is a different approach to circular addressing of a REBOL
> series. The heart of the matter is to be able to skip forward
> or backward by an arbitrary number of steps. Here are two
> functions which serve that purpose...
> Neither of the functions does ANY numeric indexing into the
> original series...
>
Ah, you sneaky fellow! ;-)
> The first function uses iteratation:
>
> ring-skip: func [s [series!] n [integer!]] [
> either positive? n [
> loop n [if tail? s: next s [s: head s]]
> ][
> loop abs n [s: back either head? s [tail s][s]]
> ]
> s
> ]
>
> The second uses recursion:
>
> ring-skip2: func [s [series!] n [integer!]] [
> if n = 0 [return s]
> either positive? n [
> if tail? s: next s [s: head s]
> ring-skip s n - 1
> ][
> s: back either head? s [tail s][s]
> ring-skip s n + 1
> ]
> ]
>
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).
I did have a few observations though...
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.
2) Explicitly handing N = 0 is the bottoming-out case for the
recursive version. For both recursive and iterative strategies
it's also possible to short-cut on a completely empty series,
as that case requires no action. There's no significant savings
unless one or the other of those cases happens sufficiently
often, but it applies to both versions.
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. Without messing up your policy of
no-numeric-indexing ;-) let me mention that there's no need
to step forward or backward multiple times around the series.
NOTE: I'm assuming here that the series is not totally empty!
In your example, the series had a length of 5, so a forward
ring-skip of 344 is exactly the same as forward ring-skip of
only 4. In addition, a forward or reverse ring-skip of any
exact multiple of the series length is the same as no skipping
at all.
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".
Of course, implementing idea (3) *requires* bailing out on empty
series values to avoid dividing by zero.
There may a clever way of rewriting these tests, or perhaps
even a suggestion that they're not needed most of the time, but
I hope that the benefit of speeding up some cases and removing
a few puzzling results are worthy of consideration.
Thanks for the interesting ideas!
-jn-
---------------------------------------------------------------
There are two types of science: physics and stamp collecting!
-- Sir Arthur Eddington
joel-dot-neely-at-fedex-dot-com
