On Sun, 2011-03-06 at 00:25 +0000, Maciej Piechotka wrote:
> I use convention iter[0] for the first value returned from iterator etc.
>
> delegate A FoldFunc<A, G> (G g, owned A a);
> delegate void ForallFunc<G> (G g);
> delegate B MapFunc<G, B> (G g);
> delegate bool FilterFunc<G> (G g);
> delegate B ZipFunc<G, A, B> (G g, A a);
>
> ========= For Iterator<G> =========
> ==== Function that disallow usage of iterator after call
> A fold<A> (FoldFunc<A, G> func, owned A seed);
> Fold. I.e. returns value of
> func(this[n], func(this[n-1], ... func(this[0], seed) ...)
>
> void foreach (ForallFunc<G> func);
> Applies function to each value in iterator. Equivalent to:
> foreach (var g: parentcollection)
> func(g)
>
> Iterator<B> map(MapFunc<G, B> func);
>
> Returns new iterator with values returned by functions. I.e.
> Iterator<B> m = this.map(func);
> m[k] = func(this[k]);
> Lazy in sense that the function is called when the 'child' iterator goes
> to this value.
>
> Iterator<A> scan(FoldFunc<A, G> func, owned A seed)
> Similar in approach to fold except that it returns intermidate values.
> Iterator<A> s = this.scan(func, seed);
> s[0] = seed;
> s[k] = func(this[k-1], s[k-1]);
>
> Iterator<G> filter(FilterFunc<G> pred);
> Filters the iterator. I.e. it returns the iterator which contains (in
> order) values that satisfies predicate in order.
>
> Iterator<B> zip(ZipFunc<G, A, B> func, Iterator<A> iter);
> Iterator<(G,A)> zip(Iterator<A> iter);
> Combines two iterators. Probably the second function is preferable
> (however vala GObject backed does not support tuples so far).
> Truncates the result to shorter one.
>
> == Functions that disallow usage of iterator during some time after call
> Iterator<G> take(int n);
>
> Resulting iterator takes returns first n element from parent iterator.
> After child finish the parent iterator points to last element (i.e. it
> skips n element).
>
> Iterator<G> takeWhile(FilterFunc<G> pred);
>
> Resulting iterator takes as long elements as pred returns true. Similar
> to take
>
> == Potentially also useful functions
> void skip(int n);
>
> Skips n elements. The bi-directional iterators accepts negative
> arguments.
>
> void skipWhile(FilterFunc<G> pred)
>
> Skips elements while predicate is true.
>
> void skipToEnd();
>
> Skips all elements. It may be useful with take/takeWhile.
>
> ========= For BidirIterator<G> =========
> A foldRight<A> (FoldFunc<A, G> func, owned A seed)
>
> Left fold. Mirror image of fold - result is:
> func(this[0], func(this[1], ... func(this[n], seed)...);
>
> Iterator<A> scanRight(FoldFunc<A, G> func, owned A seed)
>
> Mirror image of scan:
> Iterator<A> s = this.scanRight(func, seed)
>
> s[k] = func(s[k+1], seed);
> s[n] = seed;
>
> ========= Utility functions
>
> Iterator<G> Iterator.concat(Iterator<Iterator<G>> iters)
>
> Concatinate the iterators into one stream
>
>
>
> I would appreciate comments about:
> - Is any other functions needed
> - Is any function of above useless.
> - Should any implementation detail differ (say - the value computed in
> MapIterator on get or exit from the value)
>
> I am sorry for any unclear text.
>
> Regards
I'm slowly finishing implementation of those function for
uni-directional iterators. I took liberty of adding 2 functions which I
use internally but I believe they have sufficient utility to be
generally available:
public delegate Lazy<A>? UnfoldFunc<A> ();
public static Iterator<A> unfold<A> (owned UnfoldFunc<A> f)
The simple function creates iterator from calls of the delegate.
public delegate Iterator.Stream StreamFunc<A, G> (Iterator.Stream state,
owned G? input, out Lazy<A>? output);
public enum Iterator.Stream { YIELD, CONTINUE, END }
public virtual Iterator<A> stream<A> (StreamFunc<A, G> f);
This is rather complicated function. It is inspired (read blindly
copied ;) ) by stream fusion
(http://www.cse.unsw.edu.au/~dons/papers/CLS07.html) and generalised
left folds (http://okmij.org/ftp/Streams.html)
The delegate takes 3 arguments:
- state. It is usually the last returned value from delegate except
beginning and end of iteration. At the beginning it is Stream.YIELD and
if function requested next element but it is not present it is
Stream.END
- input. It is valid value iff state is Stream.CONTINUE
- output. It is valid only if result of delegate is Stream.YIELD
It may also return one of 3 results
- Stream.YIELD. It means that the value is ready right now
- Stream.CONTINUE. To produce next element it is needed to consume next
element
- Stream.END. The subiteration have ended
Example of use (I don't expect many people will use it but it is helpful
for defining other operations and may be find useful by others):
- map
stream<A>((state, item, out val) => {
switch (state) {
case Stream.YIELD:
return Stream.CONTINUE;
case Stream.CONTINUE:
val = new Lazy<A>(() => {
return (f ((owned)item));
});
return Stream.YIELD;
case Stream.END:
return Stream.END;
default:
assert_not_reached ();
}
});
- filter
stream<G>((state, item, out val) => {
witch (state) {
case Stream.YIELD:
return Stream.CONTINUE;
case Stream.CONTINUE:
if (!pred (item))
return Stream.CONTINUE;
val = new Lazy<G>.from_value (item);
return Stream.YIELD;
case Stream.END;
return Stream.END;
default:
assert_not_reached ();
});
Regards
Attachment:
signature.asc
Description: This is a digitally signed message part