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

[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