Re: [Caml-list] [ANN] The Missing Library

[skaller <skaller@users.sourceforge.net>]

On Wed, 2004-04-28 at 19:18, Jon Harrop wrote:
> On Wednesday 28 April 2004 9:37 am, skaller wrote:
> > On Wed, 2004-04-28 at 15:13, Jon Harrop wrote:
> > > ...
> > > more interesting connectivities than a bidirectional iterator can
> > > represent and which do not exhibit a clear notion of "sub".
> >
> > That isn't true. Computers can only do things in sequence
> > (well, ignoring fledgling parallelism).
> [snip]
> 
> I think you've taken the STL concept of an iterator and generalised it so much 
> that it now covers all computation. :-)

All computation by sequential machines.

> This notion of an "iterator" would have to be specialised to a specific 
> sequence-generating algorithm. That algorithm could be arbitrarily 
> complicated. Sounds like a higher-order function to me. What aspect of this 
> can ocaml not express/enforce?

Control inversion. In Ocaml you can write:

List.iter (fun x -> print_endline x) ["Hello"; "World"];;

but this isn't an iterator solution because the client
algorithm is a callback. Callbacks suck :)

Using an iterator we write:

while ( p != e) do print_endline (get p); incr p done;

This is quite different because the client algorithm
is *reading* the data, not being called with it.

The List.iter style HOF is very limited in utility
in a functional language: there is no state.

In Ocaml you can add state of course. But it's a mess.
The saving grace of the HOF is that for simple problems,
the termination is assured, and, the statelessness
of the callback is actually an important property 
for reasoning about semantics.

The control inverted solution is clearly much better
for complex problems because it allow the stack
to maintain some state.

to say another way: an iterator IS just a control inverted
HOF, indeed, the (abstraction of) the List.iter HOF.

A third view: all computation is an engineering combination
of the List.iter kind of iteration and the 'iterators'
kind of iteration. Something about 'bisimulation' and
inductive and coinductive types and categorical duality
principle is here but I don't know exactly what. 

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners