Dan, you rock. I did read this paper when it appeared on LtU (I was
programming with gambit scheme at the time), but my fuzzy memory didn't
light it up when I thought about iterators for factor. Good job there's
jedi like you guys to keep things on the straight and narrow!
I didn't have much time today, but I wrote an until for integer-indexed
sequences. I don't know the multi-dispatch stuff and didn't have time to
look it up today so haven't made this into generic function yet:
: iuntil-step ( i n quot -- i n quot ? )
[ nip call ] 3keep roll ; inline
: iuntil-next ( i n quot ? -- i' n quot ? )
>r >r >r 1+ r> r> r> ! ( i' n quot ? )
; inline
: iuntil-test ( i n quot ? -- i n quot ?' )
>r >r 2dup >= r> r> ! ( i' n ? quot ? )
swapd or ! ( i n quot ? )
; inline
: iuntil-loop ( i n quot' -- )
iuntil-step
iuntil-next
iuntil-test
[ 3drop ] [ iuntil-loop ] if ; inline
: until ( seq quot -- )
(each) ! ( n quot')
iterate-prep ! (0 n quot')
iuntil-loop ; inline
[ 1 2 3 ]
[ { 1 2 3 } [ f ] until ] unit-test
It's not fully tested or thought through - just trying out the idea. I
guess you'd need a generic collect function to handle map, subset etc..
but haven't really given this any thought.
Thanks!
-Phil
Daniel Ehrenberg wrote:
> I agree; it would be beneficial to have a generic collection iteration
> protocol. But it might be easier to use a traversal operation as the
> basis rather than what you've described here. What I mean is something
> that's like find, but not necessarily with outputs. I wrote about this
> in a very unclear blog post:
> http://useless-factor.blogspot.com/2008/01/until-ultimate-enumerator.html.
> Oleg describes the advantages of this kind of protocol here:
> http://okmij.org/ftp/papers/LL3-collections-enumerators.txt. Think
> about tree traversal: it's much easier to implement find on trees than
> a cursor like the one described below. A generic collection protocol
> could partially unify sequences and assocs (as far as their
> iteration), which would be really interesting and potentially useful.
> Presumably, though, this protocol would only need to be implemented
> once on all integer-indexed sequences. It could be done easily using
> slices. But this is all fairly inefficient, as it means that iteration
> does lots of allocation, and iteration needs to do some redundant
> tests. An iteration function like until doesn't have this advantage.
>
> Are you interested in fleshing out a library for a generic collection
> iteration protocol of either kind? That would be interesting to see.
>
> Dan
>
> On Sun, Mar 23, 2008 at 8:19 AM, Phil Dawes <[EMAIL PROTECTED]> wrote:
>> Hi Slava, Hi Factor list,
>>
>> I'm sure this must have been discussed before, but I was wondering if
>> the sequence combinators would be better served by an underlying
>> iterator protocol in addition to the current random access one. I can
>> see a couple of advantages of this:
>>
>> - sequence combinators could be used with streams
>> - sequence combinators could be used with lazy lists
>> - outsources iteration to sequence classes, affording opportunites for
>> optimization
>>
>> (By the latter I mean that e.g. a fixnum-length container could optimize
>> to fixnum+fast)
>>
>> I had a quick go at an iterator protocol by way of proof-of-concept.
>> (old tuple notation I'm afraid). This protocol is more like python's
>> than STL or java. The 'each' combinator was pretty easy:
>>
>> GENERIC: next ( iterator -- end? )
>> GENERIC: elem ( iterator -- element )
>> GENERIC: iter ( seq -- iterator )
>>
>> USING: math.private ;
>>
>> TUPLE: fixnum-iterator num end ;
>> C: <fixnum-iterator> fixnum-iterator
>>
>> M: fixnum iter ( seq -- iterator ) 0 swap <fixnum-iterator> ;
>> M: fixnum-iterator elem ( iterator -- element ) fixnum-iterator-num ;
>>
>> M: fixnum-iterator next ( iterator -- end? )
>> dup fixnum-iterator-num 1 fixnum+fast
>> dup pick fixnum-iterator-end fixnum<
>> [ swap set-fixnum-iterator-num t ] [ 2drop f ] if ;
>>
>>
>> : each-iter-loop ( iter quot -- )
>> 2dup [ elem ] dip call
>> over next [ each-iter-loop ] [ 2drop ] if ; inline
>>
>> : each-iter ( seq quot -- )
>> [ iter ] dip each-iter-loop ; inline
>>
>>
>> ( scratchpad ) 3 [ . ] each-iter
>> 0
>> 1
>> 2
>>
>> What do you think?
>>
>> Cheers,
>>
>> Phil
>>
>>
>>
>> -------------------------------------------------------------------------
>> This SF.net email is sponsored by: Microsoft
>> Defy all challenges. Microsoft(R) Visual Studio 2008.
>> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
>> _______________________________________________
>> Factor-talk mailing list
>> [email protected]
>> https://lists.sourceforge.net/lists/listinfo/factor-talk
>>
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2008.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> Factor-talk mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/factor-talk
>
-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
Factor-talk mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/factor-talk
