[erlang-questions] generators/iterators

[ok]

On 17 Jun 2007, at 8:16 am, Damien Morton wrote:
> Coming from a strong Python and C# background, I find myself missing
> generators/iterators.
>
> For example, when using list comprehension syntax, I find myself  
> wanting
> to use a function as a generator
>
> items(X) ->
>     fun() -> next_item(X) end.
>
> [Y*Y || Y <- items(X)]
>
> Would it be simple to have erlang recognise a function as a generator?

While Erlang functions *can* have side effects, most of them shouldn't.
So let's design a functional interface here.  See "Structure and
Interpretation of Computer Programs" for background, but a simple
approach is
	F() => []		at end of list
	F() => [H | F']		not at end of list.
For example, let's try a range of integers:

	range(L, U) ->
	    fun() ->
		if L >  U -> []
		 ; L =< U -> [L | range(L+1, U)]
		end
	    end.

Such things have been called 'streams' and 'lazy lists'; the difference
between what we have here and a real stream or lazy list is that the
result isn't remembered.  Whenever you call F() the work will be
repeated.

Suppose we have such a function and want to recover a list from it.

	f2l(F) -> case F()
		    of [] -> []
                     ;  [H | G] -> [H | f2l(G)]
		  end.

Now whenever we want to use such a function as a generator, all we have
to do is
	[Y*Y | Y <- f2l(items(X))]

If it's that easy, why not make the compiler do it?
Because there are many 'functional generator' interfaces possible.
You would still have to have something in the expression to say which
of the methods you were using, and it might as well be f2l(_).

The native/natural Erlang analogue of a Python iterator is a function
that returns a list.  (The idea of iterators signalling a *normal*
condition by raising an exception is pretty disgusting.  Prior art did
not do that.)  This is also the native/natural equivalent in Haskell.
For example, I have some students doing a simple analysis of the Lego
robot language NQC, with code like this:

	direct_uses :: Identifier -> NQC_AST -> [Identifier]
	direct_uses name nqc =
	    let (b,c) = fun_body False nqc name in
	    list_to_set [i | (s,c') <- substmts b c,
			     e <- stmt_exprs s,
			     VarExpr i <- subexprs e,
			     not (deep_declared i c')]

where substmts returns all the statements directly or indirectly
contained in a statement, stmt_exprs returns all the expressions
directly contained in a statement, and subexprs returns all the
expressions directly or indirectly contained in an expression.
Now Haskell is a lazy language, so this is equivalent to a backtracking
search in Prolog.  But this would still be a reasonable way to proceed
in Erlang:  the space required for the explicit lists is comparable to
the space required for the data structures being iterated over.

I *would* like to be able to iterate over tuples in Erlang, either
by having a new <-: symbol like <- but working over tuples, or by
having the compiler optimise <- tuple_to_list(...) specially.  The
former is how Clean does it; the latter may be a better approach for
Erlang and would allow for other optimisations in the same spirit,
including (a better named version of) f2l(), should there ever be any
great need for it.