EEP: XXX
Title: Extensions to comprehensions
Version: $Revision: 14 $
Last-Modified: $Date: 2007-06-29 16:24:01 +0200 (Fri, 29 Jun 2007) $
Author: Richard A. O'Keefe <ok@cs.otago.ac.nz>
Status: Draft
Type: Standards Track
Erlang-Version: R12B-4
Content-Type: text/plain
Created: 30-Jul-2008
Post-History:



Abstract

======================================================================
    Add Clean-inspired multi-sequence generators to comprehensions,
    making code more intention-revealing and reducing the need to zip.

    This is related to EEP 12 [1], but is independent of it.

Specification

    Currently, Erlang has

        Pattern <- Expr

    to enumerate over the elements of a single list and

        Pattern <= Expr

    to enumerate over a binary.  EEP 12 [1] adds

        Pattern [<-] List
        Pattern {<-} Tuple
        Pattern <<<->> Binary

    This proposal changes that to

        generator: term_generator | binary_generator;
        binary_generator: pattern '<=' expression;
        term_generator: term_generator '&&' term_generator
                      | pattern '<-' expression;

    if we otherwise stick with current Erlang, or

        generator: term_generator | binary_generator;
        binary_generator: pattern '<=' expression
                        | pattern '<<' '<-' '>>' expression;
        term_generator: term_generator '&&' term_generator
                      | pattern '<-' expression
                      | pattern '[' '<-' ']' expression
                      | pattern '{' '<-' '}' expression;

    if we go with EEP 12.

    The effect of P1 <- E1 && ... Pn <- En
    is the effect of {P1,...,Pn} <- zip(E1, ..., En)
    where

        zip([X1|Xs1], ..., [Xn|Xsn]) ->
            [{X1,...,Xn} | zip(Xs1, ..., Xsn)];
        zip([], ..., []) ->
            [].

    However, it is expected that there will NOT be any extra list
    or tuples created by the implementation; this specifies the
    effect but NOT how it is to be implemented.

    The effect of a term generator using the new notations of EEP 12
    is that which would be obtained by first replacing
        P {<-} E   with   P <- tuple_to_list(E)
        P [<-] E   with   P <- E
    and then applying the translation above.




Motivation

    "How do I iterate over several lists at once?" is a moderately
    common question from Erlang and Haskell beginners.  The stock
    answer, "use zip", is almost tolerable for Haskell, where the
    the zipping family goes up to 7 lists and the compiler works
    hard to eliminate the intermediate data structures by using
    deforestation.  For Erlang, where even zip4 is missing, and
    where the apparent cost of creating the unwanted list and
    tuples is all too real, the fact that the use of zips makes
    the code harder to read means that there is no good to
    outweigh the bad.

    With the new notation,

        zip4(As, Bs, Cs, Ds) ->
            [{A,B,C,D} || A <- As && B <- Bs && C <- Cs && D <- Ds].

        zipwith4(F, As, Bs, Cs, Ds) ->
            [F(A,B,C,D) || A <- As && B <- Bs && C <- Cs && D <- Ds].

        dot(Xs, Ys) ->
            sum([X*Y || X <- Xs && Y <- Ys]).

        ifelse(Tests, Xs, Ys) -> % Simulate R's ifelse(,,)
            [  case T of true -> X ; false -> Y end
            || T <- Tests && X <- Xs && Y <- Ys
            ].



Rationale

    This is a case where no invention is required, really.
    Clean has

        Qualifier = Generators {|Guard}
        Generators = {Generator}-list
                   | Generator {& Generator}
        Generator = Selector <- ListExpr // lazy list
                  | Selector <|- ListExpr // overloaded list
                  | Selector <-: ArrayExpr //  array

    All I have to do is bend this a little to fit it into Erlang
    syntax.  Since we use "||" for list comprehensions, "&&" was
    the obvious spelling for generators that step together.

    I do not yet understand in detail what the Erlang compiler
    does, but it seems to involve generating an auxiliary function.
    Let's take
        [f(X) || X <- Xs, X > 0]
    as an example.  This seems to be compiled as

        foo(Xs)
    where

        foo([X|Xs]) when X > 0 -> [f(X) | foo(Xs)];
        foo([_|Xs]) -> foo(Xs);
        foo([]) -> [].

    With a multigenerator, the translation is similar.

        [g(X, Y) || X <- Xs && Y <- Ys, X > Y]
    
    can be compiled as

        bar(Xs, Ys)

    where

        bar([X|Xs], [Y|Ys]) when X > Y ->
            [g(X, Y) | bar(Xs, Ys)];
        bar([_|Xs], [_|Ys]) -> bar(Xs, Ys);
        bar([], []) -> [].



Backwards Compatibility

    The "operator" '&&' is not legal syntax anywhere in Erlang
    at the moment, so no existing code can be affected.



Reference Implementation

    None yet, but I'd like to do it when I can figure out how.



References
    
    [1] EEP 12, http://www.erlang.org/eeps/eep-0012.html



Copyright

    This document has been placed in the public domain.



Local Variables:
mode: indented-text
indent-tabs-mode: nil
sentence-end-double-space: t
fill-column: 70
coding: utf-8
End: