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

[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