Why is Flatten implemented the way it is?

[Yves Jaradin]

Hello,

Contrary to my expectations, I found List.flatten to be non-incremental 
(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

which is not incremental due to the order of the execution of the two 
recursive-calls (first on T, then on H) but Flatten is implemented as:

local
   fun {DoFlatten Xs Start End}
      case Xs of
     X|Xr then S S1 in
     if {DoFlatten X S S1}
     then S=Start {DoFlatten Xr S1 End}
     else S2 in Start=X|S2 {DoFlatten Xr S2 End}
     end
      [] nil then Start=End true
      else false
      end
   end
in
   fun {Flatten X}
      Start in if {DoFlatten X Start nil} then Start else X end
   end
end

which isn't equivalent :
Test case -> result with first impl. -> result with actual impl.
{Flatten a|[b c d]|nul} -> [a b c d nul] -> a|[b c d]|nul
{Flatten a} -> [a] -> a

How is the actual implementation better than the simple one? (I assume 
that there was a reason for this design)
The main problems I see are:
* the result is not guaranteed to be a list (complicates proofs of 
correctness)
* impossibility to have a completely incremental implementation 
equivalent to the current one (bad for lazy programming)

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.
('|'-labeled tuples with a non-list second member are most probably 
erroneous constructs, so we don't really care of how they are 
transformed, do we?)

I didn't found any occurrence of Flatten depending on those border cases 
in share/lib (I didn't verified the occurrences in contrib, doc, 
share/test and share/tools)

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?

Thanks in advance,
Yves Jaradin