Fully generalizes iteration to the functional
programming model:

http://copute.com/dev/docs/Copute/ref/iteration.html

Solves problems mentioned on the mailing list:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033874.html
https://code.google.com/p/haxe/issues/detail?id=71

In short, deprecate "for( in )".  Here is the logic:

http://www.defmacro.org/ramblings/lisp-in-haskell.html

"...We also use higher order functions (functions
that take other functions in arguments) in order to
evaluate the function's arguments. Take a look at how
we use map - Haskell's function to iterate over a
list. We pass it a function and a list, and map
iterates the list and calls our function on each
member. We could do this with a for statement (or if
we're lucky with a foreach), but we don't have to -
Haskell lets us build abstractions over boilerplate
code we write over and over again without waiting for
the compiler developers to write them for us (of
course map is a standard part of Haskell but if it
weren't we could easily implement it ourselves)..."

Note, the following proposed addition of reset() to the
suggested standard interface for iteration, would still
apply to my proposal above:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033874.html

I improved the proposed code to be more OOP orthogonal:

http://copute.com/dev/docs/Copute/ref/iteration.html
(Ctrl+F for "class Iterator<E>" as starting point)

That now supports reset(), head(), tail() and all dat.
Anyone could implement those classes now in a HaXe
library, no compiler changes need for those classes.

(Humor: "all dat" is sort of like my hometown "Who dat"
French/Cajun)

Also it made me realize that I had to make the class
interface namespace distinct to avoid naming collisions
on inheritance:

http://copute.com/dev/docs/Copute/ref/class.html#Inheritance

(btw, I hope readers understand that class Name( Super ) is
like class Name : extends|implements Super in HaXe)

I was originally thinking that member names from different
interfaces would be considered duplicates, but I realized
perhaps we can improve upon (afaics) Python mixins.

I am asking the HaXe community what they think of
deprecating  "for( in )" and replacing it with at
least my proposed Iterable as standard. Deprecation
would mean can still use it but are discouraged from
using it in new code.

My class Iteration could be optional in an HaXell API.
Clever :) Any way Iteration can be used on an Iterable.
One only needs to inherit their collection from
Iteration for optimization.

fold<V> has to be separately parameterized from the
Iterable collection, because it operates on a value
which may not be the same type as the type E of
elements of the collection.

I think you are implying that HaXe doesn't currently
allow methods to be type parameterized beyond the class
type parameters?  I am proposing to allow this in Copute:

http://copute.com/dev/docs/Copute/ref/class.html
(see Parameterized Types section)

I modified the code of my proposal again:

http://copute.com/dev/docs/Copute/ref/iteration.html
(Ctrl+F for "class Iterator<E>" as starting point)

Added Iterator.index, changed Iteration methods to optionally
pass the Iterator (not the index) to the called function.

Added Iterable.unreverse

Without Iterator.reset and Iterator.previous then there is
no way to back up while inside of a loop, would instead
break out of the loop and start over again, which means
conflating the logic of the outer loop with the inner loop.
So I agree with you on reset(), and add previous() as minimum
needed.

Iterator.current and hasPrevious() are not necessary for a loop.
I am considering removing them from my proposal.  There is
Iterable.reverse for making hasNext() into hasPrevious() since
you only need that test when iterating the loop.
Iterable.index is necessary if for no other reason that
otherwise need hasPrevious() to know if at first iteration.
Without Iterable.index, then the inner loop has to be
conflated with the outer loop to set up a variable to simulate
it.  So I say add Iterable.index to the minimum needed.

Syntactical sugar is desirable when it makes code less
verbose and/or easier-to-understand.  Compare:

var a = [0, 1, 2, 3];
for( elem in a )...
a.each...

Seems to me that my proposal is superior in every aspect,
and this is why I argue to deprecate for( in ). Can you
think of any example where my what is less verbose than
for( in )?  For example, in 3 dimension loop, it is even
more compelling:

var a = [[[],[],[]],[[],[],[]],[[],[],[]]]
for( i in a ) for( j in i ) for( k in j )...
a.each.each.each...

That is very compelling given you get all the generality
for free.

Good HaXe already has Lambda ( http://haxe.org/api/lambda ),
but also need the optional ability to have it in non-static
methods, combined with my function folding proposal
( https://code.google.com/p/haxe/issues/detail?id=71 ),
so a.each is more terse than for( in ).

Even though not explicitly stated in reference docs
( http://haxe.org/ref/type_params ), implicitly static methods
can be separately type parameterized from other methods of the
same class in HaXe, but not non-static methods.  This is
because for a static method, we do not have to create the
instance when we specify the class parameters:

http://haxe.org/api/lambda

Lambda<int,int>.fold(...
Lambda<int,float>.fold(...
Lambda<string>.filter(...

For clarity only, I will repeat that I also propose that
non-static methods be type parameterizable separably from
the class parameters. And I understand your point that we
must work today without it. My plans for Copute (or HaXe
patch) would instead optionally allow:

Lambda<int,int>.fold(...
Lambda<int>.fold<int>(...
Lambda.fold<int,int>(...

There are several comments at the mailing list claiming that construction of a new
iterator is semantically equivalent to proposed iterator.reset().  Note, some admit a
difference in potential performance, depending on implementation, but that is not a
semantic difference:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033910.html
http://lists.motion-twin.com/pipermail/haxe/2010-February/033923.html
http://lists.motion-twin.com/pipermail/haxe/2010-February/033927.html
http://lists.motion-twin.com/pipermail/haxe/2010-February/033928.html

Well these folks are missing the fact that if the iterator is consumed by Lambda,
then Lambda calls a function on each iteration, then that function is unable to reset
(nor backup) without conflating logic with the outer function that called the Lambda,
which of course defects one of the main points of the orthogonal composability of
functional programming.  It also defeats referential transparency, which will become
extremely important for programming on 1000 cores (as I will explain in future on
design of Copute).

I see that Dave realized this:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033929.html

And I do understand reset can not implemented for forward-only semantics:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033931.html

The simple solution is to have BiIterator (adds reset and possibly previous) inherit
from Iterator, then parameterize Lambda on Iterator type expected by the function
Lambda calls.  Everything should be able to implement BiIterator because the
forward-only Iterator cab save its construction arguments and always support a reset.
 If something can only be consumed once, then simply cache it in the Iterator.  The
ability to specify Iterator instead of BiIterator (when reset is not needed) will
enable to turn off the internal caching in those cases.

Btw, Lambda currently has a design error, because it doesn't have the optional
interface to pass the Iterator to the called function.

The reason bidirectional Iterator needs to be standard is so that we can write code
that is composable with unknown future code in the wild.  I will get more into this
notion of correct OOP and composability with Copute.  I think people do not
understand well that referential transparency dictates composability.

I think what is confusing people is that the current the HaXe Lambda (
http://haxe.org/api/lambda ) does not offer the option to pass the Iterator (nor the
Iterable) to the inner function that Lambda functions call on each iteration.  This
is a mistake in the design of Lambda, because thus it is impossible for the inner
functions to modify (such as reverse, reset, or skip forward) the Iterator being used
by the Lambda function to iterate the inner function.

First John:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033945.html

John, there would be no way to call Iterable.iterator() to get a new iterator, even
if Iterator will be input to the inner function with an improved Lambda.  Even if
Lambda functions did pass Iterable (or an Iterator without a reset()) into the Lambda
inner function, it would be useless to create a new instance of Iterator using
Iterable.iterator(), because the outer Lambda function would still be using the
original Iterator.  Besides even if you do create a new Iterator for use on child
nested inner functions, then there is still no semantics for telling the Iterator of
a one-time-only collection (e.g. a stream) to prepare (cache) for reset.  Those are
two reasons why there is no alternative to a BiIterator.reset() as a standard (which
should be optional to implement only for collections that want interoperability on
bidirectional consumers).

Also, you can see from above that there is no benefit to inputting the Iterable (the
collection itself) into inner function, and this is harmonious with the desire to not
conflate the the inner function of a Lambda with any thing more than the Iterator
(and even not the Iterator in many cases).  The whole point of Lambda, is that you
can reuse generalized inner functions, which are not just for Iterables (and often
not just for Iterators).

Tangential point is that a generalized inner function will not even be able to
reference the Iterable variable in the outer lexical scope directly, because this
would mean the function is not reuseable except in that one instance.  Here is an
example:

function f( v : Int )
{
   i.anything
}

var i = [0, 1, 2]  // an Array which is an Iterable
Lambda<Int>.foreach( i, f )
var j = [4, 5, 9];
Lambda<Int>.foreach( j, f ) // Bug


And again John:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033948.html

John, I hope you see above that the issue is not performance twiddling, but
algorithmically fundamental to minimum needed functionality and interoperability.


And now Cauê:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033947.html

Creating your sub-class instance of Iterator is useless in terms of full
interoperability, because Lambda takes an Iterable, not an Iterator, and the standard
Iterables such as Array, return an Iterator, not your sub-classed Iterator.  The
solution of course is here:

http://copute.com/dev/docs/Copute/ref/iteration.html

Iterable returns a BiIterator or Iterator, then Lambda takes functions which expect
an Iterator or BiIterator (or no Iterator). Obviously that solution depends on
function overloading, but you can use function naming to achieve the same in HaXe. 
Also in my examples above, the Lambda functions are methods, but you can easily
convert these to HaXe's static Lambda functions.

Also note that Iterator.index() is also needed, as there is no alternative.  The name
should semantically be index and not count (because of the potential reversible
sub-class).

Off Topic: in your example the name ReverseIterator is semantically inferior to
BiIterator.  Your sub-class is bidirectional.

And again John:

http://lists.motion-twin.com/pipermail/haxe/2010-February/033950.html

1) Read my prior post above, for why creating a new Iterator is not possible in the
inner function without conflating the inner function with the outer lexical scope. 
Besides there is no way for the inner function to stop Lambda functions such as
foreach().  They don't return the Iterator to their caller.

2) toList() is useless on an infinite stream

3) the stream Classes that don't want to be cached can refuse to implement BiIterator.

4) I hadn't seen any infinite streams that weren't bugs :D  Virtual memory is plentiful.

5) How the heck does an infinite stream ever stop iterating any way?

I had a typo in prior comment, I meant "iter" instead of "foreach".

> I think you conflate two different things: streams and collections. Reset
> does not make sense for streams.

Then don't implement BiIterator on your streams.

I can implement BiIterator on my streams because after all, it is only going to force
caching when I ask for a BiIterator.  Then I much rather have the caching in the
reuseable BiIterator than duplicated every where I need caching of my stream.


> For collections, iterator() may be called
> to produce any number of iterators, thus negating the need for a "reset"
> function.

No that is not true.  Please read again:

https://code.google.com/p/haxe/issues/detail?id=77#c17

> As soon as such a reset function is created, the next natural step is to
> start passing around iterators rather than iterables.

That is desireable.

> This will lead to
> bugs because code will call "reset" before or after using the iterator,
> and other code will expect an iterator to be reset or not to be reset,
> depending on its requirements. It's a headache.

The implementation of BiIterator shouldn't be expecting any such order.  I think I
can code a BiIterator properly for a stream but if not, then no BiIterators on streams.

> Iterators are bad enough because they are stateful.

Agreed, but when you need such state, it is best to encapsulate it.  Iterator is the
ideal encapsulation for forward iteration.  If you don't need or want BiIterator
state, then do not implement it.  It won't be forced on you.

> I think you should
> avoid iterators at all cost and use higher-order functions such as fold,
> map, etc.

Agreed.  But there may be cases where someone chooses to use a bidirectional
procedural algorithm.  After all, if state was unnecessary, then we would code in
pure Haskell with no Monads.

My objective with Copute, is to isolate the state in more intuitive ways.  I am
contemplating a "function" and a "procedure" keywords.  Only latter will allow to
reference the external lexical scope.

> A subset of these functions are well-defined for both streams
> and iterables. Indeed, I'm releasing a haXe library fairly soon that will
> provide separate implementations for streams and for iterables. No API
> changes in iterator are necessary or even desired.

Iterator is well defined for a stream.  BiIterator is optional.

The counter-point line of logic seems to be that since streams are not a perfect fit
to BiIterator, then do not support BiIterator for anything.  Because we need for
Iterable and Lambda to know about BiIterator, else we can not roll our own into them.

Additionally, in the cases where one does choose to use a BiIterator on a stream, it
will be superior to rolling your own caching each time.  Remember BiIterator is
orthogonal to stream.  Your stream code isn't impinged in any way (unless you CHOOSE
to optimize for BiIterator with some stream level tricks).

I think a key point keeps getting lost.  How is Iterable.iterator() going to work for
a stream?  It is not going to rewind unless there was caching.  But how would it know
to cache?  It is simply going to create a new forward iteration from the current
position in the stream.  So constructing a new Iterator is not a solution for a reset
on streams.  At least with BiIterator it becomes explicit which Iterables do not
support BiIterator.  Actually I just realized that I need to create a BiIterable to
inherit from Iterable.  I will correct my example code now here:

http://copute.com/dev/docs/Copute/ref/iteration.html

> I get an iterator and start iterating a collection. But do I
> call reset first or not?

By "get", I assume you mean Iterable.iterator() or BiIterable.iterator():

http://copute.com/dev/docs/Copute/ref/iteration.html
https://code.google.com/p/haxe/issues/detail?id=77#c22

If you are getting an "Iterator", then there is no reset, thus the only thing you
know is that it will forward iterate.

If you get a "BiIterator", then it should be in an initially "reset" state.  "reset"
means at the start of the first iteration ever on the Iterable, except for any
modification of the contents of Iterable by operations on Iterable outside of the
Iterable interface.

> If I do not call reset, the code will have
> different behavior depending on who calls it;

I do not understand what you see as a problem?  Please remember that state of
BiIterator.reset is distinct for each copy of BiIterator.  A new copy of BiIterator
is obtained on each BiIterable.iterator() or BiIterator.copy().


> if I must call reset,

The BiIterator is initially in a reset state upon BiIterable.iterator(), but not upon
BiIterator.copy().

> then I
> may forget sometimes, leading to obscure bugs.

You do not have to remember to call reset when you BiIterable.iterator().

> Moreover, if I pass the
> same iterator to another piece of code, which you suggest is "desirable",
> then it may call reset while I am in the midst of iteration, breaking my
> code.

If you do not want to allow that, then pass BiIterator.copy().  There may be cases
where you want to allow the inner function to reset your loop, e.g. the Lambda
functions should allow this generality.

The reason that proliferating Iterators (Bi or not) is "desirable" as compared to
proliferating references to Iterables, is because each Iterator has distinct state,
whereas if all code was interacting on Iterable, then they would be interfering with
each other's state.

> Iterators do not and should not have reset.

They do not and will not.  Only BiIterator is proposed to have reset.

> It will lead to numerous bugs,
> especially if people start passing around iterators in code rather than
> iterables.

No it will lead to less bugs by passing around BiIterator instead of Iterable.  If
you pass around Iterable, then Iterable.iterator() is ambiguous with respect to
reverse iteration state.  If you pass BiIterable, then you conflate the common state.
 Best is to pass around BiIterator (and copy() as desired).

> The whole notion is imperative and wreaks of bad design.

No BiIterator is less imperative than passing around an Iterable, because at least
you have a plurality of distinct states.  If you want less imperative code than
BiIterator, then pass around .copy(), and if you want even less imperative code, then
pass around Iterator instead.  The BiIterator exists only for those algorithms where
it makes it easier and justified.  Why should I force the programmer to do it the
Haskell way?  I give them all gradients in between imperative and pure functional.


> It
> requires super human discipline and diligence for correct code.

I do not see any extra dependence on state that wouldn't also be required if the code
operated on Iterable.iterator() and did its own caching some how.  In fact, operating
on Iterable.iterator() with custom caching is going to conflate state much more.

> People should not even be using iterators (in general) since nearly all
> operations can be done with higher-order functions on collections or
> streams.

Agreed but with caveats.  For example, lets say my incoming stream is in some form of
grammar that requires me to have unbounded look-ahead.  This can not be done without
caching the stream.  I would have two choices. I can either custom cache the stream,
or I can use BiIterable.  The latter is much less imperative, because the caching is
encapsulated and supports distinct instances of bi-state.

I think you did not understand the specifics of the proposal.  Let me clarify please.

http://lists.motion-twin.com/pipermail/haxe/2010-February/033960.html

> Take, for example, the following snippet of innocent looking code:
>
> for (a in list) {
>    for (b in list) {
>    }
> }
>
>
> Fails completely under your proposal.

That does not fail.

1) for( in ) uses Iterable, not BiIterable

2) Even if for( in ) used BiIterable, the BiIterator for the outer loop is not passed
to the inner loop, because for( in ) will call .iterator() distinctly for each loop,
and because each instance of BiIterator has a distinct state and is initially reset.

P.S. I am not participating in the discussion of pooling performance implementation
of .iterator() as that is irrelevant to the semantics we are discussing.

Thank you, as feedback caused me to make the following
documentary changes:

http://copute.com/dev/docs/Copute/ref/iteration.html

    // State of the first ever BiIterable.iterator
    // except for content of elements and the appendage
    // of additional elements.
    // (it is for this reason that methods of Iterable
    //  should not modify its instance, e.g. Array.splice
    //  should return a new array)
    function reset() : void

Also I improved the definition of index, as follows. Note as for a precedent,
Javascript supports passing index (and also the Iterable) for its standard Lambda
higher-order functions (
https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference/Objects/Array/ForEach
).  Note where I am soon headed is to enable Copute to pass any extra object to an
inner function via a mechanism similar to Monad, so then I can remove the specific
option to pass an Iterator from the Lambda higher-order functions.

class Iterator
{
    // # of next() performed + 1
    function index() : int
}

class BiIterator
{
    // # of previous() to reset - 1
    function index() : int
}

> People should not even be using iterators (in general) since nearly all
> operations can be done with higher-order functions on collections or
> streams.

As for why we sometimes may want to use imperative code for data flow that could be
represented by pure functional programming (e.g. higher order functions), I quote one
of the creators of Haskell:

"Pure functional languages have this advantage: all flow of data is made explicit. 
And this disadvantage: sometimes it is painfully explicit."

P. Wadler. Monads for Functional Programming In Advanced Functional Programming, pg. 2

> I was referring specifically to David's suggestion of putting the "reset",
> "next", and "hasNext" methods on the iterable (e.g. on the Array or List),
> in which case nested looping becomes impossible (among many other
> problems). Your proposal suffers from a similar flaw as code starts
> passing around iterators rather than iterables, because then someone will
> start an iteration and pass an iterator to client code, which can reset
> the iterator and cause an infinite loop.

To prevent opportunities for infinite loops, eliminate loop constructs entirely.

Any client code can make an infinite loop:

while( 1 );

If the outer function wants to prevent opportunities for an infinite loop, then it
can give the inner function a BiIterable.copy().

There may be cases where the outer function wants to give the inner function the
capability to reset the outer function's loop.  In those cases, the inner function
will be responsible for not creating an infinite loop (enabled when I added the
overloads that take previous return value P, which I plan to generalize with Monads).


> In addition, your proposal has other problems all caused by passing
> iterators around:
> 
> public function someFunc(iter: BiIterator<Int>)
> 
> In a large program there will be many such functions, and every time you
> create a new one, you need to answer the question: Do I call
> "iter.reset()" or not before I use the iterator that was passed to me?


Document your function, just like you have to do for every other function in your
program that you want people to use correctly.

Actually you are violating the principle of functional programming with this
non-sequitur.  The inner function should operate on the BiIterator it receives.  It
shouldn't expect it to be "whole" or "remainder" unless it is documented, as the
outer loop will determine that.  If your inner function uses reset in its algorithm,
then document how the incoming state of BiIterator affects the algorithm.


> Because that choice has no "correct" answer
> (i.e. sometimes client code
> calling a function will want it to operate on a remainder, other times, on
> the whole collection), some code will call reset and other code will not
> call reset.


I just gave the answer above.  It is same as for any inputs of a function, you have
to document them.

I can make similar non-sequitur arguments about Iterator.next().  The inner function
may expect the iterator to be 3 times iterated from the start of the iteration.  If
your inner function expects something about its inputs, then document it.

Actually I think you are making a valid point, which is that it would be useful to
have a mark() and resetToMark(), as this would in many cases be more useful and
orthogonal for an inner function, than a global reset.

But bear in mind, that reset() can be orthogonally used by the inner function (no
special documentation needed for the inner function), if insures it will next() until
it is back to at least the index() where it was before the reset().  So reset() is
useful for going back to consume the entire iteration-to-date again in the inner
function (e.g. I said an unbounded look-back and look-ahead might need to do).

And I do not hear any complaints about previous()?  I think it is also useful in some
orthogonal ways (no special documentation needed for the inner function), e.g.
similar caveats as for reset above.

> And then whenever I pass an iterator, I need to know something
> about the code that's going to use it. Either that or blindly call
> iter.clone() every time (defensively)

Yes you can do that if there is no documentation for the inner function.  Do you
prefer name clone() to copy() and why?

>, which is not only useless
> boilerplate and easily forgotten (which will lead to bugs), but destroys
> the so-called performance advantage of putting reset() on an iterator.

I am not involved in the discussion about performance.  I am interested in the
semantics only.  I tend to trust people to document their functions, else I won't be
using their functions, so I don't think I will need to call copy() blindly.

And if you want to get more performance in those rare blind cases, you can save
index() then compare on return from inner function, then next() as many times as
necessary to get back to where you were.

As for boilerplate, I don't expect to be using functions without documentation.  Do
you?  If an inner function takes BiIterator instead of an Iterator, then I am going
to be expecting some documentation on any dangers.

> Iterators are already stateful.

Agreed.

> Adding "reset" to them makes them even
> more stateful

I am not proposing to add that to Iterator, only to BiIterator, which will be
something that inner function should not input, unless it absolutely needs the
functionality.  Then it better document why.

> and ambiguous and multiplies the possibilities for errors.

As far as I can see, you are making a mountain out of an ant hill.  Are you scared of
hidden while( 1 ) loops in undocumented inner functions?

> The best solution is to leave iterators as they are, define a subset of
> higher-order functions for streams, and when you want caching on a stream,
> do so explicitly with caching facilities provided on the stream itself.

And you just throw away re-useability of iteration across different collection types.
And for what gain?  To eliminate fear of ant hills?

Stateful programming gives the opportunity for state spaghetti.  That is going to be
true unless you move to a purely referentially transparent language such as Haskell.
 Then everything is a constant and all global state is propagated via Monad from the
bottom tips of the functional tree up to the main trunk:

http://copute.com/dev/docs/Copute/ref/Functional_Programming_Essence.html#State_Monad

Anything short of that, and you are just trading one ant hill for another ant hill. 
I am sure I can find ant hills created by your alternative stateful proposal.  For
example, as I said previously, without reset and previous, then inner function look
back and look ahead algorithms, are going to need to conflate themselves statefully
and in non-standard way with the outer loops.

Thanks for the prior discussion, I have changed BiIterator.reset() to goto( index = 0
), which thus implements the mark() and resetToMark() discussed previously.

I have also changed copy() to clone() and added a new ClonedBiIterator, to address
the prior discussion, so inner functions can require that they receive a clone() and
to announce that they do not wish to modify the outer loop iteration state.  This
protection applies to forward iteration state as well, so it is useful even without
goto or previous.  This change thus forces the boilerplate and the overhead of clone
in all such usage.  However, the Lambda functions will do this boiler plate
automatically.  And/or the compiler can do it automatically because the
ClonedBiIterator.new() does the clone() call as it inputs a BiIterator (however
allowing such copy constructors will create more opportunities for ambiguities in
type inference).  The performance overhead of clone() should be negligible because it
is merely creating a new copy of the integer for index().  Internally a pointer to
the integer and stack of available integer pool is extremely fast.  If the platform
supports reference counting with Bacon algorithm for garbage collection, then the
pool can be smaller.  I don't want to expend more time on performance implementation
discussion.

Also I want to EMPHASIZE that the above will only apply to code that needs the
features of BiIterator.  Most code can use Iterator instead.

> If you are designing your own language I suggest you do not support
> iterable at all, and instead support something like "foldable", which
> exposes a fold method (foldr as well if you like right-to-left folding).

Thank you. I have that already as Iteration has fold() and inherits from Iterable,
thus e.g. Stack inherits from Iteration.

> Most useful operations can be built on top of a fold, and it's purely
> functional (when used on immutable data structures) rather than purely
> imperative, like iteration.

Agreed fold can be referentially transparent when it is applied on an immutable data
structure.

I am looking into how to integrate Monad with these Lambdas in order to get the
appearance of mutability with the actuality of immutability.  Any ideas?  You might
refer to my simple explanation of State Monads:

http://copute.com/dev/docs/Copute/ref/Functional_Programming_Essence.html#State_Monad

I changed ClonedBiIterator to ClonedIterator, because as mentioned, Iterator.next in
the inner function is also dangerous to the outer loop.

Since I have proposed that Lambda functions offer the option (use the other overloads
if you don't need this feature) to input the Iterator to the inner function, then
cloning is necessary to avoid special documentation of the inner function.  And it
still allows the fully generalized case, when an inner function prefers to take an
Iterator (or BiIterator) instead of ClonedIterator.

One may argue that passing around the Iterator is too stateful and further from
functional programming.  I believe there are many gradients between the extremes (and
ClonedIterator passed by Lambda is step towards more state from Lambda without
passing Iterator, and Iterator or BiIterator passed by Lambda even more stateful, and
inner function referencing the Iterable in outer scope is even more stateful), and
there are times when it will be just too painful to get an interwined algorithm into
the full referentially transparent paradigm:

https://code.google.com/p/haxe/issues/detail?id=77#c26
(Haskell creator mentions the trade-off)

The advantage of passing Iterator (over specialized interfaces for each iterable
type) is that it gives us a granular composability model on iteration of plurality of
iterable types (e.g. collections, streams, deterministic generators, etc).

There will be ways we can offer referential transparency on specialized models of
data collections, e.g. list in Haskell.  But this does not preclude the above
advantages for those cases where they are more compelling.

Eureka!  Thanks, the perfected design just came into view.  All the boilerplate
and performance issues can be avoided, as I added ImmuIterator, this cascaded several
changes:

http://copute.com/dev/docs/Copute/ref/iteration.html

> This is an improvement

Thank you.

> but you still have some absolutely hideous things
> in there, such as:
> 
> // Swaps the meaning of next and previous
>     // on ONLY the next obtained iterator()
>     // Returns this
>     function reverse() : T
> 
> This is as stateful as you can imagine.

Only stateful external to Iterator, because it it is immutable within the scope of
Iterator.  Within the scope of an Iterator (an iteration), it is no different than
passing a constant in a State Monad:

http://copute.com/dev/docs/Copute/ref/Functional_Programming_Essence.html#State_Monad

> In general, you have no way of
> knowing whether calling iterator() will give you forward or reverse
> iterator, and no way to know if calling iterator() two times in a row will
> return the same iterator.

The interface iterator() does not define what the "next" direction means.  That is
the case now with HaXe. I think it is desirable to not define it, because there
really isn't a way to define direction general for any iterable.

Even without reverse() you have no way to know if calling iterator() twice will
return the same iterator, because the Iterable may have changed and/or it may not be
reversible from a previous iterator (i.e. uncached streams).  That is also the case
with the current HaXe Iterable and Iterator interface.

> Anyone wanting a reverse iterator should have to call a reverse iterator
> method. Things must be explicit in order to avoid bugs.

Or an optional argument for iterator().

Forward and reverse are arbitrary.  The only difference we can define is relative to
each other, they are opposite directions, but we can not define their absolute meanings.

If we make them separate interfaces() versus a state toggle, then BiIteration.lambdas
will also either need two names or an optional argument.

I agree with your suggested change and will make it now.  Thank you.

> Also index() should not return an int, but a Marker, which provides no
> methods; and goto should take such a marker. This makes the code more
> resistant to bugs, because it means you cannot move to a position you have
> not seen (and have a reference for through index()).
> Otherwise sometimes
> you will call goto(0) when what you really wanted was to return to the
> first position you read.


Ah yes.  Excellent.  I believe in community effort!  Given enough eyeballs, all bugs
are shallow (and that includes design bugs).

> Note I still strongly recommend you reconsider the imperative approach,
> and instead base your methods on Foldable or even Traversable:
> http://www.haskell.org/haskellwiki/Foldable_and_Traversable
> 
> Meanwhile, I'd recommend a separate streams API based on ideas from
> functional reactive programming.
> 
> In my opinion the world does not need another mostly imperative, slightly
> functional programming language. If you want to build a new one with
> Copute, I recommend taking a different approach entirely; it will draw
> more people to help you, since right now people will simply say, "Why not
> use haxe/javascript/etc?" (And rightly so.)


I will review the above suggestions in light of continued work I am doing on
contemplating how to achieve maximum interoperability of imperative and functional
programming.  I may have another reply for you on this in future.

Added an example to show that recursion can be used instead of iteration, which one
of the claimed properties of functional programming:

http://copute.com/dev/docs/Copute/ref/iteration.html

(function Each( a, f ) f( a.head ) Each( a.tail, f ))( instance ) my[i] = s //
recursion can iterate

Note Python is crippled for "pure" FP because it enables dynamic rebinding for what
are intended to be "pure" functions:

http://www.ibm.com/developerworks/library/l-prog2.html

I have already prevented this in Copute with my definition of new 'pure' keyword
which is disallowed to be assigned to 'dynamic' variables.  This will be presented
shortly, I am just making a notation while it is in my mind.

> Note I still strongly recommend you reconsider the imperative approach,
> and instead base your methods on Foldable or even Traversable:
> http://www.haskell.org/haskellwiki/Foldable_and_Traversable

All 3, Iterable, Foldable, and Traversable can be supported, within the OOP model
presented (and the purity model to be presented next will help).  Iterable requires
minimally the ability to next().  Foldable requires the ability to apply a function
to each element but as atomic operation without any control over the order. 
Traversable is like Foldable, but returns a Traversable instead of a single value.

There is nothing special about the above that requires the language itself dedicate
to any of them.  In fact, the more I have dug into the new purity model for Copute,
the more I realized that most of Haskell is libraries, not language.

If I am wrong, I hope someone will point out to me why (ideally if can be, please no
subjective arguments, only indisputable facts).  I will present the purity model for
Copute within an hour or so.

Here is the new purity model for Copute:

http://copute.com/dev/docs/Copute/ref/function.html#Purity
http://copute.com/dev/docs/Copute/ref/class.html#Purity

As far as I know, it has never been done like that before in world?  The significance
is that purity is absolutely essential to move to next level in computing (100 cores,
WLAN funtional composability like the hyperlink is to WWW), and Copute makes more
intuitive where imho Haskell buried the paradigm in concepts and syntax that is
unfriendly to non-mathematicians.  Don't fret about the absence of discussion of
Monads, Arrows, etc, as these are all just libraries, not language.  For example, the
state things that Monads do, i.e. 'Maybe' exceptions, 'State' injection, are merely a
way of declaring some functions as impure combined with type inference.

What is very interesting to me, is how the new model changed the prior iteration model:

http://copute.com/dev/docs/Copute/ref/iteration.html

It seems it forced a more correct model that was not obvious.  For example, in order
for the Lambda functions (each, fold, map, etc) to be 'pure' it was necessary to make
the constructor of *Iterator take an *Iterable, instead of *Iterator.iterator
returning one.  Ditto clone() must be a constructor.  That all seems more correct,
now that I am taught by the model to think about it.

ImmuIterator and ClonedIterator are eliminated by this purity model.  Instead purity
is able to define when the inner function can be trusted.  Wow!  Love when a model
eliminates boilerplate by being more general and more useful.

The purity model did force new IOIterator, because next() can't be just mutable for
an *Iterable container that mutates on next() (because mutable in that case applied
only to *Iterator, not to *Iterable), thus we need IOIterable distinction. And
*IOIteration methods can not be pure.  So goes to show that Iterable is not the ideal
interface for streams, which I think was one of the prior points made.  However even
an atomic operation such as Foldable or Traversable which as long as their methods
are merely mutable (not totally impure), then could be used within a pure function.

Note a change I made not caused by purity, is that Iterator.mark was removed because
an Iterable must not be restricted as IterMark requires, thus I added
Iterator.index() since there is no Iterator.goto().  Bi* fulfill IterMark and thus
support mark() and goto().

I did create a few new abstract super-classes for the *Iterators, but these were not
required by the purity, they just made sense and so they can be input by inner functions.

I welcome any feedback, positive or otherwise.

> All functional routines (e.g. fold, map, etc) can be built off Iterator.

Agreed, except to adopt your prior point that ideally one still wants Foldable and
Traversable in addition to Iterable, because some containers can not be iterated
without mutating the container, which is a side effect and violates the composability
requirement of pure functional programming.

> BiIterable is not likely to be widely used because of its statefulness
> will make code more error-prone, not less.

BiIterable is now 100% pure.  No state at all if its Lambdas are called on a pure inner
function.  The pure inner function can clone the BiIterator if it wants to also be
pure and depend on the the state of the outer loop.  Clever?

Copute's purity model helps teach what can be pure.

> Nothing that exposes "next" can be pure, because "next" returns different
> values when you invoke it with the same arguments (i.e. no arguments in
> this case). If you want pure, you can't have iteration.

It is BiIterable is that is 100% pure, not BiIterator.next().  Clever eh?  Every time
you call the BiIterable methods, then you will always get same result (assuming inner
function is pure).  I have just generalized the purity model more than what Haskell
can do because I added concept of mutable for class methods!

Conceptually that rule for purity that allows mutable on instances created within the
function, is similar conceptually to as if you made .next() an inline, it is just
operating on values within the function and no side-effects.

I want to elaborate a bit on the my prior comment, because there may be some people
will think "it is impossible to create a pure function that calls an impure one".

First of all understand that iteration can be written in free point recursion style
which is 100% pure as long as the container is immutable:

function Each( a, f )
{
   a.length && (f( a.head() ) Each( a.tail(), f ))
}
Each( container, function inner( element ) {} );

Now let me redefine Each to iterate purely (assuming container is an array):

function Each( a, f )
{
   for( i = 0; i < a.length; i++ )
      f( a[i] );
}

Each will still return the same results each time it is called, as long as the
container is immutable.  And there are not side-effects outside of Each (assumer
inner() is pure)  The key observation is that i is only changing within the pure
function (and since there are no external references to i, then incrementing i is
conceptually a pure function that returns a new copy of i).

Iterable.each() and BiIterable.each() are doing similar pure form of iteration.  The
*Iterator.next() modifiers the *Iterator, but not the *Iterable.  And that instance
of *Iterator is created within and never referenced outside of the pure function
each(), thus it can be conceptually considered to be returning a new copy of itself
instead of modifying itself at least as with respect to the external purity for
callers of each().

The clever thing that I have done to expand upon what Haskell can view as pure, is I
have added the concept of methods that mutate their instance only, with no potential
for side-effects beyond that instance.  Thus as long as that instance is instantiated
(with a constructed that doesn't take references to instances) within the pure
function, then purity is assured.

I thought very carefully about the rules for purity.  For example, I realized that
the return of an instance from a function does not affect its purity, but rather how
the caller uses the instance affects the caller's purity.

I am confident I have improved drastically on Haskell.  I hope people don't think I
am naive or joking.  If so, please share your logic.  As I wrote previously in
private email, this changes everything in computer languages.

OT: since we are off on the tangent of Copute's new proposal for 'purity', it also
occurred to me while I was designing it, how it was different from C++ 'const'. 
Actually it is different in a very important way, and in fact the failure of 'const'
helped clarify a key design choice.  I was involved in some discussion about 'const'
in 2008:

http://lists.motion-twin.com/pipermail/haxe/2008-November/020919.html
http://lists.motion-twin.com/pipermail/haxe/2008-November/020935.html
(also some of my early thinking about Copute in general near bottom, especially
theory about Dunbar number limits on composability of caveats which is why we need
purity, economic driver of open source, etc)

In C++ 'const' when applied to a data type meant the data was immutable every where
and infectiously cascaded the 'const' in other types where the entire program nearly
could end up being 'const'.  It was extremely annoying and unhelpful.  The focus of
'const' was to be able to declare an object immutable, but then this could require
one could only call 'const' methods.  The problem of course was the focus on the data
type being 'const'.

Copute's purity is about what functions do, not what data types do.  That is the key
difference which enables more flexibility.

For example, it has no bearing on the pureness of a function whether it returns an
instance with impure methods.

The C++ 'const' on a method is lacking some of the requirements placed on 'pure'
methods in Copute. As well, 'mutable' is nothing like 'const' and (as explained in my
prior comments) is crucial for achieving pureness of some key functions, that afaik
Haskell can not achieve.

I assume Copute's proposed purity model is totally new, until someone can point out
any language that has done similarly.

const is useless unless you want to make some data const.  There is no such thing as
a const function, only const methods.  Thus const data thus forces other containers
to be const and force the const to propogate even where you don't want it to be.

Pure has nothing to do with declaring some data const, it has to do with declaring
the the function is referentially transparent and that it has no side-effects.  Pure
does not get forced outwards as const data does on its containers.  Pure is an inward
(within the function) requirement.

A const method returns (operates on) a const instance and that causes const to
cascade (infect) externally, not inwardly.

Let me take one more stab at explaining why const has nothing to do with pure.

A C++ const method is not pure, if for example it calls a C++ static method.  Thus
const is not concerned with purity, but rather with making data immutable.

And there is no such thing as a const non-method function in C++, thus clearly const
has nothing to do with pure functions.

The way const attempts to control side-effects, is by making data immutable.  But
this concept of const data is incongruent with the functional programming model,
because in FP the functions are the data.  And BTW, this is why const forces itself
to propagate where we do not want it to be (e.g. out to every external container).

So what is needed instead (as proven by the lambda calculus) is to make the functions
pure and from that, data will be const that should be, without inhibiting external
composability of pure functions with impure ones.

const was entirely the wrong model.

Made further improvements and corrections to iteration model:

http://copute.com/dev/docs/Copute/ref/iteration.html

OT: again on the tangent of purity, I have made some modification to the rules to
obtain optimal orthogonality, so that class instances can be maximally used with
impure functions without subverting purity:

http://copute.com/dev/docs/Copute/ref/function.html#Purity
http://copute.com/dev/docs/Copute/ref/class.html#Purity

Specifically I removed the limitation of not allowing a pure function to modify an
instance returned from a pure function or pure (also mutable) method, and instead a
pure method now infers that the class instance is immutable.  Thus a pure method
return value that contains any portion of that instance will be inferred to be
immutable, which may be explicitly declared with the keyword 'immu' class type
modifier.  Yet such instance can simultaneously be returned as not immutable by
mutable and impure methods.  I also allowed pure and mutable methods (and
constructors) to input and store instances in their class's members, as input class
instance arguments for pure functions are now inferred to be immutable.  These
instances are inferred to have an immutable type in the class member, and thus can
not be simultaneously be returned as not immutable by mutable and impure methods. 
The point of all this is to maximize flexibility (e.g. an Iterator can be constructed
on an Iterable, even cloned, carrying forward the immutable Iterable reference while
transferring purity to the consumer of the Iterator), while preventing transitive
subversion of purity (e.g. a pure method can not modify the return of a pure method
which returns their mutual instance).

This illuminates key differences from C++ const.  First, const does not automatically
propagate to the type parameters of a class (e.g. const Array<const T> is roughly
equivalent to immu Array<T>, but not to const Array<T>).  Second, the immutable
attribute is (in most cases) inferred by purity and not inflexibly attached to the
instance in orthogonal propagations.  For example, if Iteration.each() was const then
the Iterator constructor would take a const Iteration<E>, but this would not force
the E elements to be const as returned by Iterator.next.  To achieve the immutability
we need for purity, then either this use of Iteration would have to be inflexibly
declared with a const E element type parameter (which means the elements can never be
modified any where in the program), or Iterator's constructor could enforce the type
conversion (if the compiler supports implicit cast from const Array<T> to const
Array<const T>) but then the const each() method will not be making this guarantee
(only by each()'s use of the correct type conversion will it be upholding a contract
that is not stated in its declaration).  Also a const each() can do other impure
things such as call global impure functions and access static class members. Purity
is a more restrictive yet also more orthogonal attribute, as it applies only the what
pure function and methods do, and does not force the data (instance) itself to be
const every where (that one might use impure functions on).  In short, const is
focused on making data immutable, and pure is focused on making functions arguments
immutable.  Note also that immu can not be applied to non-class (Basic) data types,
such as int, float, bool, and string.

P.S. I allowed to throw an exception from a pure function.  This does not create
state that subverts the associativity of referentially transparent lambda calculus. 
Only try and catch do.  This was important because otherwise the only way to handle
error return in pure functions is via a Maybe or Exception monad:

http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf#page=8
(section 2.7 Exceptions)
http://copute.com/dev/docs/Copute/ref/Functional_Programming_Essence.html#State_Monad

Note that Maybe monad (equivalent to overloading all functions and operations on null
type) will be useful where we want to overload for all functions (including
operators) and pass through the null (error) result without needing an impure
function to catch (but this will be overly intrusive for cases where we just want to
abort the entire program on error or are catching the error in a stateful impure
function):

http://ianen.org/articles/monad-is-not-difficult/

Should take a deeper look at this sometime:

http://osteele.com/sources/javascript/functional/

OT: purity parallelism (referential transparency, any order of execution) might mesh
well with E's distributed computation model:

http://www.crockford.com/ec/

I added a parameterized version of *Iteration.some<V>, so that the inner function can
return a value other than true:

http://copute.com/dev/docs/Copute/ref/iteration.html

I am using this now (in JavaScript for the bootstrap compiler) and it is useful and
works well.

I added a notation that Array must support a way to select whether null elements are
iterated.

Also the JavaScript new Array( literal number ) creates an array with a length but
undefined elements, which of course do not get iterated.  Unlike in HaXe which
supports non-nullable default types on AS3/Flash9+, all types in Copute will be
nullable always.  Thus I think new( n : int ) must create an array with n null
elements.  There is no undefined value in HaXe and Copute, only null.  I suppose
JavaScript (forEach, etc) iterates null elements but not undefined ones.

Added a map<E2> overload, so that map can output a container with a type of elements
different from the source container:

http://copute.com/dev/docs/Copute/ref/iteration.html

I have rename *Iterator to Uni*Iterator, and Bi*Iterator to *Iterator.

Realized that Uni*Iterator.clone() requires bidirectional capability, because one
copy of an iterator may have its next() called, while the other has not yet, so I
removed clone() from the Uni*Iterator.

And I realized that Uni*Iterable.iterator() can create new instances of Uni*Iterator
and thus subvert the reason clone() was removed above, so thus each Uni*Iterator must
always update every Uni*Iterator instance, and so thus Uni*Iterable has to contain
the single Uni*Iterator instance as one of its members.  Thus Uni*Iterable.iterator()
can never be a pure method.  Thus 2 unnecessary classes UniMutaItera* were removed,
and remains UniIterable and UniIterator.

Added *Iterator.iterable()

Realized that it is often easier to implement an iterator with bidirectional
capability only via only clone(), than via previous(), mark() and goto().

Thus I split Iterator into Iterator and BiIterator, where the former has only clone().

I have further generalized purity granularity (afaics, an advantage over Haskell), by adding the following:

A function which is declared (at any nested depth) within a second function, and is pure except that it does any of following, does not cause the second function to be impure:

    * References (but not modifies) any class instance argument of the second function
    * References or modifies any built-in type instance (argument or local variable) and/or any class instance instantiated with a pure or mutable constructor within the second function.

================

The point of the above and the mutable method is that a container function is pure as long as it only references and modifies local instances, even if it contains functions/methods which reference and modify outside their local scope, as long as those are in the container function's local scope.

The use case that inspired the above addition, is a local function which is input argument of a pure iteration, but it is much cleaner syntax to reference the local variables of the function calling the pure iteration, than to define variable arguments for pure iterations and pass those variables into the pure iteration.

Issue 37 explains why we want to encourage use of container iteration (e.g. Arrap.map) instead of imperative loops (e.g. for and while). This is why I have not included a 'for' statement in Copute. I would like to eliminate 'while', but I am not yet clear that every possible situation can be coded in Copute's functional programming model, i.e. Issue 8 and Issue 33. As we gain more experience, 'while' may be deprecated.

Let me expound on the discussion of 'const' in Comments 31 - 37.

1. 'const' was for making an instance immutable every where; whereas, 'immu' allows the instance to be mutable in non-pure functions, i.e. 'immu' is for propagating immutability within a chain of pure functions, and the 'immu' attribute is ignored (and automatically type convertible to a non-'immu', but will propagate through non-pure function inferred) when an 'immu' instance is return to a non-pure function.

2. 'immu' is only applicable to instances that are assigned by reference, because it is only concerned with referential transparency across the assignment of arguments and return value of the function call, so is not allowed (or ignored) on basic (built-in) data types, such as Int, Float, Bool, and String. Whereas, 'const' was allowed on basic types to indicate a non-variable value.

3. 'const' did not automatically propagate to the type parameters of a parametrized type, whereas 'immu' does. This was because 'const' would propagate every where its type parameters were used in the program. This made 'const' effectively not an orthogonal attribute, as it couldn't be applied to parametrized type, without forcing it to applied to all the type parameter cases throughout the program.

4. As detailed in Comments 28, 29, 30, and 37, the orthogonality of the 'immu' attribute enables one to do referentially opaque (non-pure) iteration within a pure function without violating the purity of that function, e.g. the transitive purity of the Iterable type is preserved.

Instead of iterating through IO string or IO array, it is possible to abstract the data structure as a string or array that has lazy evaluation where the needed portions are loaded implicitly from IO on demand without burdening the programmer with the details of that load, buffer, and garbage collection. Thus bidirectional iteration could be abstracted as implicit lazy buffering on random access.

Regarding #2 in Comment 48, I have decided to allow 'immu' for types that are not assigned by reference, which in this case which apply in pure and non-pure functions. This is because otherwise I would need a 'const' keyword for this:

https://code.google.com/p/copute/issues/detail?id=40

Note this use of 'immu', will not cause it to propagate, because by definition, these cases are where types are assigned by copying the value, so thus the 'immu' does not propagate even in a pure function for these cases.

Expounding on #1 in Comment 48, 'const' also propagated backwards up the hierarchy of a hierarchy of functions, because 'const' insured that every assignment to a 'const' was also 'const', i.e. that nothing could modify that instance if any function ever accessed a 'const' reference to the instance at compile-time.

Whereas, 'immu' does not guarantee what outer functions will do to the referenced instance, it only insures that within a chained hierarchy of pure functions, that the instance is not modified. Thus where 'const' could be used to create a referentially transparent callback, Copute's purity model can not:

http://copute.com/dev/docs/Copute/ref/class.html#Method_Callback (see attached for archived copy)

But at what cost? The 'const' propagated every where, and an entire constant program can do nothing.

class.html 35.9 KB   View   Download

Comment 51 states that generally a function Fc that contains a closure (i.e. partial application, which is not the same as currying) is not referentially transparent (unless the whole program is 'const').

Comment 46 states the conditions where calling Fc does not cause the container function to be impure.

Comment 46 has an error, the "or modifies" must be removed, otherwise the order of calling Fc matters (e.g. by another pure function Fp), which is the antithesis of referential transparency. Also Comment 46 correctly implies that Fc can not be pure outside of the container function, and I want to state that explicitly.

Comment 46 states that calling Fc is pure relative to the purity of the container function. If a pure function Fp calls Fc, or even another pure function Fp2 calls Fp, Fc will be referentially transparent (static external state-machine) within Fp and Fp2. Calling Fp or Fp2 is not pure within the imperative code of the container function which can modify the instance referenced by the closure of Fc, but this doesn't matter to the purity of the container function.

Thus we can make Fc pure as long as it meets the corrected requirements of Comment 46.

Filed this bug report for HaXe (I bet Nicolas will mark it Won't Fix or Invalid):

https://code.google.com/p/haxe/issues/detail?id=340

I am referring to this API:

http://haxe.org/api/lambda

Global functions which operate on Iterable, which are not methods of Iterable, is semantically flawed, because the optimum implementation may vary by subclass of Iterable.  For example, there shouldn't be two ways to get length or count, or to test isEmpty or empty.

This is amplified by afaik that HaXe doesn't have function overloading nor type parametrization of non-static functions, so there is no way to replace the Lambda implementation for a specific subclass of Iterable.

Also in order to support homomorphisms such as map, filter, scan, that output the same container type as they operate on, e.g. a morphism from an Array<E> to an Array<E>, not always to a List<E>, then it is necessary to further parametrize the Lamba. However, if these would be made methods of the subclass of Iterable, then one wouldn't have to specify that type parameter on each call, as it would be built-in to the instantiation ot the subclass of Iterable.

Also wouldn't have to repeat the boilerplate "Lamba.func( Iterable" everywhere, it would be "Iterable.func(" instead.

Afaics, in order to optimally fix this, would require a change to the HaXe compiler to support mixins, similar to Scala, because in my trial design of this API, it became apparent that the standard implementations would need to inherit from Iterable, but they can't implement Iterable. HaXe doesn't support such a mixin capability, which is probably why the Lambda was done the way it is.

Filed another bug report for HaXe:

Lambda.indexOf is semantically useless (ambiguous)

https://code.google.com/p/haxe/issues/detail?id=341

Since the API for Iterable does not input an index, then the indexOf has no purpose. The indexed element access of any subclass of Iterable, e.g. Array, is not semantically tied to the iteration order. This is an adhoc assumption.

This is also why structural typing a/k/a duck typing, e.g. HaXe's typedef, is semantically ambiguous and should not be included in language:

http://copute.com/dev/docs/Copute/ref/intro.html#HaXe
http://copute.com/dev/docs/Copute/ref/class.html#Static_Duck_Typing

Filed another bug report for HaXe:

Lambda.count<A> is semantically erroneous (too broad)

https://code.google.com/p/haxe/issues/detail?id=342

An Iterable is not always countable, because it may not be rewinded or reset on Iterable.iterator(), e.g. a subclass which reads from a stream and does not cache the elements read from the stream.

The semantic of countable belongs in a container, which is a subset of the Iterable category. Iterable means anything that can be enumerated, but that does not imply that everything that can be enumerated must also be collected (i.e. cached or contained).

In short, count should not operate on an Iterable, but rather on a container interface which inherits from Iterable.

I added to the bug report at HaXe:

Lambda non-method style iteration is semantically flawed

https://code.google.com/p/haxe/issues/detail?id=340#c1

Let me provide another example of why some subclasses of Iterable may have different optimum implementations of homomorphisms such map, filter, and scan.

Say for example, the subclass of Iterable is a singly-linked list.  A singly-linked list is more space efficient than a doubly-linked list, and it can be implemented with a recursive, even immutable data structure (which is very important for referentially transparent FP):

http://en.wikipedia.org/wiki/Linked_list#Singly-linked_linear_lists_vs._other_lists

But elements can be added efficiently to the head, but not the tail, end of a singly-linked list. Adding to the tail end requires walking the entire list from the head, on each add.

Thus, homomorphisms that output a singly-linked list, would be more efficiently implemented with a variant that builds the singly-linked list in reverse order (by efficiently adding to head), then reversing the list in one operation at the end of the map, filter, or scan, then returning the reversed list.  This is because reversing a singly-linked list, only requires walking the list twice.