What does “flatten” mean?

If I had a tree, would "flatten" intuitively imply

get a list of all items in the tree, traversing from left to right?

If i have a linked list, would "flatten" intuitively imply

get a list of all items, starting with this one

For example, a linked list would be made up of an exception that aggregates its inner exception. Would it be fair to name a method on exception "flattenInnerExceptions" with expectation that it would return a sequence of exceptions, outermost exception first, and inner-most exception -- last?

-

If I had a list of lists, “flatten” would be the operation that returns a list of all the leaf elements in order, i.e., something that changes:

``````[[a, b, c], [d, e, f], [g, h i]]
``````

Into

``````[a, b, c, d, e, f, g, h, i]
``````

For trees, flatting is generating a list of all leaves in natural traversal order (NB: since only leaves are in the result, it doesn't matter whether you think of this as pre-, in- or post-order traversal.)

As a consequence, for a simple list the “flatten” operation is by definition an identity transformation.

Flattening can be performed in stages, or degrees. For instance:

``````[[[a, b], [c, d]], [[e, f], [g, h]]]
``````

can be flattened to:

``````[[a, b, c, d], [e, f, g, h]]
``````

and then to:

`````` [a, b, c, d, e, f, g, h]
``````
-
@Donal Fellows: This addresses the half of the question about trees. What about linked lists? Is it intuitive to talk about them with the term "Flatten?" – GregC Apr 23 '11 at 16:23
@GregC, perhaps you would like to add an example of what you consider a linked list to be. – user1249 Apr 23 '11 at 16:36
Edited the question with an example. – GregC Apr 23 '11 at 16:43
@GregC: A linked list is just an implementation of a sequence abstract type. (An array is also an implementation of that abstract type on at least one level, and yes there are significant differences; abstract types aren't the whole story.) Most memory allocation systems make linked lists fairly expensive due to the fact that you're paying the memory allocation overhead per list cell (that overhead's often about 8 bytes on a 32-bit system) so I wouldn't recommend using them unless you've got a need for constant-time inserts and deletes. – Donal Fellows Apr 24 '11 at 13:56
Actually, wouldn't your example go straight from the first structure to the last without the middle step? The elements in the first list are all at level [][i]. I think the original one should be [[[a, b], [c, d]], [[e, f], [g, h]]]. Sorry to be a pedant! – Ed Woodcock Jun 7 '11 at 17:45