Why is Flatten implemented the way it is?

[Raphael Collet]

Yves Jaradin wrote:
> Contrary to my expectations, I found List.flatten to be non-incremental 

I had a look at the sources.  You're right.  The Flatten in the sources 
is non-incremental and not very readable.

> (no result is available until the whole structure has been processed). I 
> supposed that Flatten was implemented as:
> 
> local
>   fun{Flatten2 Xs End}
>      case Xs
>      of nil then End
>      [] H|T then {Flatten2 H {Flatten2 T End}} % rather than the 
> incremental: []H|T then R I in {Flatten2 H I R} {Flatten2 T End I} R
>      else Xs|End
>      end
>   end
> in
>   fun{Flatten Xs}
>      {Flatten2 Xs nil}
>   end
> end

Well, your proposal is not incremental either...  Even the following 
expression is non-incremental (see why?).

    R I in {Flatten2 H I R} {Flatten2 T End I} R

You have to write it as a procedure:

%% incremental flatten with difference lists
local
    proc {DoFlatten L Start End}
       case L
       of nil then Start=End
       [] X|T then S in {DoFlatten X Start S} {DoFlatten T S End}
       else Start=L|End
       end
    end
in
    fun {Flatten L}
       {DoFlatten L $ nil}
    end
end

Here is another idea.  It is completely tail-recursive, and uses an 
explicit stack instead of two recursive calls.  This one is well 
designed to become lazy.

%% incremental tail-recursive flatten
local
    fun {DoFlatten L Stack}
       case L
       of X|T then {DoFlatten X T|Stack}
       [] nil then {DoFlatten Stack nil}
       else L|{DoFlatten Stack nil}
       end
    end
in
    fun {Flatten L}
       {DoFlatten L nil}
    end
end

> The current implementation of Flatten is also different from the rest of 
> the List module in it's treatment of '|'-labeled tuples with a non-list 
> second member. Those are errors in all the other cases but for Flatten 
> they are just non-list values.

Do you mean: {Flatten 1|2} is accepted, and returns 1|2?  No a great 
feature indeed.

> Has someone ever written code depending on this behavior? (which isn't 
> documented, documentation for Flatten isn't precise at all)
> Are those problems worth an incompatible change in future releases?

I think it is worth the change.  It will create a natural selection 
process on programmer that may rely on the unexpected feature ;-)

Cheers,
raph